What is the type of apomorphism specific to list and how is it implemented?

I am learning recursion schemes and it has proven very helpful to me to implement them specific to the list type. However, I got stuck on apomorphisms.

Here is an implementation of `tails` in terms of apo I recently found:

``````import Data.Functor.Foldable

tailsApo :: [a] -> [[a]]
tailsApo = apo coalgTails
where
coalgTails = \case
[] -> Cons [] (Left [])
li@(_:xs) -> Cons li (Right xs)
``````

Unfortunately, I couldn't import `Data.Functor.Foldable` with GHCi, because I get a package not found error. Another search revealed this implemenation of apo specific to lists:

``````apoList :: ([b] -> Maybe (a, Either [b] [a])) -> [b] -> [a]
apoList f b = case f b of
Nothing -> []
Just (x, Left c)  -> x : apoL f c
Just (x, Right e) -> x : e
``````

Obviously, `apoList`'s first argument doesn't match with `tailsApo`. I'd expext the type to be something like `apoList :: ([b] -> Either (a, b) [a])) -> [b] -> [a]`.

There seems to be no more beginner friendly information on this subject. I appreciate any help.

Solution

• `Data.Functor.Foldable` is provided by the recursion-schemes package. The type of `apo` there is:

``````apo :: Corecursive t => (a -> Base t (Either t a)) -> a -> t
``````

Here, `t` is the structure being generated by the unfold, and `Base t` is its base functor. Broadly speaking, the base functor represents one level of the recursive structure, the idea being that if we indefinitely nest it within itself we get a type equivalent to that of the whole structure -- in fact, that is precisely what `Fix` from `Data.Functor.Foldable` does. (On a meta note, there doesn't seem to be a Q&A here specifically about `Base` in recursion-schemes; it could be useful to have one.)

`Base` for lists is:

``````data ListF a b = Nil | Cons a b
``````

So `apo` specialises to:

``````apo @[_] :: (b -> ListF a (Either [a] b)) -> b -> [a]
``````

If we want to write it without using the recursion-scheme infrastructure, we can use the fact that `ListF a b` is isomorphic to `Maybe (a, b)`:

``````Nil     | Cons  a  b
Nothing | Just (a, b)
``````

In terms of `Maybe (a, b)`, the signature would then become:

``````apoList :: (b -> Maybe (a, Either [a] b)) -> b -> [a]
``````

In the coalgebra (that is, the function argument to `apo`), `Nothing` (or `Nil`, in the recursion-schemes version) signal the generation of the list should be stopped by capping it with an empty tail. That is why you still need `Maybe`, even if you are also using `Either` to short-circuit the unfold in other ways.

The implementation of this `apoList` is pretty much like the one in your question, except that this signature doesn't restrict the seed (of `b` type) to a list, and flips the roles of `Left` and `Right` (so that `Left` signals short-circuiting):

``````apoList :: (b -> Maybe (a, Either [a] b)) -> b -> [a]
apoList f b = case f b of
Nothing -> []
Just (x, Left e) -> x : e
Just (x, Right c) -> x : apoList f c
``````