Skip to content

Instantly share code, notes, and snippets.

@robrix
Created March 31, 2021 22:44
Show Gist options
  • Save robrix/a6bdab903f516f42b9dfdad18a7da014 to your computer and use it in GitHub Desktop.
Save robrix/a6bdab903f516f42b9dfdad18a7da014 to your computer and use it in GitHub Desktop.
Recursion schemes over lists, in contrast with foldr/unfoldr
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment