4

I'm learning tail recursion and I'm having some difficulties in determining whether my function is tail recursive or not (mainly on functions which I use another function).

I've implemented the two following functions but I'm not so sure if they are tail recursive or not.

The first one is a function to concatenate two lists.

conca list [] = list
conca [] result = result
conca (h:t) result = conca (init (h:t)) ( last(h:t):result ) 

concatenate::[a]->[a]->[a]
concatenate list1 list2 = conca list1 list2

The computations in the function are processed before the recursive call, but its using last and init, which aren't tail recursive ( I checked their definition in http://ww2.cs.mu.oz.au/172/Haskell/tourofprelude.html )

The second function is to remove the first occurrence of a given number in a given list.

invert [] result = result
invert (h:t) result = invert t (h:result)

remov n [] aux result = invert result []
remov n (h:t) aux result
        | aux==1 = remov n t 1 (h:result)
        | n==h = remov n t 1 (result)
        | otherwise = remov n t 0 (h:result)

remove n list = remov n list 0 []

The parameter aux (which can assume 0 or 1 as value) is being used to mark if the ocurrence has been removed or not.

In the remove function while the partial result is passed down through the recursive call the list is being inverted, upon the end the list is without the first ocurrence but upside-down, thus it have to be inverted to be returned as a result.

user1493813
  • 981
  • 1
  • 8
  • 16
  • 2
    You're presumably learning about tail recursion for efficiency reasons. Have you read up [this question](http://stackoverflow.com/questions/13042353/does-haskell-have-tail-recursive-optimization) yet? It goes into why tail call optimisation isn't quite what you need. Also, on the topic of efficiency, using `init` and `last` a lot is a disaster! – AndrewC Dec 19 '12 at 02:45
  • Just read it. In this case i'm not looking for efficiency but just implementing some basic functions using tail recursion, as practice. So, instead of using init and last what would be a better option? – user1493813 Dec 19 '12 at 03:06
  • 1
    `init` and `last` both traverse the entire list, so are _O(n)_ operations. `head` and `tail` are _O(1)_, so much better to use, but you can get those by pattern matching. The standard definition of `(++)` says `(x:xs) ++ ys = x:(xs ++ ys)`, a classic efficient non-tail recursive lazy function which produces the head of the result immediately. – AndrewC Dec 19 '12 at 03:29

1 Answers1

6
conca (h:t) result = conca (init (h:t)) ( last(h:t):result )

is a tail call, but last(h:t):result starts life as an unevaluated thunk, so it's a (hand-wavy) bit like these nested function calls are on the stack still.

conca pattern matches on its first argument so init will be evaluated in the recursive call.

conca is non-strict in its second argument, so those thunks won't get evaluated while applying the recursive call of conca.

remov is tail recursive, yes, but....

Use True and False instead of 0 and 1 to make your code clearer:

remov n [] found result = invert result []
remov n (h:t) found result
        | found = remov n t True (h:result)
        | n==h = remov n t True (result)
        | otherwise = remov n t False (h:result)

remove n list = remov n list False []

This would be better not passing around so much data, reducing the copying of n and using two functions instead of a single function that tests a boolean parameter:

remove' n list = seek list [] where
   seek []     result = invert result []
   seek (h:t) result | h == n    = got t result
                     | otherwise = seek t (h:result)
   got []    result = invert result []
   got (h:t) result = got t (h:result)

but got a result just calculates reverse result ++ a, so you could write

remove'' n list = seek list [] where
   seek []     result = invert result []
   seek (h:t) result | h == n    = invert result [] ++ t
                     | otherwise = seek t (h:result)

However, it all seems rather a lot of effort, and still traverses the list twice. Why not go for a non-tail call:

removeFast n [] = []
removeFast n (h:t) | h == n = t
                   | otherwise = h:removeFast n t

This has the benefit of producing its first element straight away rather than running the whole list, and short cuts to return t without further computation once it's found the element to remove. Try racing length (removeFast 1 [1..100000]) against length (remove 1 [1..100000]) (vary the number of zeros according to your processor speed).

If you want to make a more efficient tail recursive conca, you could use the trick from remove:

conc this result = prepend (invert this []) result

prepend [] result = result
prepend (h:t) result = prepend t (h:result)

As before, you're traversing this twice, once inverting it, the other prepending it, but that's still a linear algorithm, and much better than using init and last for each element, which is quadratic.

AndrewC
  • 32,300
  • 7
  • 79
  • 115
  • thanks for the advice! So, in order to make conca tail recursive will i have to make the second argument strict? – user1493813 Dec 19 '12 at 03:14
  • @user1493813 My main point is tail recursion isn't very important. Check out the speed gains I got with `removeFast` which isn't tail recursive, but instead performs minimal operations. – AndrewC Dec 19 '12 at 03:24
  • your answer is now making me question why on earth did my teacher demanded of us to implement these functions with tail recursion in our homework, this is the reason why i got to implement concatenation, because if i don't I'll get a 0. – user1493813 Dec 19 '12 at 03:35
  • @user1493813 It's already tail recursive, but that's different to making efficient use of the stack. – AndrewC Dec 19 '12 at 03:36
  • @user1493813 Don't be discouraged; your tail recursion skills are crucial in most languages - strict functional compilers and good imperative compilers can optimise tail recursive functions into loops. – AndrewC Dec 19 '12 at 03:39
  • huh? my concatenation is tail recursive? i thought it wasn't according to your post. – user1493813 Dec 19 '12 at 03:39
  • @user1493813 I said "is a tail call, but..." – AndrewC Dec 19 '12 at 03:42
  • thanks for the attention and patience, I'm reading again the post you indicated to understand the efficiency of tail recursion and non-tail recursion. – user1493813 Dec 19 '12 at 03:49
  • @user1493813 I've added a tail recursive but faster `conc`. You should notice that my `remove''` isn't tail recursive, because `++` isn't. `remove'` is tail recursive. – AndrewC Dec 19 '12 at 03:53