haskellrecursionrecursion-schemes# Histomorphisms, Zygomorphisms and Futumorphisms specialised to lists

I ended up figuring it out. See the video and slides of a talk I gave:

Original question:

In my effort to understand generic recursion schemes (i.e., that use `Fix`

) I have found it useful to write list-only versions of the various schemes. It makes it much easier to understand the actual schemes (without the additional overhead of the `Fix`

stuff).

However, I have not yet figured out how to define list-only versions of `zygo`

and `futu`

.

Here are my specialised definitions so far:

```
cataL :: (a -> b -> b) -> b -> [a] -> b
cataL f b (a : as) = f a (cataL f b as)
cataL _ b [] = b
paraL :: (a -> [a] -> b -> b) -> b -> [a] -> b
paraL f b (a : as) = f a as (paraL f b as)
paraL _ b [] = b
-- TODO: histo
-- DONE: zygo (see below)
anaL :: (b -> (a, b)) -> b -> [a]
anaL f b = let (a, b') = f b in a : anaL f b'
anaL' :: (b -> Maybe (a, b)) -> b -> [a]
anaL' f b = case f b of
Just (a, b') -> a : anaL' f b'
Nothing -> []
apoL :: ([b] -> Maybe (a, Either [b] [a])) -> [b] -> [a]
apoL f b = case f b of
Nothing -> []
Just (x, Left c) -> x : apoL f c
Just (x, Right e) -> x : e
-- DONE: futu (see below)
hyloL :: (a -> c -> c) -> c -> (b -> Maybe (a, b)) -> b -> c
hyloL f z g = cataL f z . anaL' g
hyloL' :: (a -> c -> c) -> c -> (c -> Maybe (a, c)) -> c
hyloL' f z g = case g z of
Nothing -> z
Just (x,z') -> f x (hyloL' f z' g)
```

How do you define `histo`

, `zygo`

and `futu`

for lists?

Solution

*Zygomorphism* is the high-falutin' mathsy name we give to folds built from two *semi-mutually* recursive functions. I'll give an example.

Imagine a function `pm :: [Int] -> Int`

(for *plus-minus*) which intersperses `+`

and `-`

alternately through a list of numbers, such that `pm [v,w,x,y,z] = v - (w + (x - (y + z)))`

. You can write it out using primitive recursion:

```
lengthEven :: [a] -> Bool
lengthEven = even . length
pm0 [] = 0
pm0 (x:xs) = if lengthEven xs
then x - pm0 xs
else x + pm0 xs
```

Clearly `pm0`

is not compositional - you need to inspect the length of the whole list at each position to determine whether you're adding or subtracting. *Paramorphism* models primitive recursion of this sort, when the folding function needs to traverse the whole subtree at each iteration of the fold. So we can at least rewrite the code to conform to an established pattern.

```
paraL :: (a -> [a] -> b -> b) -> b -> [a] -> b
paraL f z [] = z
paraL f z (x:xs) = f x xs (paraL f z xs)
pm1 = paraL (\x xs acc -> if lengthEven xs then x - acc else x + acc) 0
```

But this is inefficient. `lengthEven`

traverses the whole list at each iteration of the paramorphism resulting in an O(n^{2}) algorithm.

We can make progress by noting that both `lengthEven`

and `para`

can be expressed as a *catamorphism* with `foldr`

...

```
cataL = foldr
lengthEven' = cataL (\_ p -> not p) True
paraL' f z = snd . cataL (\x (xs, acc) -> (x:xs, f x xs acc)) ([], z)
```

... which suggests that we may be able to fuse the two operations into a single pass over the list.

```
pm2 = snd . cataL (\x (isEven, total) -> (not isEven, if isEven
then x - total
else x + total)) (True, 0)
```

We had a fold which depended on the result of another fold, and we were able to fuse them into one traversal of the list. Zygomorphism captures exactly this pattern.

```
zygoL :: (a -> b -> b) -> -- a folding function
(a -> b -> c -> c) -> -- a folding function which depends on the result of the other fold
b -> c -> -- zeroes for the two folds
[a] -> c
zygoL f g z e = snd . cataL (\x (p, q) -> (f x p, g x p q)) (z, e)
```

On each iteration of the fold, `f`

sees its answer from the last iteration as in a catamorphism, but `g`

gets to see both functions' answers. `g`

entangles itself with `f`

.

We'll write `pm`

as a zygomorphism by using the first folding function to count whether the list is even or odd in length and the second one to calculate the total.

```
pm3 = zygoL (\_ p -> not p) (\x isEven total -> if isEven
then x - total
else x + total) True 0
```

This is classic functional programming style. We have a higher order function doing the heavy lifting of consuming the list; all we had to do was plug in the logic to aggregate results. The construction evidently terminates (you need only prove termination for `foldr`

), and it's more efficient than the original hand-written version to boot.

Aside: @AlexR points out in the comments that zygomorphism has a big sister calledmutumorphism, which captures mutual recursion in all its glory.`mutu`

generalises`zygo`

in thatboththe folding functions are allowed to inspect the other's result from the previous iteration.`mutuL :: (a -> b -> c -> b) -> (a -> b -> c -> c) -> b -> c -> [a] -> c mutuL f g z e = snd . cataL (\x (p, q) -> (f x p q, g x p q)) (z, e)`

You recover

`zygo`

from`mutu`

simply by ignoring the extra argument.`zygoL f = mutuL (\x p q -> f x p)`

Of course, all of these folding patterns generalise from lists to the fixed point of an arbitrary functor:

```
newtype Fix f = Fix { unFix :: f (Fix f) }
cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix
para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para f = snd . cata (\x -> (Fix $ fmap fst x, f x))
zygo :: Functor f => (f b -> b) -> (f (b, a) -> a) -> Fix f -> a
zygo f g = snd . cata (\x -> (f $ fmap fst x, g x))
mutu :: Functor f => (f (b, a) -> b) -> (f (b, a) -> a) -> Fix f -> a
mutu f g = snd . cata (\x -> (f x, g x))
```

Compare the definition of `zygo`

with that of `zygoL`

. Also note that `zygo Fix = para`

, and that the latter three folds can be implemented in terms of `cata`

. In foldology everything is related to everything else.

You can recover the list version from the generalised version.

```
data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)
zygoL' :: (a -> b -> b) -> (a -> b -> c -> c) -> b -> c -> List a -> c
zygoL' f g z e = zygo k l
where k Nil_ = z
k (Cons_ x y) = f x y
l Nil_ = e
l (Cons_ x (y, z)) = g x y z
pm4 = zygoL' (\_ p -> not p) (\x isEven total -> if isEven
then x - total
else x + total) True 0
```

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code