[Haskell-cafe] tail recursion

[wren ng thornton]

Daryoush Mehrtash wrote:
> Is the call to "go" in the following code considered as tail recursion?
> 
> data DList a = DLNode (DList a) a (DList a)
> 
> mkDList :: [a] -> DList a
> 
> mkDList [] = error "must have at least one element"
> mkDList xs = let (first,last) = go last xs first
>              in  first
> 
>   where go :: DList a -> [a] -> DList a -> (DList a, DList a)
>         go prev []     next = (next,prev)
>         go prev (x:xs) next = let this        = DLNode prev x rest
>                                   (rest,last) = go this xs next
>                               in  (this,last)


No. For @go _ (_:_) _@ the tail expression is @(this,last)@ and so the 
tail call is to @(,)@. Consider this general transformation[1]:

     go prev []     next = (next,prev)
     go prev (x:xs) next =
         case DLNode prev x rest of this ->
         case go this xs next    of (rest,last) ->
             (this,last)

Let binding is ignored when determining tail-callingness, and case 
evaluation only contributes in as far as allowing multiple tails.


[1] Which isn't laziness-preserving and so will break on your recursive 
let binding. It's a valid transformation for non-recursive let bindings, 
though, provided the appropriate strictness analysis.

-- 
Live well,
~wren