haskellrecursion-schemesunfold# 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
```

- 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