haskellrecursioncatamorphismrecursion-schemes# A library implementation of a recursion scheme

I 'invented' a recursion scheme which is a generalization of catamorphism. When you fold a data structure with catamorphism you don't have access to subterms, only to subresults of folding:

```
{-# LANGUAGE DeriveFunctor #-}
import qualified Data.Map as M
newtype Fix f = Fix { unFix :: f (Fix f) }
cata :: Functor f => (f b -> b) -> Fix f -> b
cata phi = self where
self = phi . fmap (\x -> self x) . unFix
```

The folding function `phi`

has only access to the result of `self x`

, but not to original `x`

. So I added a joining function:

```
cataWithSubterm :: Functor f => (Fix f -> c -> b) -> (f b -> c) -> Fix f -> c
cataWithSubterm join phi = self
where self = phi . fmap (\x -> join x (self x)) . unFix
```

Now it's possible to combine `x`

and `self x`

in a meaningful way, for example using `(,)`

:

```
data ExampleFunctor a = Var String | Application a a deriving Functor
type Subterm = Fix ExampleFunctor
type Result = M.Map String [Subterm]
varArgs :: ExampleFunctor (Subterm, Result) -> Result
varArgs a = case a of
Var _ -> M.empty
Application ((Fix (Var var)), _) (arg, m) -> M.insertWith (++) var [arg] m
processTerm :: (ExampleFunctor (Subterm, Result) -> Result) -> Subterm -> Result
processTerm phi term = cataWithSubterm (,) phi term
```

`processTerm varArgs`

returns for each identifier the list of actual arguments it receives on different control paths. E.g. for `bar (foo 2) (foo 5)`

it returns `fromList [("foo", [2, 5])]`

Note that in this example results are combined uniformly with other results, so I expect existence of a simpler implementation using a derived instance of `Data.Foldable`

. But in general it's not the case as `phi`

can apply its knowledge of internal structure of `ExampleFunctor`

to combine 'subterms' and 'subresults' in ways not possible with Foldable.

My question is: can I build `processTerm`

using stock functions from a modern recursion schemes library such as `recursion-schemes/Data.Functor.Foldable`

?

Solution

Folding such that it "eats the argument and keeps it too" is called a paramorphism. Indeed, your function can be readily expressed using *recursion-schemes* as

```
cataWithSubterm :: Functor f => (Fix f -> b -> a) -> (f a -> b) -> Fix f -> b
cataWithSubterm f g = para $ g . fmap (uncurry f)
```

Moreover, if we supply `(,)`

to `cataWithSubterm`

as you did in `processTerm`

, we get

```
cataWithSubterm (,) :: Functor f => (f (Fix f, b) -> b) -> Fix f -> b
```

which is precisely `para`

specialized for `Fix`

:

```
para :: Functor f => (f (Fix f, b) -> b) -> Fix f -> b
```

- What is the proper way of wrapping an Int (not a general type) in another type if type safety is the only motive?
- What is the most practical way to express a dependency on a library for which we have a local git repository with some changes?
- Htmx POST to haskell servant handling optional field in FormUrlEncoded request
- Haskell fails to infer the return type of a monad after using the sequence operator
- Does extracting values from a multiple Value return in Haskell invoke the function more than once?
- How to specify c/c++ compiler on stack install command
- Why do I get "Unexpected reply type" from notify-send when using this Haskell notification server?
- Don't understand notation of morphisms in Monoid definition
- Foldln in haskell
- Is this property of a functor stronger than a monad?
- How to Instantiate a Custom Data Type with Record Syntax and Multiple Constructors
- How do I make a minimal working example for the a DBus server?
- Is it safe to downgrade Haskell stack version?
- Haskell, list of natural number
- unfamiliar syntax in Haskell / Clash function type signature
- foldM with monad State does not type check
- Why does my Runge-Kutta implementation oscillate to 0?
- How do I get the desired behavior in my TCP server?
- Why does the Haskell PVP describe new functions as non-breaking?
- How do I correctly use toLower in Haskell?
- How can I write a notification server in Haskell?
- Every Lens' is a Traversal'... how?
- How do I crate a value of type a{sv} for a call to org.freedesktop.Notifications.Notify via DBus?
- Web Scraping With Haskell
- Double exclamation marks in Haskell
- Haskell Servant POST FormUrlEncoded for (Vector String) field
- Confusion about list types in Haskell
- Idiomatic way to define new vs persisted types in Haskell
- Why does Cabal, unlike GHC, not automatically enable GeneralizedNewtypeDeriving if I explicitly enabled DerivingStrategies?
- Parsing inside `between` with Megaparsec