惯用高效哈斯克尔追加？ [英] Idiomatic efficient Haskell append?

问题描述

名单和利弊运营商（：）是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帕斯卡三角，但我不得不使用 ++ [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).

我最喜欢的答案是 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

现在我们只需要清单是一个类，让其他结构可以使用它的方法，如 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

推荐答案

标准序为O（1）除由两头和O（日志（分（N1，N2）））为一般级联

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

<一个href=\"http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Sequence.html\">http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Sequence.html

从列表的区别是，虽然序是严格

The difference from lists though is that Sequence is strict

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