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