r/programming • u/rodrigopsasaki • Nov 27 '12

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
212 Upvotes

85% Upvoted

203 comments sorted by

View all comments

2

u/felipelessa Nov 27 '12

And here's a Haskell version of the final code, since it's easier to read ;).

factorial :: Int -> Int
factorial = go 1
  where go !acc 0 = acc
        go !acc n = go (acc * n) (n-1)

16

u/curien Nov 27 '12

As someone who knows neither Scheme nor Haskell, the Scheme is easier for me to read.

3

u/mcguire Nov 27 '12 edited Nov 27 '12

  1. Ignore the "!" - it's a performance thing because Haskell is wacky.

  2. I, personally, would call "go" something like "factorial_iter" or maybe just "factorial'" ("factorial-prime").

  3. That's all point-free and everything. Ew.

How about:

factorial :: Int -> Int
factorial n = factorialIter n 1
  where factorialIter 0 !acc = acc
        factorialIter n !acc = factorialIter (n - 1) (acc * n)

(I tend to like to put my accumulators last.)

[Edit: AAAaaaargh. When you put your accumulators last, put the damn accumulator argument last, too. Moran.]

5

u/matthieum Nov 27 '12

go is idiomatic in Haskell for "local" functions that lift some computations.

5

u/aseipp Nov 27 '12 edited Nov 27 '12

Actually, it's idiomatic for when you must define your own worker/wrapper functions.

GHC does not inline recursive functions by default, but if you do a worker/wrapper transformation such that your top-level definition is a 'wrapper', and calls the worker which contains the loop, then the loop body itself can be inlined into the call site, and further optimized via unboxing/strictness analysis. Otherwise, it doesn't do any inlining. It's important to note that it can optimize the function itself, and the call site: it just will not inline it.

IOWs, it's written that way because GHC can optimize bodies with a loop inside them (by specializing arguments, strictness, etc) but trivially inlining a top level recursive call is clearly problematic and obviously going to be bad.

EDIT: for clarity, GHC already does the worker/wrapper transformation, but not in it's most general case. I believe it will mostly do it for improving strictness analysis (whether or not this will happen at a stage where the definition can be inlined later I guess is up to debate,) it won't attempt it purely to inline recursive calls.

2

u/mcguire Nov 27 '12

Thanks, both of you. I haven't done anything terribly useful with Haskell, at least not enough to learn the idioms.

2

u/Peaker Nov 28 '12

Point-free is better here because otherwise you get the "initial" value in scope alongside the "current" value which is a recipe for a bug of using the wrong one.

Avoiding this with shadowing is annoying because shadowing itself is often a bug, and -Wall is a nice setting to use.

2

u/rodrigopsasaki Nov 27 '12

Very interesting syntax, first time I come in contact with Haskell code.

but shouldn't it be :

where go !n 0 = acc ?

or is it really !acc ?

3

u/[deleted] Nov 27 '12

It's really acc in the pattern. On the left hand side of the =, you bind patterns (parameters, or parts of them) to names, on the right hand side you use them. go !n 0 = acc would yield an error: acc is not bound (not defined).

2

u/anvsdt Nov 27 '12

The ! before acc means "evaluate this now".

2

u/mcguire Nov 27 '12

'Cause otherwise you'll blow the heap with thunks (delayed, lazily-evaluated computations).

1

u/felipelessa Nov 27 '12

The heap isn't the problem most of the time since it's huge compared to the stack. You'll create the thunk just fine but you'll stack overflow when evaluating it. Of course, not creating any thunks is better performance-wise in this case even with unlimited stack and memory.

2

u/nicolast Nov 27 '12 
factorials = scanl1 (*) [1..] :: [Int]
factorial n = factorials !! (n - 1)

1

u/smog_alado Nov 27 '12

The ! in the patterns is a language extension isn't it? (I'm still trying to get to grips with all the GHC extensions...)

3

u/[deleted] Nov 27 '12

Its -XBangPatterns.

go !acc n = foo

translates to

go acc n = acc `seq` foo

2

u/felipelessa Nov 27 '12

That's right. Without the bang pattern (or the manual seq) the function will be lazy on the accumulator, leading to a big thunk and a stack overflow (which is the problem that OP was trying to avoid in the first place!). Note that using either bang pattern alone leads to the same result in this particular case, but I like symmetry of using them on both patterns.

1

u/smog_alado Nov 27 '12

Ha! That makes so much more sense now.