I've started using Haskell lately, and defined this seemingly simple function:
f 0 = 1
f x = x * f x - 1
However, it results in this:
GHCi, version 8.2.1: http://www.haskell.org/ghc/ :? for help
Prelude> f 0 = 1
Prelude> f x = x * f x - 1
Prelude> f 10
*** Exception: stack overflow
Prelude>
Your factorial seems innocent, but it isn't. It's parsed like this:
f 0 = 1
f x = x * (f x) - 1
What happens if we use f 1?
f 1 = 1 * (f 1) - 1 = 1 * (1 * (f 1) - 1) - 1
= 1 * (1 * (1 * (f 1) - 1) - 1) - 1
= 1 * (1 * (1 * (1 * (f 1) - 1) - 1) - 1) - 1
= ...
I'm going to stop here. This will never end. It will build up a stack of parentheses, and at some the whole tower collapses and you end up with a stack overflow.
You have to use parentheses:
f 0 = 1
f x = x * f (x - 1)
Now we get the correct result:
f 1 = 1 * f (1 - 1) = 1 * f 0 = 1 * 1 = 1
Keep in mind that this works only in an implementation file. In GHCi you have to use multi-line mode or a semicolon:
ghci> f 0 = 1; f x = x * f (x - 1)
ghci> -- or
ghci> :{
ghci| f 0 = 0
ghci| f x = x * f (x - 1)
ghci| :}
Otherwise later definitions will shadow earlier ones. Note that your prompt might differ.
f. It proceeds line by line sof x = x * f x - 1is a functionfshadowing the previous definition off(f 0 = 1). To enter a multiline block, enter:{. Close that block with:}.f xusingf x. Your definition means thatf x = x * (f x) - 1, notx * (f (x - 1))x * f x - 1gets parsed as(x * f x) - 1. Did you meanx * f (x - 1)?