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