Maths - Expressions

Here are some concepts which are used in functional programming (see: Meijer, Erik; Fokkinga, Maarten; Paterson, Ross. "Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire") and these concepts are also used in category theory.

Notation Functional Programming Term Category Theory Term Meaning (from here)
  banana catamorphism tears down a structure level by level
[( )] lense anamorphism builds up a structure level by level
  envelope hylomorpism builds up and tears down a virtual structure
  barbed wire paramorphism tears down a structure with primitive recursion

Catamorphism and Anamorphism

If we start with an algebra that has a binary operation (S,S)->S and, instead of supplying interal values we supply a symbolic value to represent a variable or unknown, we might build up a free algebra. free algebra

 

catamorphism anamorphism

Catamorphism (banana)

Reduces the data structure to a required value.

Functional Programming Examples:

Category:

Tree is a initial object in the category of F-algebras

Anamorphism (Lenses)

Upwards morphism - Builds an invocation tree as an explicit data structure.

Functional Programming Examples:

A notation for ana(f) found in the literature is [(f)]. The brackets used are known as lens brackets.

In programming 'lenses' can be used as the functional equivalent of a 'reference' and they allow a functional (non-mutable) data structure to be used like an imperative (mutable) data structure. They do this by duplicating the data rather than using references to the same stucture. This allows functional programs to act on imperitive structures like databases in a purely functional way. Unlike other ways of doing this lenses are composable, that is, we can nest these structures to any debth (subject to memory constraints because of this duplication).

Laws

get-put P(S,G (S))=S
put-get G(P(S,V))=V

Where:

Haskell Example

case class Lense[A,B] {
  g: A => B
  s: (B,A) => A
| {
DEF get (a:A):B=g(a)
DEF set(b:B,a:A): A=s(b,a)

References

Hylomorphism

Composition of an anamorphism and a catamorphism. Invocation tree is isomorphic to a function which processes lists.

Example Monoid

free monoid = list

 

monoid expression

 

Fold Left fold left
Fold Right fold right

 

 

So the fold operation takes a list and a monoid and returns a value

fold

Googles MapReduce software framework.

Example Field

free field = tree?

free field

 


metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

flag flag flag flag flag flag The Princeton Companion to Mathematics - This is a big book that attempts to give a wide overview of the whole of mathematics, inevitably there are many things missing, but it gives a good insight into the history, concepts, branches, theorems and wider perspective of mathematics. It is well written and, if you are interested in maths, this is the type of book where you can open a page at random and find something interesting to read. To some extent it can be used as a reference book, although it doesn't have tables of formula for trig functions and so on, but where it is most useful is when you want to read about various topics to find out which topics are interesting and relevant to you.

 

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.