Home > database >  tail recursion to add element to end of list in Haskell
tail recursion to add element to end of list in Haskell

Time:01-30

I wrote this simple function to append an element to the end of a list recursively:

--takes arguments x and lst and appends x to the end of list
append1::a->[a]->[a]
append1 x [] = x:[] 
append1 x (h:t) = h:append1 x t

It works fine. To practice writing tail recursive functions (which I was not aware of until a few days ago), I tried writing it the following way.

--tail recursion
appendt::a->[a]->[a]->[a]
appendt x [] acc = x:acc
appendt x (h:t) acc =  appendt x t (h:acc) 

It outputs the list I want in reverse. Why this happens I can sort of grasp but it is still hurting my head.

  1. Why exactly does this happen? Is a general thing that happens when iterating over lists like this?
  2. is there any way it can be changed (while still using tail recursion/not using ) to output the list in the correct order?

Note: This is just for practice

CodePudding user response:

Why exactly does this happen? Is a general thing that happens when iterating over lists like this?

You use an accumulator that you each time prepend, so you use:

   appendt 1 [4,2,5] []
=  appendt 1 (4:(2:(5:[]))) []
-> appendt 1 (2:(5:[])) (4:[])
-> appendt 1 (5:[]) (2:(4:[]))
-> appendt 1 [] (5:(2:(4:[])))
=  appendt 1 [] [5,2,4]
-> 1:[5,2,4]
= [1,5,2,4]

Each item you thus encounter in the second parameter (the first list), you "push" on the second list (third parameter), so that means it acts as some sort of stack where the order is of course in reverse.

is there any way it can be changed (while still using tail recursion/not using ) to output the list in the correct order?

Reversing the output, so:

appendt :: a -> [a] -> [a] -> [a]
appendt x [] acc = x : reverse acc
appendt x (h : t) acc = appendt x t (h : acc)

but as said before, tail recursion has not much added value in Haskell.

  • Related