Lazily consuming a self-referential linked list

VegOwOtenks:

Thanks for all the fancy words, made me look up and learn what (co-)algebras are.

You’re welcome I wasn’t sure if you were aware of them or not. Sorry for the dictionary shock.

VegOwOtenks:

what is a monadic anamorphism

I’ll explain an anamorphism first and then I will explain a monadic anamorphism. An anamorphism is a combinator for constructing recursive functions that construct/build recursive data structures.

-- | Given any functor construct it's recursive form.
data Fix f = Fix (f (Fix f))

-- | Given a co-algebra construct a function that produces a recursive data structure.
ana :: (Functor f) => (a -> f a) -> a -> Fix f
ana coalg = let c = Fix . fmap c . coalg in c

One provides a co-algebra (which is typically non-recursive) to an anamorphism and the anamorphism provides a function that creates the recursive data structure. Technically however, the functor that’s in use corresponds to a class of recursive data structures. And that’s what the Recursive/CoRecursive type classes and the Base type family are for. I don’t have room to explain that here. So instead of using Fix f as the co-domain (return type) of the function we can use a more concrete data structure like [e].

The functor f above describes the structure of a single layer of recursion (when to terminate, and when to keep going, what data to remember at each layer etc). The purpose of the anamorphism is then to produce the fully recursive function a -> Fix f. Here’s a concrete example:

data ListF e a = Nil | Cons e a
  deriving (Functor f)

nSized :: Natural -> ListF Natural Natural
nSized 0 = Nil
nSized n = Cons n (n-1)

-- Fix (ListF e) ~ [e]
sizedList :: Natural -> [Natural]
sizedList = ana evens

Monadic anamorphisms are anamorphisms that operate over a monad. More concretely their co-domain is wrapped in a monad m - in both the co-algebra and the return type:

ana  :: (Functor f)          => (a ->    f a)  -> a ->    Fix f
anaM :: (Monad m, Functor f) => (a -> m (f a)) -> a -> m (Fix f)

Now let’s say that you want to write a program where the user gives your program n names to consume via CLI prompts. You’ll need a way ask the user for a value as noted by askforName. Now let’s say we will keep asking the user for values until they type “done”. We’ll need to recursively ask for a name, check if the given string is equivalent to “done” and then based on the resulting truth value we terminate or we recurse.

We can use a monadic anamorphism to accomplish this. I’ll write the proof steps below:

import Data.Functor ((<&>))

-- If IO throws exceptions we won't handle them here.
askForName :: IO String
askForName = do
  putStrLn "Next name please:"
  getLine

-- Claim: allNames can be defined using a monadic anamorphism
allNames  :: IO [String] -- we want to construct this
  {- forall a. a ~ () -> a -}
  -- :: () -> IO [String]
  {- exists f. Base t ~ f. t ~ Fix f -}
  -- :: () -> IO (Fix (ListF String))
allNames = anaM nextName ()

nextName :: () -> IO (ListF String ())
nextName _ = askForName <&> \case
  -- we're done, terminate
  "done" -> Nil
  -- assume the user typed a valid name...
  name   -> Cons name ()

The benefit of nextName is that it’s non-recursive. The ListF functor completely determines the structure of the recursion and when we terminate becomes very clear. Unfortunately this example doesn’t show case the full power of recursion schemes, however I’ve written many a server streaming handler with them with robust error handling and you can imagine the recursion gets very tricky. Recursion schemes solves many of these problems.

I believe a lot of mistakes in Haskell can be avoided by writing recursion-schemes instead of explicit recursion. If you’re interested in learning more:

• Here is a great resource to learn more about recursion schemes.
• I highly recommend reading the Programming with Bananas Lenses Envelopes and Barbed Wire functional perl. It can be overwhelming at first but if you have the time and energy to wade through it you’ll be a changed programmer (for example you’ll begin to spot easy ways to refactor your code and create optimizations algebraically).

I will post another response after I did int your code a bit more.