recursion-schemes
Representing common recursion patterns as higher-order functions
http://github.com/ekmett/recursion-schemes/
Version on this page: | 5.1.3@rev:2 |
LTS Haskell 22.43: | 5.2.3 |
Stackage Nightly 2024-12-04: | 5.2.3 |
Latest on Hackage: | 5.2.3 |
recursion-schemes-5.1.3@sha256:cbcf3c36e1733a83fb8cda305bde2de18a2fbab53692e3301263964def430107,3523
Module documentation for 5.1.3
- Data
- Data.Functor
recursion-schemes
What is a recursion scheme?
Many recursive functions share the same structure, e.g. pattern-match on the input and, depending on the data constructor, either recur on a smaller input or terminate the recursion with the base case. Another one: start with a seed value, use it to produce the first element of an infinite list, and recur on a modified seed in order to produce the rest of the list. Such a structure is called a recursion scheme.
Benefits
Clearer
Each recursion scheme has a unique name, such as “fold” and “unfold”; or, if you prefer the fancy names, “catamorphism” and “anamorphism”. If you program with others, it can be useful to have names to refer to those recursion patterns, so you can discuss which type of recursion is the most appropriate for the problem at hand. Even if you program alone, having names with which to clearly label those different solutions can help to structure your thoughts while writing recursive functions.
This library lists the most common recursion schemes, and also provides an implementation corresponding to each one. The idea is that a recursive function may be broken into two parts: the part which is the same in all the recursive functions which follow a given recursion scheme, and the part which is different in each function. Our implementation performs the recursive, common part, and takes as input a function which performs the non-recursive, unique part.
If you use those implementations instead of making explicit recursive calls, your code will simultaneously become clearer (to those who are familiar with recursion schemes) and more obscure (to those who aren’t). Obviously, if one knows how to read and understand recursive code but does not know what e.g. para
means, then the version which uses para
will look needlessly obfuscated compared to the version they already know how to read. But if one is familiar with para
, then seeing this familiar name will instantly clarify that this is a spine-based function, like Map.insert
, which allocates new nodes along a spine but leaves the rest of the nodes untouched. This is a very useful starting point, guiding the reader to look for the logic which decides which sub-trees to drill through and which sub-trees to leave untouched. In contrast, with the general-recursion version, the reader has no such starting point and must thus read through the entire function (or guess based on the function’s name) before they can infer that kind of big picture information.
Faster
Using recursion schemes can guide you towards optimizations. When multiple functions are composed, Haskellers often use equational reasoning in order to rearrange those compositions into equivalent compositions which compute the same result, but do so in a different, possibly more efficient manner. When the recursive and non-recursive portions of a function are written separately, more equations become available, as they have more pieces to work with. The paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire has a lot more details on that subject.
Safer
Using recursion schemes can help you to avoid accidentally writing infinite or non-productive loops. For example, when producing an infinite list, it would be a mistake to look at the result of the recursive call in order to decide which element to produce as the head of the list, because that recursive call will itself look at its recursive call, etc., and so the information will never be returned. With ana
, the non-recursive function you need to provide as input intentionally does not have access to the result of the recursive call, so you cannot make that mistake.
Composable
Many recursion schemes can be implemented in terms of each other. So if you notice that the non-recursive functions you provide themselves seem to share a common pattern, you might be accidentally reimplementing an existing recursion scheme which already has those common parts builtin; or maybe you have stumbled upon a new recursion scheme which does not yet have a name, and which you may want to implement yourself.
One way to implement such a custom recursion scheme is to combine the features of existing recursion schemes. For example, a “paramorphism” gives the non-recursive function access to the original sub-trees, a “zygomorphism” gives that function access to auxiliary results computed from those sub-trees, and so the combined “zygomorphic paramorphism” gives that function access to both the original sub-trees and the auxiliary results. In order to construct such combinations, most of our recursion schemes come in a generalized variant, e.g. gzygo
, and in a “distributive law transformer” variant, e.g. distZygoT
. Just like monad transformers, distributive law transformers can be combined into stacks, and like monad transformers, the order in which you combine the layers determines how the layers interact with each other. Apply a generalized recursion scheme to a stack of distributive laws in order to obtain a recursion scheme which has both the features of the generalized recursion scheme and those of the distributive laws.
Contributing
Contributions and bug reports are welcome!
Please feel free to contact us by opening a github issue or by hopping onto the #haskell IRC channel on irc.freenode.net.
Changes
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 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)
- Add
hoist
,hoistMu
andhoistNu
- Add
transverse
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.
- Add
Recursive
andCorecursive Natural
instances, withBase Natural = Maybe
.
5.0.1
- Add
Data.Functor.Foldable.TH
module, which provides derivation of base functors via Template Haskell.
5
- Renamed
Foldable
toRecursive
andUnfoldable
toCorecursive
. WithFoldable
inPrelude
in GHC 7.10+, having a needlessly conflicting name seemed silly. - Add support for GHC-8.0.1
- Use
Eq1
,Ord1
,Show1
,Read1
to deriveFix
,Nu
andMu
Eq
,Ord
Show
andRead
instances - Remove
Prim
data family.ListF
as a new name forPrim [a]
, with plenty of instances, e.g.Traversable
. - Export
unfix
- Add chronomorphisms:
chrono
andgchrono
. - 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
andpara
by exploiting sharing.
4.0
- Compatibility with
comonad
andfree
version 4.0
3.0
- Compatibility with
transformers
0.3 - Resolved deprecation warnings caused by changes to
Data.Typeable