From LiteratePrograms

Jump to: navigation, search

This is the sandbox, an article where contributors can experiment with editing and the code viewing and downloading feature. To learn how to use our markup and extensions, visit LiteratePrograms:How to write an article. Please don't remove this notice.

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

module Ackermann

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 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 (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 _ _ = 0

Unlambda test

These functions are straight from the Unlambda page:


Define a pair of functions

<<some pair>>=

This (untested) Unlambda program shows extraction of the first element by just applying it to i (thus printing 1). In addition it prints a newline.

`r``car some pair i

Empty chunk test

The following chunk is intentionally empty.


There should be only whitespace between "Hello" and "world":

Hello empty world

Deactivating stdio synchronization in C++

If you are using streams in C++, you can improve their performance a little bit by using instruction from the code below. However, be careful because you'd better not mix stdio with streams after such modification.

int main ()
Download code