1

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

Improve this question
7
  • 3
    As mentioned in the comments on your previous question, tail recursion is usually not helpful in Haskell. Here, as often, it has numerous problems: it's less lazy and it reverses the list. Commented Jan 29, 2023 at 22:02
  • 1
    It is a bit bizarre to focus on tail recursion, since that often has not much added value in Haskell. Commented Jan 29, 2023 at 22:04
  • mm, I see. So this is a general result from using it in haskell and should be expected (without manually reversing it again)? Commented Jan 29, 2023 at 22:04
  • Yeah, let's just say I probably should have learned it before in a previous course and am trying to catch up with it without switching back to a different language. Commented Jan 29, 2023 at 22:05
  • @floxam: this is not specific to Haskell no, it is just how you wrote your program: each element on the list, you push onto the second list as first parameter, so at the end, the second list is the first list in reverse. Commented Jan 29, 2023 at 22:10

2 Answers 2

Reset to default
2

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 = reverse (x:acc)
appendt x (h : t) acc = appendt x t (h : acc)

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

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

Thanks, got it. On a related note - would the point about tail recursion not having much added value in haskell also apply to if I wanted to do this using foldl? Would it run into the same issue (reversed list) and thus make foldr a better choice?
@floxam: using foldl will (of course depending on how you implement it), result in the same issue if you prepend to the accumulator. Appending will produce a non-reversed list, but will take quadratic time.
trying to do it with foldr right now. Looking at the right associativity of what foldr does...I'm thinking a way to do it would be to have list be the 2nd argument of the f parameter (3rd argument to foldr), have our accumulator be the singleton list with the value we are trying to put at the end of the list, and our function basically just a lambda that does what the list constructor does.
@floxam: but foldr is not tail recursive, this is equivalent to your first approach.
@floxam That's the exact reason, yep.
|
2

Prepending to the accumulator is efficient, but produces the result backwards. Appending produces the right result, but is inefficient. In this answer, I'd like to show a standard-ish trick to directly (i.e. without reverseing afterwards) produce the right result efficiently. The trick is to make the accumulator be a function which modifies a list (e.g. by prepending to it). So:

appendt x [] acc = acc [x]
appendt x (h:t) acc = appendt x t (acc . (h:))

Before, you would pass [] as your initial accumulator; now, you pass id. You could, if you wanted, hide that detail:

appendt = go id where
    go acc x [] = acc [x]
    go acc x (h:t) = go (acc . (h:)) x t

Try it in ghci:

> appendt 4 [1,2,3]
[1,2,3,4]
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.