Module documentation for 5.2.3

• Data
  • Data.Functor
    • Data.Functor.Base
    • Data.Functor.Foldable

recursion-schemes

This package represents common recursion patterns as higher-order functions.

A familiar example

Here are two recursive functions.

sum :: [Int] -> Intsum [] = 0sum (x:xs) = x + sum xsproduct :: [Int] -> Intproduct [] = 1product (x:xs) = x * product xs

These functions are very similar. In both cases, the empty list is the base case. In the cons case, each makes a recursive call on the tail of the list. Then, the head of the list is combined with the result using a binary function.

We can abstract over those similarities using a higher-order function,foldr:

sum     = foldr (+) 0product = foldr (*) 1

Other recursive types

foldr works great for lists. The higher-order functions provided by this library help with other recursive datatypes. Here are two recursive functions onTrees:

depth :: Tree a -> Intdepth (Node _ subTrees) = 1 + maximum subTreessize :: Tree a -> Intsize (Node _ subTrees) = 1 + sum subTrees

It is not possible to usefoldr to simplifydepth. Conceptually,foldr is flattening all the elements of the tree into a list before combining them with the binary function. This does not work fordepth because it needs to examine the structure of the tree, whichfoldr flattened away.

We can instead use one of the higher-order functions provided by this library,cata.

import Data.Functor.Base (TreeF(..))import Data.Functor.Foldable-- data Tree  a   = Node  a [Tree a]-- data TreeF a r = NodeF a [r     ]depth :: Tree a -> Intdepth = cata go  where    go :: TreeF a Int -> Int    go (NodeF _ subDepths) = 1 + maximum subDepthssize :: Tree a -> Intsize = cata go  where    go :: TreeF a Int -> Int    go (NodeF _ subSizes) = 1 + sum subSizes

In this example, the code is a bit longer, but it is correct. Did you spot the mistake in the version which does not usecata? We forgot a call tofmap:

depth :: Tree a -> Intdepth (Node _ subTrees) = 1 + maximum (fmap depth subTrees)size :: Tree a -> Intsize (Node _ subTrees) = 1 + sum (fmap size subTrees)

cata automatically adds this call tofmap. This is whysubDepths contains a list of already-computed depths, not a list of sub-trees. In general, each recursive position is replaced by the result of a recursive call. These results have typeInt, not typeTree, so we need a helper datatypeTreeF to collect these results.

When you think about computing the depth, you probably think “it’s 1 plus the maximum of the sub-depths”. Withcata, this is exactly what we write. By contrast, withoutcata, we need to describe both the “how” and the “what” in our implementation. The “how” is about recurring over the sub-trees (usingfmap depth), while the “what” is about adding 1 to the maximum of the sub-trees.cata takes care of the recursion, so you can focus solely on the “what”.

Arecursion-scheme is a function likecata which implements a common recursion pattern. It is a higher-order recursive function which takes a non-recursive function as an argument. That non-recursive function describes the part which is unique to your calculation: the “what”.

Types with many constructors

Let’s look at a more complex example. Here is a small lambda-calculus and a function to compute thefree variables of an expression:

import Data.Set (Set)import qualified Data.Set as Setdata Expr  = Var String  | Lam String Expr  | App Expr Expr  | Constant Int  | Add Expr Expr  | Sub Expr Expr  | Mul Expr Expr  | Div Expr Expr  | ...freeVars :: Expr -> Set StringfreeVars (Var name)      = Set.singleton namefreeVars (Lam name body) = Set.difference (freeVars body) (Set.singleton name)freeVars (App e1 e2)     = Set.union (freeVars e1) (freeVars e2)freeVars (Constant _)    = Set.emptyfreeVars (Add e1 e2)     = Set.union (freeVars e1) (freeVars e2)freeVars (Sub e1 e2)     = Set.union (freeVars e1) (freeVars e2)freeVars (Mul e1 e2)     = Set.union (freeVars e1) (freeVars e2)freeVars (Div e1 e2)     = Set.union (freeVars e1) (freeVars e2)freeVars ...

As you can see, we had to repeat theSet.union (freeVars e1) (freeVars e2) line over and over. With recursion-schemes, this code becomes much shorter:

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable, TemplateHaskell, TypeFamilies #-}import Data.Functor.Foldable.TH (makeBaseFunctor)makeBaseFunctor ''ExprfreeVars :: Expr -> Set StringfreeVars = cata go  where    go :: ExprF (Set String) -> Set String    go (VarF name)           = Set.singleton name    go (LamF name bodyNames) = Set.difference bodyNames (Set.singleton name)    go fNames                = foldr Set.union Set.empty fNames

