Odtnhj

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:

1. Is the code I've written correct according to the quoted answer?


2. 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.

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.