Идиоматический эффективный апплет Haskell?

Question

Список и оператор минусов (:) очень распространены в Haskell.Минусы это наш друг.Но иногда я хочу добавить в конец списка.

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

К сожалению, это не эффективный способ его реализации.

Я написалup Треугольник Паскаля в Хаскеле, но мне пришлось использовать ++ [x] анти-идиому:

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

imho, это прекрасный читабельный треугольник Паскаля и все, но анти-идиома раздражает меняМожет ли кто-нибудь объяснить мне (и, в идеале, указать мне хороший учебник), какова идиоматическая структура данных для случаев, когда вы хотите эффективно добавить к концу?Я надеюсь на красоту, похожую на список, в этой структуре данных и ее методах.Или, альтернативно, объясните мне, почему этот анти-идиома на самом деле не так уж плох для этого случая (если вы считаете, что это так).

---

[править] Ответ, который мне нравится больше всего, -Data.Sequence, которая действительно обладает "красотой, подобной почти списку".Не уверен, как я отношусь к требуемой строгости операций.Всегда приветствуются дальнейшие предложения и различные идеи.

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

Answer 1

Имейте в виду, что то, что выглядит плохой асимптотикой, на самом деле может и не быть, потому что вы работаете на ленивом языке.На строгом языке добавление в конец связанного списка таким способом всегда будет O (n).В ленивом языке это O (n), только если вы действительно переходите к концу списка, и в этом случае вы все равно потратили бы O (n) усилий.Так что во многих случаях лень спасает вас.

Это не гарантия ... например, k добавлений, за которыми следует обход, все равно будет выполняться в O (nk), где это могло быть O (n +)к).Но это немного меняет картину.Думая о выполнении отдельных операций с точки зрения их асимптотической сложности, когда результат немедленно принуждается, не всегда дает правильный ответ в конце.

Answer 2

Стандарт Sequence имеет O (1) для сложения с «обоих концов» и O (log (min (n1, n2))) для общей конкатенации:

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

Отличие от списков в том, что Sequence строго

Answer 3

Что-то вроде этой явной рекурсии избегает вашего добавления "анти-идиома". Хотя я не думаю, что это так ясно, как ваш пример.

ptri = []:mkptri ptri
mkptri (xs:ys) = pZip xs (0:xs) : mkptri ys
    where pZip (x:xs) (y:ys) = x+y : pZip xs ys
          pZip [] _ = [1]

Answer 4

В вашем коде для треугольника Паскаля ++ [x] на самом деле не является проблемой.Так как вы все равно должны создать новый список в левой части ++, ваш алгоритм по своей сути является квадратичным;Вы не можете сделать это асимптотически быстрее, просто избегая ++.

Кроме того, в этом конкретном случае, когда вы компилируете -O2, правила слияния списков GHC (должны) исключают копию списка, которую ++ обычно создает,Это потому, что zipWith - хороший производитель, а ++ - хороший потребитель в своем первом аргументе.Вы можете прочитать об этих оптимизациях в Руководстве пользователя GHC .

Answer 5

Если вы просто хотите дешево добавить (concat) и snoc (cons справа), список Hughes, также называемый DList для Hackage, проще всего реализовать. Если вы хотите знать, как они работают, посмотрите на первую статью Энди Гилла и Грэма Хаттона «Рабочий упаковщик», оригинальная статья Джона Хьюза, похоже, не в сети. Как уже говорили другие, ShowS - это специализированный список Hughes / DList.

JoinList - это немного больше работы для реализации. Это двоичное дерево, но с API списков - concat и snoc дешевы, и вы можете разумно отобразить его: DList на Hackage имеет экземпляр functor, но я утверждаю, что его не должно быть - экземпляр functor должен преобразовываться в и из обычный список. Если вам нужен JoinList, вам нужно будет создать свой собственный - тот, что на Hackage, мой, и он не эффективен и плохо написан.

