5. Recursion schemes¶

Traversing an EADT explicitly (see Explicit recursive traversal) can be tedious. Another approach consists in using dedicated composable combinators called recursion schemes.

The well known `map` and `fold` functions are examples of recursion schemes for lists: these functions handle the recursive traversal of the data structure and are parameterized by the functions performing the actual work. Recursion schemes are a generalization of this approach.

The best introduction to recursion schemes I’ve read can be found here: https://blog.sumtypeofway.com/an-introduction-to-recursion-schemes/

To avoid paraphrasing, I recommend that you read it before continuing.

5.1. Catamorphism: Show example¶

Suppose we rewrite our `Show` class like this:

```class FunctorShow (f :: * -> *) where
functorShow :: f String -> String
```

We can define instances for `NilF` and `ConsF`:

```instance FunctorShow NilF where
functorShow _ = "Nil"

instance (Show a) => FunctorShow (ConsF a) where
functorShow (ConsF a l) = show a ++ " : " ++ l
```

Note that there is no recursive call in the definition of `ConsF`’s instance: it is because we are going to use a recursion scheme that will handle the recursion.

We also need an instance to handle the generic `VariantF` type:

```instance (AlgVariantF FunctorShow String xs) => FunctorShow (VariantF xs) where
functorShow = algVariantF @FunctorShow functorShow
```

Finally we can define a generic `eadtShow` function that uses the catamorphism recursion scheme with the `functorShow` class method.

```eadtShow ::
( Functor (VariantF xs)
, FunctorShow (VariantF xs)
) => EADT xs -> String
```

We can test it:

```intList :: List Int
intList = Cons (10 :: Int) \$ Cons (20 :: Int) \$ Cons (30 :: Int) Nil

mixedList :: EADT '[ConsF Int, ConsF Float, ConsF String, NilF]
mixedList = Cons @Int 10 \$ Cons @Float 5.0 \$ Cons "Test" Nil

10 : 20 : 30 : Nil

10 : 5.0 : "Test" : Nil
```

5.2. Catamorphism: List (a -> a) mapping example¶

Similarily to the example above, suppose that we want to implement mapping over an EADT list. We can use the following type-class:

```class MapEADT a xs (f :: * -> *) where
-- map the outer constructor of an EADT
```

We need some instances to handle our EADT constructors:

```instance (NilF :<: xs) => MapEADT a xs NilF where

instance (ConsF a :<: xs) => MapEADT a xs (ConsF a) where
mapEADT1 f (ConsF a x) = Cons (f a) x
```

And a additional instance to traverse the `VariantF` combinator datatype:

```instance (AlgEADT (MapEADT a xs) xs) => MapEADT a xs (VariantF xs) where
```

Now we can define the `mapEADT` function by using the catamorphism combinator:

```-- recursively map an EADT
mapEADT :: ( Functor (VariantF xs)
, MapEADT a xs (VariantF xs)
```

We can test it:

```intList :: List Int
intList = Cons (10 :: Int) \$ Cons (20 :: Int) \$ Cons (30 :: Int) Nil

> putStrLn \$ eadtShow \$ mapEADT ((+5) :: Int -> Int) intList
15 : 25 : 35 : Nil
```

5.3. Catamorphism: List (a -> b) mapping example¶

Similarily, we can also support mapping with a function that changes the EADT type as follow:

```class TransEADT a b xs xs' (f :: * -> *) where

instance (NilF :<: xs') => TransEADT a b xs xs' NilF where

instance (ConsF b :<: xs', xs ~ xs') => TransEADT a b xs xs' (ConsF a) where
transEADT1 f (ConsF a x) = Cons (f a) x

instance TransEADT a b xs xs' (VariantF '[]) where

instance
( TransEADT a b xs xs' f
, TransEADT a b xs xs' (VariantF fs)
) => TransEADT a b xs xs' (VariantF (f ': fs)) where
Right u -> transEADT1 f u
Left  w -> transEADT1 f w

transEADT :: ( Functor (VariantF xs)
, TransEADT a b xs' xs' (VariantF xs)
```> putStrLn \$ eadtShow \$ (transEADT (fromIntegral :: Int -> Float) intList :: List Float)