Difference between revisions of "Peano numbers"
(→Peano number types: Improved lay-out (the <haskell> tag does not handle indentation nicely))
(→Peano number values: update link to code.haskell.org)
|Line 18:||Line 18:|
See an [http://
See an [http://.haskell.org/htam/src/Number/PeanoNumber.hs example implementation].
=== Peano number types ===
=== Peano number types ===
Revision as of 12:07, 24 October 2014
Peano numbers are a simple way of representing the natural numbers using only a zero value and a successor function. In Haskell it is easy to create a type of Peano number values, but since unary representation is inefficient, they are more often used to do type arithmetic due to their simplicity.
Peano number values
data Peano = Zero | Succ Peano
Succ are values (constructors).
Zero has type
Succ has type
Peano -> Peano. The natural number zero is represented by
Zero, one by
Succ Zero, two by
Succ (Succ Zero) and so forth.
Here's a simple addition function:
add Zero b = b add (Succ a) b = Succ (add a b)
See an example implementation.
Peano number types
data Zero data Succ a
Succ are types.
Zero has kind
Succ has kind
* -> *. The natural numbers are represented by types (of kind
Succ (Succ Zero) etc.
Arithmetic can be done using fundeps:
class Add a b ab | a b -> ab instance Add Zero b b instance (Add a b ab) => Add (Succ a) b (Succ ab)
Note that classes express relationships between types, rather than functions from type to type. Accordingly, with the instance declarations above one can add another fundep to the class declaration to get subtraction for free:
class Add a b ab | a b -> ab, a ab -> b instance Add Zero b b instance (Add a b ab) => Add (Succ a) b (Succ ab)
See type arithmetic for other functions and encodings.
The lazy nature of Peano numbers rehabilitates the use of list functions which count list elements. As described in Things to avoid one should not write
length xs == 0
length traverses the whole list and may take a long time doing so, although after you have seen only one, it is obvious that the list is not empty.
The above expression can be simply replaced by
null, but with Peano numbers you achieve the same
genericLength xs == Zero -- or genericLength xs == (0::Peano)
length xs == length ys
is harder to make lazy without Peano numbers.
With them (and an appropriate
Num instance) this becomes rather simple, because
genericLength xs == (genericLength ys :: Peano)
traverses only as many list nodes as are in the shorter list.
Lazy Peano numbers can also be used within "Tying the Knot" techniques. There is a package for determining the right order for solving equations, where an equation is only solved if only one of its variables is still indeterminate.
See example implementations: