If I have an expression, which is partitially evaluable, is it a good idea to avoid tail-recursion?

Question

Consider an haskell-expression like the following: (Trivial example, don't tell me what the obvious way is! ;)

toBits :: Integral a => a -> [Bool]
toBits 0 = []
toBits n = x : toBits m where
 (m,y) = n `divMod` 2
  x    = y /= 0

Because this function is not tail-recursive, one could also write:

toBits :: Integral a => a -> [Bool]
toBits = toBits' [] where
  toBits' l 0 = l
  toBits' l n = toBits (x : l) m where
    (m,y) = n `divMod` 2
     x    = y /= 0

(I hope there is nothing wron whithin this expression)

What I want to ask is, which one of these solutions is better. The advantage of the first one is, that it can be evaluated partitially very easy (because Haskell stops at the first : not needed.), but the second solution is (obviously) tail-recursive, but in my opinion it needs to be completely evaluated until you can get something out.

The background for this is my Brainfuck parser, (see my optimization question), which is implemented very uggly (various reverse instructions... ooh), but can be implemented easily in the first - let's call it "semi-tail-recursion" way.

Answer 1

I think you've got it all just right. The first form is in general better because useful output can be obtained from it before it has completed computation. That means that if 'toBits' is used in another computation the compiler can likely combine them and the list that is the output of 'toBits' may never exist at all, or perhaps just one cons cell at a time. Nice that the first version is also more clear to read!

Answer 2

In Haskell, your first choice would typically be preferred (I would say "always," but you're always wrong when you use that word). The accumulator pattern is appropriate for when the output can not be consumed incrementally (e.g. incrementing a counter).

Answer 3

Let me rename the second version and fix a few typos so that you can test the functions.

toBits :: Integral a => a -> [Bool]
toBits 0 = []
toBits n = x : toBits m where
 (m,y) = n `divMod` 2
 x     = y /= 0

toBits2 :: Integral a => a -> [Bool]
toBits2 = toBits' [] where
  toBits' l 0 = l
  toBits' l n = toBits' (x : l) m where
    (m,y) = n `divMod` 2
    x     = y /= 0

These functions don't actually compute the same thing; the first one produces a list starting with the least significant bit, while the second one starts with the most significant bit. In other words toBits2 = reverse . toBits, and in fact reverse can be implemented with exactly the same kind of accumulator that you use in toBits2.

If you want a list starting from the least significant bit, toBits is good Haskell style. It won't produce a stack overflow because the recursive call is contained inside the (:) constructor which is lazy. (Also, you can't cause a thunk buildup in the argument of toBits by forcing the value of a late element of the result list early, because the argument needs to be evaluated in the first case toBits 0 = [] to determine whether the list is empty.)

If you want a list starting from the most significant bit, either writing toBits2 directly or defining toBits and using reverse . toBits is acceptable. I would probably prefer the latter since it's easier to understand in my opinion and you don't have to worry about whether your reimplementation of reverse will cause a stack overflow.