将元素添加到列表末尾而无需遍历整个列表（haskell）

Question

Haskell中有没有一种方法可以将元素添加到列表的末尾而不必遍历整个列表？

例如，如果我有列表，[1,2,3,4]并想在末尾添加5，例如：[1,2,3,4,5]

据我了解，++运算符将不得不对整个列表进行解散，这效率很低。

谢谢！

Answer 1

正如@Jubobs在评论中已经说过- 不，您不能，但这不一定（总是）效率低下。

在开始一些解释之前，我想提醒您唐纳德·努斯（Donald Knuth）和他所说的一切邪恶的根源是过早的优化。因此，请尝试编写正确的程序，稍后再担心性能-当您遇到瓶颈时（请确保haskell具有检测瓶颈的良好工具！）。

例

假设您有一个无限的列表，[1..]并且想要追加，5您仍然可以在haskell中执行此操作。让我们启动ghci并观察一些事情。

> ghci
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Prelude> let a = [1..] ++[5] :: [Int]

首先，我们注意到- let绑定工作缓慢，并且尚未打印任何内容。我们甚至可以进一步检查检查的程度a。

Prelude> :sprint a
a = _

尽管诸如此类的表达式filter (== 5) a永远不会终止，但我们仍然可以使用list来做有用的事情a。

Prelude> let b = map (+2) a
Prelude> take 10 b
[3,4,5,6,7,8,9,10,11,12]

并a再次检查。

Prelude> :sprint a
a = 1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : _

我们只评估了前十个元素。

结束这个例子，我们看到-即使您“附加” 5它可能永远不会被使用-因此，“附加”将永远不会发生，这比我们便宜的“附加”情况更有效。

（请注意，这种懒惰会引入一些内存开销，这可能会导致麻烦，请参阅“ 懒惰评估-空间泄漏”以获取更多信息。）

备择方案

正如其他人已经说过的-使用好的旧列表还有其他选择。

1. 如果您经常追加列表，但将列表用作“累加器”，则最好在返回之前先添加列表并反转列表。这是O(1)对于所有(:)的操作和O(n)用于反向-比较O(n)用于每个(++)步骤。

2. 使用不同的数据结构：

   • 差异列表：您可以在其中了解更多有关haskell的信息，以便从那里进行报价：

     像清单这样的差异清单等效[1,2,3]于函数\xs -> [1,2,3] ++ xs。一个正常的空列表是[]，而一个空的差异列表是函数\xs -> [] ++ xs。

   • Sequence：来自Data.Sequence，它支持有效的prepend/- 运算append以及对边缘元素的查找。

     $ stack ghci --package containers
     Prelude> import Data.Sequence
     Prelude Data.Sequence> let a = fromList [1..4] :: Seq Int
     Prelude Data.Sequence> (a |> 5)
     fromList [1,2,3,4,5]
     Prelude Data.Sequence> 0 <| (a |> 5)
     fromList [0,1,2,3,4,5]
     

   • Set-虽然不像列表那样排序，但是仍然支持有效（O(log n)）插入，但仅允许唯一插入。

     $ stack ghci --package containers
     Prelude> import Data.Set
     Prelude Data.Set> let a = fromList [1..4] :: Set Int
     Prelude Data.Set> insert 5 a
     fromList [1,2,3,4,5]
     Prelude Data.Set> insert 4 a
     fromList [1,2,3,4]