[Haskell-cafe] tail recursion
wren ng thornton
wren at freegeek.org
Tue Apr 7 07:11:55 EDT 2009
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
More information about the Haskell-Cafe
mailing list