ThemakeBaseFunctor line uses Template Haskell to generate ourExprF datatype, a single layer of theExpr datatype.makeBaseFunctor also generates instances which are useful when using recursion-schemes. For example, we make use of theFoldable ExprF instance on the last line ofgo. ThisFoldable instance exists becauseExprF has kind* -> *, whileExpr has kind*.

Other recursion-schemes

All of our examples so far have usedcata. There are many more recursion-schemes. Here is an example which follows a different recursive structure:

-- |-- >>> halves 256-- [256,128,64,32,16,8,4,2,1]halves :: Int -> [Int]halves 0 = []halves n = n : halves (n `div` 2)

That recursive structure is captured by theana recursion-scheme:

halves :: Int -> [Int]halves = ana go  where    go :: Int -> ListF Int Int    go 0 = Nil    go n = Cons n (n `div` 2)

TheData.Functor.Foldable module provides many more.

Flowchart for choosing a recursion-scheme

In addition to the choices described by the flowchart, you can always choose to use a refold.

Contributing

Contributions andbug reports are welcome!

5.2.3 [2024-06-12]

• Support GHC-9.10.
• Drop support for GHC-7.10 and earlier.

5.2.2.5 [2023-10-14]

• Support GHC-9.6 and GHC-9.8
• Supportth-abstraction-0.6.0.0 or later.

5.2.2.4 [2023-02-27]

• Supportth-abstraction-0.5.0.0 or later.

5.2.2.3

• Support GHC-9.4
• Workaround forhttps://gitlab.haskell.org/ghc/ghc/-/issues/18320, which waspreventing code calling makeBaseFunctor from being profiled.

5.2.2.2

• Support GHC-9.0 and GHC-9.2

5.2.2.1

• Fix build issue regardingSetup.hs. See #120.

5.2.2

• More Mendler-style recursion-schemes:mpara,mzygo,mana,mapo, andmfutu.
• makeBaseFunctor no longer generates warnings when combined withDerivingStrategies.

5.2.1 [2020-10-04]

• Allow building withtemplate-haskell-2.17.0.0 (GHC 9.0).

5.2

• Add instances forTree (fromcontainers)
• Add some haddocks and basic examples
• Generalize the type ofmakeBaseFunctor(With), such thatit can take alsoDec. This way you may supply context forRecursiveandCorecursive instances.
• Depend ondata-fix package for fixed point types.

5.1.3 [2019-04-26]

• Supportth-abstraction-0.3.0.0 or later.

5.1.2

• Make theGeneric-based instances to also support data constructors with zeroarguments (and datatypes with zero constructors).

5.1.1.1

• Invalid release

5.1.1

• Addcotransverse
• AddGeneric based default implementation toembed andproject.Recursive andCorecursive can beDeriveAnyClass-derived now,if you write the base functor by hand.

5.1

• Export gfutu
• distGHisto,ghisto, andgchrono now useCofree (Base t)
• distGFutu,gfutu, andgchrono now useFree (Base t)
• Addhoist,hoistMu andhoistNu
• Addtransverse andcataA

5.0.3 [2018-07-01]

• Make the Template Haskell machinery look through type synonyms.
• Avoid incurring some dependencies when using recent GHCs.

5.0.2

• Support GHC-8.2.1
• Fix Template Haskell derivation with non-default type renamer.
• AddRecursive andCorecursive Natural instances, withBase Natural = Maybe.

5.0.1

• AddData.Functor.Foldable.TH module, which provides derivation of base functors via Template Haskell.

5

• RenamedFoldable toRecursive andUnfoldable toCorecursive. WithFoldable inPrelude in GHC 7.10+, having a needlessly conflicting name seemed silly.
• Add support for GHC-8.0.1
• UseEq1,Ord1,Show1,Read1 to deriveFix,Nu andMuEq,OrdShow andRead instances
• RemovePrim data family.ListF as a new name forPrim [a], with plenty of instances, e.g.Traversable.
• Exportunfix
• Add chronomorphisms:chrono andgchrono.
• AdddistGApoT

4.1.2

• Support forfree 4.12.1

4.1.1

• Support for GHC 7.10
• Fixedpara.

4.1

• Support for GHC 7.7+’s generalizedTypeable.
• Fastergapo andpara by exploiting sharing.

4.0

• Compatibility withcomonad andfree version 4.0

3.0

• Compatibility withtransformers 0.3
• Resolved deprecation warnings caused by changes toData.Typeable