# recursion-schemes

Representing common recursion patterns as higher-order functions

http://github.com/ekmett/recursion-schemes/

 Version on this page: 5.2.2.1 LTS Haskell 22.34: 5.2.3 Stackage Nightly 2024-09-09: 5.2.3 Latest on Hackage: 5.2.3

See all snapshots `recursion-schemes` appears in

This version can be pinned in stack with:`recursion-schemes-5.2.2.1@sha256:fed7167e83698147d7c078bbb1fe74451f96c7c55ed9986c734d268070d85864,3728`

#### Module documentation for 5.2.2.1

• Data
• Data.Functor
Depends on 9 packages(full list with versions):
Used by 5 packages in lts-18.6(full list with versions):

# recursion-schemes

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

## A familiar example

Here are two recursive functions.

``````sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + sum xs

product :: [Int] -> Int
product [] = 1
product (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 (+) 0
product = 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 on `Tree`s:

``````depth :: Tree a -> Int
depth (Node _ subTrees) = 1 + maximum subTrees

size :: Tree a -> Int
size (Node _ subTrees) = 1 + sum subTrees
``````

It is not possible to use `foldr` to simplify `depth`. Conceptually, `foldr` is flattening all the elements of the tree into a list before combining them with the binary function. This does not work for `depth` because it needs to examine the structure of the tree, which `foldr` 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 -> Int
depth = cata go
where
go :: TreeF a Int -> Int
go (NodeF _ subDepths) = 1 + maximum subDepths

size :: Tree a -> Int
size = 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 use `cata`? We forgot a call to `fmap`:

``````depth :: Tree a -> Int
depth (Node _ subTrees) = 1 + maximum (fmap depth subTrees)

size :: Tree a -> Int
size (Node _ subTrees) = 1 + sum (fmap size subTrees)
``````

`cata` automatically adds this call to `fmap`. This is why `subDepths` 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 type `Int`, not type `Tree`, so we need a helper datatype `TreeF` to collect these results.

When you think about computing the depth, you probably think “it’s 1 plus the maximum of the sub-depths”. With `cata`, this is exactly what we write. By contrast, without `cata`, we need to describe both the “how” and the “what” in our implementation. The “how” is about recurring over the sub-trees (using `fmap 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”.

A recursion-scheme is a function like `cata` 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 the free variables of an expression:

``````import Data.Set (Set)
import qualified Data.Set as Set

data Expr
= Var String
| Lam String Expr
| App Expr Expr
| Constant Int
| Sub Expr Expr
| Mul Expr Expr
| Div Expr Expr
| ...

freeVars :: Expr -> Set String
freeVars (Var name)      = Set.singleton name
freeVars (Lam name body) = Set.difference (freeVars body) (Set.singleton name)
freeVars (App e1 e2)     = Set.union (freeVars e1) (freeVars e2)
freeVars (Constant _)    = Set.empty
freeVars (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 the `Set.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 ''Expr

freeVars :: Expr -> Set String
freeVars = 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
``````

The `makeBaseFunctor` line uses Template Haskell to generate our `ExprF` datatype, a single layer of the `Expr` datatype. `makeBaseFunctor` also generates instances which are useful when using recursion-schemes. For example, we make use of the `Foldable ExprF` instance on the last line of `go`. This `Foldable` instance exists because `ExprF` has kind `* -> *`, while `Expr` has kind `*`.

## Other recursion-schemes

All of our examples so far have used `cata`. 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 the `ana` recursion-scheme:

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

The Data.Functor.Foldable module provides many more.

## Contributing

Contributions and bug reports are welcome!

## 5.2.2.1

• Fix build issue regarding `Setup.hs`. See #120.

## 5.2.2

• More Mendler-style recursion-schemes: `mpara`, `mzygo`, `mana`, `mapo`, and `mfutu`.
• `makeBaseFunctor` no longer generates warnings when combined with DerivingStrategies.

## 5.2.1 [2020.10.04]

• Allow building with `template-haskell-2.17.0.0` (GHC 9.0).

## 5.2

• Add instances for `Tree` (from `containers`)
• Generalize the type of `makeBaseFunctor(With)`, such that it can take also `Dec`. This way you may supply context for `Recursive` and `Corecursive` instances.
• Depend on `data-fix` package for fixed point types.

## 5.1.3 [2019.04.26]

• Support `th-abstraction-0.3.0.0` or later.

## 5.1.2

• Make the `Generic`-based instances to also support data constructors with zero arguments (and datatypes with zero constructors).

## 5.1.1.1

• Invalid release

## 5.1.1

• Add `cotransverse`
• Add `Generic` based default implementation to `embed` and `project`. `Recursive` and `Corecursive` can be `DeriveAnyClass`-derived now, if you write the base functor by hand.

## 5.1

• Export gfutu
• `distGHisto`, `ghisto`, and `gchrono` now use `Cofree (Base t)`
• `distGFutu`, `gfutu`, and `gchrono` now use `Free (Base t)`
• Add `hoist`, `hoistMu` and `hoistNu`
• Add `transverse` and `cataA`

## 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.
• Add `Recursive` and `Corecursive Natural` instances, with `Base Natural = Maybe`.

## 5.0.1

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

## 5

• Renamed `Foldable` to `Recursive` and `Unfoldable` to `Corecursive`. With `Foldable` in `Prelude` in GHC 7.10+, having a needlessly conflicting name seemed silly.
• Use `Eq1`, `Ord1`, `Show1`, `Read1` to derive `Fix`, `Nu` and `Mu` `Eq`, `Ord` `Show` and `Read` instances
• Remove `Prim` data family. `ListF` as a new name for `Prim [a]`, with plenty of instances, e.g. `Traversable`.
• Export `unfix`
• Add chronomorphisms: `chrono` and `gchrono`.
• Add `distGApoT`

## 4.1.2

• Support for `free` 4.12.1

## 4.1.1

• Support for GHC 7.10
• Fixed `para`.

## 4.1

• Support for GHC 7.7+’s generalized `Typeable`.
• Faster `gapo` and `para` by exploiting sharing.

## 4.0

• Compatibility with `comonad` and `free` version 4.0

## 3.0

• Compatibility with `transformers` 0.3
• Resolved deprecation warnings caused by changes to `Data.Typeable`