User:Ezrakilty/Draft of Anamorphism as pattern of function definition

From Wikipedia, the free encyclopedia
Jump to: navigation, search
For other uses, see Anamorphosis (disambiguation).

In functional programming, an anamorphism is a function defined according to a certain pattern, which builds up results of an type one constructor at a time from a seed. 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. 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 anamorphism on lists builds a (potentially infinite) list from a seed value and a construction function.

In terms of a predicate finished :: b -> Bool and a function step :: b -> (a,b), a list anamorphism f has the following definition (in Haskell syntax):

f x | finished x = []
      | otherwise = a : f y
           where (a, y) = step x

Such a function takes a seed value, x and checks whether it is "finished" in which case it simply returns the empty list. If not, it uses the step operation to generate a "next" list element and a new seed; it generates the rest of the list by recursing with the new seed.

This pattern can be abstracted into a higher-order function definition, as followss:

-- The type signature of 'ana':
ana :: (b->(a,b)) -> (b->Bool)-> b -> [a]   
-- Its definition:
ana step finished x = f x
  where
      f x | finished x = []
            | otherwise = a : f y
        where (a, y) = step x

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 [\!(f)\!]. The brackets used are known as lens brackets, after which anamorphisms are sometimes referred to as lenses.

See also[edit]

References[edit]

  1. ^ Meijer, Erik; Fokkinga, Maarten; Paterson, Ross (1991). "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire". 

External links[edit]