2

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>
schuelermine
  • 1,958
  • 2
  • 17
  • 31
  • 3
    GHCi doesn't realize you are defining _one_ function `f`. It proceeds line by line so `f x = x * f x - 1` is a function `f` shadowing the previous definition of `f` (`f 0 = 1`). To enter a multiline block, enter `:{`. Close that block with `:}`. – Alec Oct 05 '17 at 16:12
  • 1
    https://stackoverflow.com/questions/8443035/multi-line-commands-in-ghci – Alec Oct 05 '17 at 16:12
  • 3
    You're function definition also defines `f x` using `f x`. Your definition means that `f x = x * (f x) - 1`, not `x * (f (x - 1))` – Edward Minnix Oct 05 '17 at 16:15
  • @Alec It didn't work: Prelude> :{ Prelude| f 0 = 1 Prelude| f x = x * f x - 1 Prelude| :} Prelude> f 10 *** Exception: stack overflow Prelude> – schuelermine Oct 05 '17 at 16:16
  • 2
    @MarkNeu Sure it didn't, but not for the same reason. Note that `x * f x - 1` gets parsed as `(x * f x) - 1`. Did you mean `x * f (x - 1)`? – Alec Oct 05 '17 at 16:18

1 Answers1

9

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.

Zeta
  • 103,620
  • 13
  • 194
  • 236