向列表中添加一个元素，然后反转它

Question

我 learning Haskell，正在尝试理解列表。

根据研究，要将元素添加到列表中，您通常会这样做：

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

但引用 :

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.

代码:

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

输出:

[56,43,23,69]

问题:

根据引用的答案，我编写的代码是否正确？
我想更好地理解术语，我可以说我正在向 list 的 head 添加元素吗？据我了解，每个新元素都是第一个元素，当我写 head newNumbers.

Answer 1

您需要区分链表数据结构和您使用链表实现的任何类似列表的数据类型。您可以做两件事来修改链表：将新头添加到列表中，并删除当前头（如果链表不为空）。

引用中提到的用例对于队列数据类型很常见：您可以在一端添加并从另一端删除。您可以使用 two 链接列表来实现这一点，方法是向一个列表添加新元素并从另一个列表中删除元素。队列的实现会根据需要进行反转，以确保您永远不会在删除之前插入的所有其他项目之前删除项目。

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))

（我们不关心处理从空队列中移除的好方法；只是将其称为错误并保留它。）

添加到传入列表和从传出列表中删除很容易。棘手的部分是我们如何以及何时将项目从传入列表传输到传出列表。我们只在传出列表为空时这样做，当它为空时，我们立即传输 entire 传入列表，并在过程中反转它。换句话说，我们正在反向构建传入列表，但只在必要时才反转它，而不是在添加每一个项目之后。

摊销分析可以用来表明，虽然 reverse 可能很慢，但它通过前面和后面的快速操作的数量来平衡。

向列表中添加一个元素，然后反转它

Adding an element to a list and then reverse it

reverse

haskell

list