0
data Tree = Leaf Int | Branch Tree Tree

sumt (Leaf i) acc = i + acc
sumt (Branch l r) acc = sumt l (sumt r acc)

sumt is in tail position, but it's also in the accumulator. I lean towards no because it has to evaluate the inner call to sumt (using a call stack), but I can see why it could be tail-recursive because the last function call is sumt. fibsumt is clearly tail-recursive even though the acc function creates a deep call-stack.

fib 0 = 0
fib 1 = 1
fib n = fib (n - 2) + fib (n - 1)

fibsumt 0 acc = acc
fibsumt n acc = fibsumt (n - 1) (acc + (fib n))

Is sumt classified as a tail-recursive function?

eMMe
  • 569
  • 5
  • 16
Karl
  • 427
  • 4
  • 15
  • I don’t think so, since the result of the inner call to `fibsumt` must then be added to the accumulator. – Regis Kuckaertz Apr 10 '18 at 06:45
  • 1
    … things are different in Haskell though, see https://stackoverflow.com/questions/13042353/does-haskell-have-tail-recursive-optimization – Regis Kuckaertz Apr 10 '18 at 06:46
  • I probably should have used a strict language for this because laziness makes this all a bit more difficult. – Karl Apr 10 '18 at 06:51
  • Yeah, in a strict one that would not qualify because of the outer add... but you could move it inside the inner recursive call, couldn’t you? Where is that `b` coming from? – Regis Kuckaertz Apr 10 '18 at 06:54
  • @RegisKuckaertz That answer is a good read but I don't think it quite applies here since `sumt` is strict in both of its arguments. – Benjamin Hodgson Apr 10 '18 at 09:48
  • @BenjaminHodgson I would have thought that because the recursive call does not inspect `acc`, then the compiler would box the value. Is that reasoning incorrect? – Regis Kuckaertz Apr 10 '18 at 10:29
  • 2
    “Strict” in this context is quite a specific term: _how much of the input is forced when evaluating the output to WHNF?_ It should be clear that `(+)` (on `Int`s) is strict in both of its arguments, so `sumt` (which calls `(+)`) is also strict. GHC _may_ implement the recursive calls using the trampoline-esque evaluation strategy described in the linked answer but with optimisations on it won’t. (Disclaimer: I haven’t looked at the generated Core so I might be talking outta my ass!) – Benjamin Hodgson Apr 10 '18 at 10:35
  • haha, no that's very useful, thank you. – Regis Kuckaertz Apr 10 '18 at 10:52

0 Answers0