Adding an element to a list and then reverse it

Question

I'm learning Haskell, and attempting to understand lists.

From researching, to add an element to a list, you would normally do:

let numbers = [4,8,15,16,23,42] 
numbers ++ [56]

but to quote this answer:

If you need to do this, there is usually a better way to structure your algorithm. For example, you can build your list in reverse order (adding elements at the beginning) and only call reverse at the end.

Code:

let numbers = [23,43,56]
let newNumbers = 69:numbers
reverse newNumbers

Output:

[56,43,23,69]

Question:

Is the code I've written correct according to the quoted answer?
I want to understand the terminology a little better, can I say I'm adding elements to the head of the list? From my understanding, every new element would be the first element, and the value returned when I write head newNumbers.

It doesn't mean "call `reverse` after you prepend each itme"; that's no better than using `++` to append the item. Instead, it means that if you want to build up a list by adding new items to the end, you should put them at the beginning instead, and call reverse once it is time to consume the entire list. — chepner, Nov 15 '18 at 16:27
@chepner - So in this case, if I wanted to just add `69` to the list, have I done it correctly in accordance with the quote? Which also makes me wonder, how would you add more than one element to the beginning of the list? Guess that's another exercise to try out. — , Nov 15 '18 at 16:30
It really depends on how you intend to use the list. See my answer for an example. — chepner, Nov 15 '18 at 16:55
There are times you must definitelly append a list to another list and to make it worse you may need to append new lists to the resulting one several thousands of times. This will be a very costly operation. To overcome this cost difference list data structures are used. [This question is all about that](https://stackoverflow.com/q/13879260/4543207) — Redu, Nov 15 '18 at 17:06
This isn't really a question about haskell, it's a question about a stackoverflow question. Adding the tag makes it harder to find questions about haskell. It's also not a question about "add" — codeshot, Nov 16 '18 at 08:56
@codeshot - The question is about `Haskell`. Before asking my question, I did my research, and came across that answer, and decided to try for myself. I did what was recommended by SO. I asked a question to make sure I was going in the right direction. I'm new to `Haskell`, and languages change, so I wanted to make sure I'm on the right track. One of the topics introduced in LHftGG is `List`. Coming from an OOP background, I asked myself how I can `add`/`remove` items from a list. Questions about other SO questions happen all time. It's about researching and learning. — , Nov 16 '18 at 17:46

chepner · Accepted Answer · 2018-11-15T17:00:29.147

You need to distinguish between the linked list data structure and whatever list-like data type you are implementing with the linked list. You can do exactly two things to modify a linked list: prepend a new head to the list, and remove the current head (if the linked list isn't empty).

The use case the quote talks about is common for a queue data type: you can add to one end and remove from the other end. You can implement this using two linked lists, by adding new elements to one list and removing elements from the other. The implementation of the queue takes care of reversing as necessary to ensure that you never remove an item before every other item inserted previously is removed.

data Queue a = Queue [a] [a]

-- Put new elements on the incoming list.
addToQueue :: a -> Queue a -> Queue a
addToQueue x (Queue incoming outgoing) = Queue (x:incoming) outgoing

-- Take elements from the outgoing list, whose elements are stored
-- in the reverse order that they were added to the incoming list
-- previously.
removeFromQueue :: Queue a -> (a, Queue a)
removeFromQueue (Queue [] []) = error "Cannot remove from empty queue"
removeFromQueue (Queue incoming (x:xs)) = (x, Queue incoming xs)
removeFromQueue (Queue incoming []) = removeFromQueue (Queue [] (reverse incoming))

(We're not concerned with good ways to deal with removing from an empty queue here; just call it an error and leave it at that.)

Adding to the incoming list and removing from the outgoing list is easy. The tricky part is how and when we transfer items from the incoming list to the outgoing list. We only do so when the outgoing list is empty, and when it is, we transfer the entire incoming list at once, reversing it in the process. In other words, we're building up the incoming list in reverse, but only ever reverse it when necessary, not after each and every single item is added.

Amortized analysis can be used to show that although reverse could be slow, it is balanced by the number of fast operations that precede and can follow it.

The sharp-eyed reader might notice I left out a `peek :: Queue a -> a` function. Ensuring that a series of `peek` operations doesn't have to repeatedly scan through the incoming list when the outgoing list is empty complicates the other two functions in ways I didn't want to deal with for this answer. The solution is to ensure that neither `addToQueue` nor `removeFromQueue` can return a queue whose outgoing list is empty. — chepner, Nov 15 '18 at 17:06
The amortized analysis of *that* queue only holds up when the queue is used ephemerally. In a persistent application, the rotations need to be done somewhat differently. — dfeuer, Nov 15 '18 at 21:28

Adding an element to a list and then reverse it

1 Answers1