User:Ezrakilty/Draft of Anamorphism as generic function
In functional programming, an anamorphism is a kind of generic function which can (co)recursively construct a result of a certain type and which is parameterized by functions that determining what the next single step of the construction is. The term comes from Greek ἀνά (upwards) + morphism (from Greek μορφή, or form, shape) and the concept has its grounding in Category theory.
The concept of anamorphism generalizes the list-producing unfold functions to arbitrary algebraic data types that can be described as final coalgebras. In fact, the terms 'anamorphism' and "unfold" (as a noun) are often used interchangeably. Anamorphisms, which are co-recursive, are dual to catamorphisms, which are recursive, just as unfolds are dual to folds.
Examples
[edit]Anamorphisms on Lists
[edit]An unfold on lists would build a (potentially infinite) list from a seed value. Typically, the unfold takes a seed value x
, a one-place operation unspool
that yields a pairs of such items, and a predicate finished
which determines when to finish the list (if ever). In the action of unfold, the first application of unspool
, to the seed x
, would yield unspool x = (y,z)
. The list defined by the unfold would then begin with y
and be followed with the (potentially infinite) list that unfolds from the second term, z
, with the same operations. So if unspool z = (u,v)
, then the list will begin y:u:...
, where ...
is the result of unfolding v with r, and so on.
A Haskell definition of an unfold, or anamorphism for lists, called ana
, is as follows:
-- The type signature of 'ana': ana :: (b->(a,b)) -> (b->Bool)-> b -> [a] -- Its definition: ana unspool finished x = if finished x then [] else a : ana unspool finished y where (a,y) = unspool x
(Here finished
and unspool
are parameters of the function, like x
.) We can now implement quite general functions using ana.
Anamorphisms on other data structures
[edit]An anamorphism can be defined for any recursive type, according to a generic pattern. For example, the unfold for the tree data structure
data Tree a = Leaf a | Branch Tree a Tree
is as follows
ana :: (b->Either a (b,a,b)) -> b -> Tree a ana unspool x = case unspool x of Left a -> Leaf a Right (l,x,r) -> Branch (ana unspool l) x (ana unspool r)
History
[edit]One of the first publications to introduce the notion of an anamorphism in the context of programming was the paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire,[1] by Erik Meijer et al., which was in the context of the Squiggol programming language.
Applications
[edit]Functions like zip
and iterate
are examples of anamorphisms. zip
takes a pair of lists, say ['a','b','c'] and [1,2,3] and returns a list of pairs [('a',1),('b',2),('c',3)]. Iterate
takes a thing, x, and a function, f, from such things to such things, and returns the infinite list that comes from repeated application of f, i.e. the list [x, (f x), (f (f x)), (f (f (f x))), ...].
zip (a:as) (b:bs) = if (as==[]) || (bs ==[]) -- || means 'or'
then [(a,b)]
else (a,b):(zip as bs)
iterate f x = x:(iterate f (fx))
To prove this, we can implement both using our generic unfold, ana
, using a simple recursive routine:
zip2 = ana g p where p (as,bs) = (as==[]) || (bs ==[]) g ((a:as), (b:bs)) = ((a,b),(as,bs))
iterate2 f = ana (\a->(a,f a)) (\x->False)
Ruby comes with an explicit unfold operation; so, for example:
10.unfold { |n| n-1 unless n == 1 }.inspect => [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
10.class.unfold(&:superclass).inspect => [Fixnum, Integer, Numeric, Object]
In a language like Haskell, by contrast, even the abstract functions fold
, unfold
and ana
are merely defined terms, as we have seen from the definitions given above.
Anamorphisms in category theory
[edit]In category theory, anamorphisms are the categorical dual of catamorphisms.
Notation
[edit]A notation for ana f found in the literature is . The brackets used are known as lens brackets, after which anamorphisms are sometimes referred to as lenses.
See also
[edit]References
[edit]- ^ Meijer, Erik (1991). "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire".
{{cite web}}
: Unknown parameter|coauthors=
ignored (|author=
suggested) (help)