OCaml and Haskell are both statically typed functional programming languages. Their type systems are very similar. They both have function types, algebraic data types, higher-order types (list of things, maybe/option types, tuple types). They both support type variants of the Hindley-Milner type inference algorithm.
But in Haskell, one often heralded featured is that data types can be "infinite". Haskellers love to showcase this clever one-linear which produces the fibonacci numbers:
fibs :: [Int] fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
A school-yard argument
Everyone has, at some point during their childhood, found themselves in a contest to name the largest number. It starts off with perhaps a hundred, or a thousand, then a million, a billion, a trillion. Perhaps the savvy youngsters will know about quadrilions or quintillions.
But at some point, we run out of words for numbers. The argument continues with one-upsmanship. Your friend names a numbers. You tack "plus one" onto the end. They come back with "plus two". Maybe some multiplication gets thrown in there ("a trillion trillion!").
The game gets boring pretty quickly, though. You decide it's time to pull out your trump card: infinity!
Surely, you've won. No one can top infinity. It's bigger than the biggest number, after all. Your friend will have to forfeit.
Or so you think. But they comeright back at you: "Infinity plus one!"read more...
The Specs for
We suppose the existence of a function called
Halt. It takes one parameter: a function, we will call f, that takes 0 parameters. Then
true if the call to
f() ever returns a value, and
f() loops infinitely.
An important part of this assumption is that
Halt(f) must always return
false regardless of your choice of
f. It must not itself loop.