Recursion schemes over lists, in contrast with foldr/unfoldr

FoldsAndUnfolds.hs

module FoldsAndUnfolds where

import Data.List -- for unfoldr

class Functor f => Recursive f t | t -> f where
  project :: t -> f t

  cata :: (f a -> a) -> t -> a
  cata alg = go where go = alg . fmap go . project


class Functor f => Corecursive f t | t -> f where
  inject :: f t -> t

  ana :: (a -> f a) -> a -> t
  ana coalg = go where go = inject . fmap go . coalg


data ListF a b = Nil | Cons a b
  deriving (Functor)

instance Recursive (ListF a) [a] where
  project = \case
    []   -> Nil
    x:xs -> Cons x xs

  -- relative to unfoldr/ana, the foldr/cata relationship is obscured somewhat
  -- by splitting the cases of the algebra into separate arguments. we recover
  -- them here by manually constructing ListF values to apply alg to.
  cata alg = foldr (\ a as -> alg (Cons a as)) (alg Nil)

instance Corecursive (ListF a) [a] where
  inject = \case
    Nil       -> []
    Cons x xs -> x:xs

  ana coalg = unfoldr (convert . coalg)
    where
    -- map the constructors of ListF a b onto the constructors of Maybe (a, b).
    -- we could also have defined ListF as a newtype around Maybe (a, b) and
    -- given it pattern synonyms or something, but meh.
    convert = \case
      Nil       -> Nothing
      Cons a as -> Just (a, as)