Ackermann function (Haskell)
From LiteratePrograms
The Ackermann function or Ackermann-Péter function is defined recursively for non-negative integers m and n as follows:
- 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}"/>
In the theory of computation, the Ackermann function is a simple example of a recursive function that is not primitively recursive. Note that this function grows very quickly -- even A(4, 3) cannot be feasibly computed on ordinary computers.
The Ackermann function is ideal for representation in Haskell and an excellent use of its pattern matching facility and specifically n+k pattern matching.
The Ackermann function could also have been easily implemented in Haskell with conditional code or guards.
With pattern matching you create multiple definitions of a function and specify patterns for the arguments. Haskell will use its pattern matching facility to invoke the first definition that matches the pattern.
Haskell has extremely little Housekeeping code
<<ackermann.hs>>= module Ackermann where
The case that bottoms out the recursion uses simple pattern matching to match the first argument to 0 and binds the second argument to the variable n
<<ackermann.hs>>= ackermann 0 n = n+1
The case that reduces the first argument with primitive recursion uses what is called n+k pattern matching, in an n+k pattern match n>= k. In this case the n+k pattern is m+1 therefore the first argument or m must be greater than 1.
The case that uses multiple recursion also uses n+k pattern matching. Therefore both the first and second argument must be greater than 1
<<ackermann.hs>>= ackermann (m+1) 0 = ackermann m 1 ackermann (m+1) (n+1) = ackermann m (ackermann (m+1) n)
Finally a "catch all" definition that use the underscore, which are wildcards that don't even bother to bind the values. Note the pattern matching goes in order, so something like this should always be last. This is nice approach for eeking out every bit of efficiency because catching invalid negative arguments doesn't affect performance of algorithm with valid arguments. I suppose I could have spit out an error message, but I simply return 0.
<<ackermann.hs>>= ackermann _ _ = 0