Data.Sequence имеет эффективные минусы и снок, и подходит для других операций - взятия, отбрасывания и т. Д., Для которых JoinList работает медленно. Поскольку реализация Data.Sequence во внутреннем дереве пальца должна уравновешивать дерево, добавление - это больше работы, чем его эквивалент JoinList. На практике, поскольку Data.Sequence лучше написана, я ожидаю, что она все равно превосходит мой JoinList для добавления.

Answer 6

В зависимости от вашего варианта использования может быть полезен метод ShowS (добавление через композицию функций).

Answer 7

другой способ вообще избежать конкатенации, просто используя бесконечные списки:

ptri = zipWith take [0,1..] ptri'
  where ptri' = iterate stepRow $ repeat 0
        stepRow row = 1 : zipWith (+) row (tail row)

Answer 8

Я бы не стал называть ваш код "антиидомным". Часто яснее, лучше , даже если это означает пожертвовать несколькими тактами.

И в вашем конкретном случае добавление в конце на самом деле не меняет сложность big-O time ! Оценивая выражение

zipWith (+) xs (0:xs) ++ [1]

займет время, пропорциональное length xs, и никакая причудливая структура данных последовательности не изменит этого. Во всяком случае, только постоянный фактор будет затронут.

Answer 9

У Криса Окасаки есть дизайн очереди, которая решает эту проблему. Смотрите страницу 15 его диссертации http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Возможно, вам придется немного адаптировать код, но некоторое использование реверса и сохранение двух частей списка позволяет вам работать более эффективно в среднем .

Кроме того, кто-то поместил некоторый код списка в считыватель монад с эффективными операциями. Я признаю, я действительно не следовал этому, но я думал, что мог понять это, если бы я сконцентрировался. Оказывается, это был Дуглас М. Оклер в выпуске Monad Reader 17 http://themonadreader.files.wordpress.com/2011/01/issue17.pdf

---

Я понял, что приведенный выше ответ не имеет прямого отношения к вопросу. Итак, для хихиканья, вот мой рекурсивный ответ. Не стесняйтесь разрывать его на части - это не красиво.

import Data.List 

ptri = [1] : mkptri ptri

mkptri :: [[Int]] -> [[Int]]
mkptri (xs:ys) =  mkptri' xs : mkptri ys

mkptri' :: [Int] -> [Int]
mkptri' xs = 1 : mkptri'' xs

mkptri'' :: [Int] -> [Int]
mkptri'' [x]        = [x]
mkptri'' (x:y:rest) = (x + y):mkptri'' (y:rest)

Answer 10

Вы можете представить список как функцию для построения списка из []

list1, list2 :: [Integer] -> [Integer]
list1 = \xs -> 1 : 2 : 3 : xs
list2 = \xs -> 4 : 5 : 6 : xs

Затем вы можете легко добавлять списки и добавлять их в любой конец.

list1 . list2 $ [] -> [1,2,3,4,5,6]
list2 . list1 $ [] -> [4,5,6,1,2,3]
(7:) . list1 . (8:) . list2 $ [9] -> [7,1,2,3,8,4,5,6,9]

Вы можете переписать zipWith, чтобы вернуть эти частичные списки:

zipWith' _ [] _ = id
zipWith' _ _ [] = id
zipWith' f (x:xs) (y:ys) = (f x y :) . zipWith' f xs ys

А теперь вы можете написать ptri как:

ptri = [] : mkptri ptri
mkptri (xs:yss) = newRow : mkptri yss
    where newRow = zipWith' (+) xs (0:xs) [1]

Если продолжить, приведем однострочник, который более симметричен:

ptri = ([] : ) . map ($ []) . iterate (\x -> zipWith' (+) (x [0]) (0 : x [])) $ (1:)

Или это еще проще:

ptri = [] : iterate (\x -> 1 : zipWith' (+) (tail x) x [1]) [1]

Или без zipWith '(mapAccumR находится в Data.List):

ptri = [] : iterate (uncurry (:) . mapAccumR (\x x' -> (x', x+x')) 0) [1]