惯用的高效 Haskell 附加? [英] Idiomatic efficient Haskell append?

问题描述

List 和 cons 运算符 (:) 在 Haskell 中非常常见.缺点是我们的朋友.但有时我想添加到列表的末尾.

List and the cons operator (:) are very common in Haskell. Cons is our friend. But sometimes I want to add to the end of a list instead.

xs `append` x = xs ++ [x]

遗憾的是，这不是实现它的有效方式.

This, sadly, is not an efficient way to implement it.

我用 Haskell 写了 Pascal's triangle，但我不得不使用 ++ [x] 反成语:

I wrote up Pascal's triangle in Haskell, but I had to use the ++ [x] anti-idiom:

ptri = [1] : mkptri ptri
mkptri (row:rows) = newRow : mkptri rows
    where newRow = zipWith (+) row (0:row) ++ [1]

恕我直言，这是一个可爱的可读的帕斯卡三角形等等，但反成语让我感到厌烦.有人可以向我解释(并且，理想情况下，为我指出一个很好的教程)关于您想要有效地附加到末尾的情况的惯用数据结构是什么?我希望这种数据结构及其方法具有近乎列表的美感.或者，或者，向我解释为什么这种反成语实际上对这种情况并没有那么糟糕(如果你认为是这样的话).

imho, this is a lovely readable Pascal's triangle and all, but the anti-idiom irks me. Can someone explain to me (and, ideally, point me to a good tutorial) on what the idiomatic data structure is for cases where you want to append to the end efficiently? I'm hoping for near-list-like beauty in this data structure and its methods. Or, alternately, explain to me why this anti-idiom is actually not that bad for this case (if you believe such to be the case).

[edit] 我最喜欢的答案是 Data.Sequence，它确实具有类似列表的美感".不知道我对所需的操作严格性有何看法.随时欢迎进一步的建议和不同的想法.

[edit] The answer I like the best is Data.Sequence, which does indeed have "near-list-like beauty." Not sure how I feel about the required strictness of operations. Further suggestions and different ideas are always welcome.

import Data.Sequence ((|>), (<|), zipWith, singleton)
import Prelude hiding (zipWith)

ptri = singleton 1 : mkptri ptri

mkptri (seq:seqs) = newRow : mkptri seqs
    where newRow = zipWith (+) seq (0 <| seq) |> 1

现在我们只需要 List 作为一个类，以便其他结构可以使用它的方法，如 zipWith ，而无需对 Prelude 隐藏或限定它.:P

Now we just need List to be a class, so that other structures can use its methods like zipWith without hiding it from Prelude, or qualifying it. :P

推荐答案

Standard Sequence 有 O(1) 用于从两端"和 O(log(min(n1,n2)) 的加法) 用于一般连接:

Standard Sequence has O(1) for addition from 'both ends' and O(log(min(n1,n2))) for general concatenation:

http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Sequence.html

与列表的不同之处在于Sequence是严格的

The difference from lists though is that Sequence is strict

这篇关于惯用的高效 Haskell 附加?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！