Susan Potter

Practical Recursion Schemes

Mon October 10, 2018

DRAFT

Recursive data types

Recursive data structures pop up all over in software from general-purpose structures like lists and binary trees to more application-specific structures like this AST from a simple business rules engine:

  data BusinessRule input output
    = IfThenElse (input -> Bool) (BusinessRule input output) (BusinessRule input output)
    | Return (input -> output)
    | Stop

Functor

Foldable

The Foldable class gives you the ability to process the elements of a structure one-at-a-time, discarding the shape.

Intuitively this is an assortment of List-like fold methods on other structures

class Foldable t where
  foldMap :: Monoid m => (a -> m) -> t a -> m
  fold    :: Monoid m => t m -> m
  foldr   :: (a -> b -> b) -> b -> t a -> b
  foldl   :: (a -> b -> a) -> a -> t b -> a
  foldr1  :: (a -> a -> a) -> t a -> a
  foldl1  :: (a -> a -> a) -> t a -> a

Example of defining a Foldable instance manually:

data Tree a
  = Empty
  | Leaf a
  | Node (Tree a) (Tree a)

instance Foldable Tree where
  foldMap f Empty = mempty
  foldMap f (Leaf x) = f x
  foldMap f (Node l r) = foldMap f l <> foldMap f r

count :: Foldable t => t a -> Int
count = getSum . foldMap (const $ Sum 1)

Foldable is derivable using the DeriveFoldable language pragma like so:

data Tree a
  = Empty
  | Leaf a
  | Node (Tree a) (Tree a)
  deriving (Foldable)

Traversable

Traversable gives you the ability to traverse a structure from left-to-right, performing an effectful action on each element and preserving the shape.

  • Intuitively it is fmap with effects

  • Derivable using DeriveTraversable language pragma

  • See 'Applicative Progamming with Effects', by McBride and Paterson

class (Functor t, Foldable t) => Traversable t where
  traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
  sequenceA :: Applicative f => t (f a) -> f (t a)
  mapM      :: Monad m => (a -> m b) ->  t a ->  m (t a)
  sequence  :: Monad m => t (m a) -> m (t a)

Example for this for Tree type defining the instance manually is:

instance Traversable Tree where
  traverse f Empty = pure Empty
  traverse f (Leaf x) = Leaf <$> f x
  traverse f (Node l r) = Node <$> traverse f l <*> traverse f r

Notes:

  • mapM and sequence generalize Prelude functions of the same name

  • sequence can also be thought of as a generalized matrix transpose

sequence :: Monad m => t (m a) -> m (t a)
sequence = mapM id

Fixed Points of Functors

An idea from category theory which gives:

  • data-type generic functions

  • compositional data

Fixed points are represented by the type:

newtype Fix f = Fix { unFix :: f (Fix f) }

A functor f is a data-type of kind * -> * together with an fmap function.

Fix f = f (f (f (f ...

Useful functions

fan-out aka fork

(&&&)
  :: (b -> c)
  -> (b -> d)
  -> b
  -> (c, d)
(f &&& g) = \x -> (f x, g x)

fan-in

(|||)
  :: (b -> d)
  -> (c -> d)
  -> Either b c
  -> d
(f ||| g) = either

function product

(***)
  :: (a -> c)
  -> (b -> d)
  -> (a, b)
  -> (c, d)
(f *** g) = \(x, y) -> (f x, g y)

generalized unzip for functions

funzip
  :: Functor f
  => f (a, b)
  -> (f a, f b)
funzip = fmap fst &&& fmap snd

Data-type generic programming

  • allows us to parameterise functions on the structure, or shape, of a data-type

  • useful for large complex data-types, where boilerplate traversal code often dominates, especially when updating a small subset of constructors

  • for recursion schemes, we can capture the pattern as a standalone combinator

Limitations:

  • The set of data-types that can be represented by means of Fix is limited to regular data-types.

  • Nested data-types and mutually recursive data-types require higher-order approaches.

In order to work with lists using a data-type generic cata combinator, we need a new "unfixed" type representation.

data ListF a r = C a r | N

ListF a r is not an ordinary functor, but we can define a polymorphic functor instance for ListF a

instance Functor (ListF a) where
  fmap f N = N
  fmap f (C x xs) = C x (f xs)

We might also want a pattern functor for natural numbers!

data NatF r = Succ r | Zero deriving Functor

Catamorphism

We would like to write foldr once for all data-types. Category theory shows us how to define it data-type generically for a functor fixed-point.

That catamorphism-fusion law

The catamorphism-fusion law is arguably the most important law, and can be used to transform the composition of a function with a catamorphism into a single catamorphism, eliminating intermediate data structures.

h . f = g . fmap h => h . cata f = cata g
  where f :: f a -> a
        g :: f b -> b
        h :: a -> b

Composing Algebras