Haskell: problems fully defining factorial in Continuation Passing Style

Question

I've been trying to understad Functional Programming, Haskell and Continuation Passing Style in one big blob and my structured/OOP background is giving me a hard time.

According to this I understand the following should be a correct definition of factorial in CPS-style:

factorial n = fact n id where id = \x -> x
    fact 0 cont = cont n
    fact (n+1) cont = fact n * (n + 1)

but I'm not sure about the "* (n + 1)" part at the end - is that correct?

Answer 1

It's not quite correct (and doesn't compile for me); the value n+1 is right but it isn't used in quite the correct way. Maybe you meant to use an operator section?

factorial n' = fact n' id
 where
  id = \x -> x
  fact 0 cont = cont 1
  fact (n+1) cont = fact n (cont . (* (n+1)))

This is identical to (but more obtuse than) the following

factorial n' = fact n' id
 where
  id = \x -> x
  fact 0 cont = cont 1
  fact (n+1) cont = fact n (\ret -> cont (ret * (n+1)) )

There are a few things I would change here. First, id is a standard function so you don't need to redefine it. Secondly, these examples use "n+k patterns", which IIRC are no longer available by default in GHC. Instead of an "n+k pattern", you can use a normal pattern variable. Note that I used 1 for the base case; this is simpler to reason about if you're counting down from n, and the continuation function should be applied at each step within the computation (you'd dropped it from the induction step). With these in mind, you can write

factorial n' = fact n' id
 where
  fact 0 cont = cont 1
  fact n cont = fact (n-1) (cont . (* n))

which I would consider more or less idiomatic.

Edit: I personally don't like n+k patterns, but I thought I'd take a bit of time to explain them. I find it easier to follow if you think of mathematical induction with a base case and an induction step. The base case is fact 0 .... You then define the other values by proceeding from the base step: "for any fact n k, determine fact (n+1) k by this relation." This is different from how I think of normal pattern variables, that is top-down instead of bottom-up as here, but I think it explains the motivation and why some people like the style.

The reason I don't like n+k patterns is simply because I find the definitions more cluttered, but YMMV.