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

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 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]

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

иначе можно было бы избежать конкатенации, просто используя бесконечные списки:

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

Ответ 8

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

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

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

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

Ответ 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)

Ответ 10

Я написал пример подхода @geekosaur ShowS. Вы можете увидеть много примеров ShowS в prelude.

ptri = []:mkptri ptri
mkptri (xs:ys) = (newRow xs []) : mkptri ys

newRow :: [Int] -> [Int] -> [Int]
newRow xs = listS (zipWith (+) xs (0:xs)) . (1:)

listS :: [a] -> [a] -> [a]
listS [] = id
listS (x:xs) = (x:) . listS xs

[править] Как идея @Dan, я переписал newRow с zipWithS.

newRow :: [Int] -> [Int] -> [Int]
newRow xs = zipWithS (+) xs (0:xs) . (1:)

zipWithS :: (a -> b -> c) -> [a] -> [b] -> [c] -> [c]
zipWithS z (a:as) (b:bs) xs =  z a b : zipWithS z as bs xs
zipWithS _ _ _ xs = xs

Ответ 11

Если вы ищете решение общего назначения, то как насчет этого:

mapOnto :: [b] -> (a -> b) -> [a] -> [b]
mapOnto bs f = foldr ((:).f) bs

Это дает простое альтернативное определение для отображения:

map = mapOnto []

Мы можем аналогичное определение для других функций, основанных на foldr, таких как zipWith:

zipOntoWith :: [c] -> (a -> b -> c) -> [a] -> [b] -> [c]
zipOntoWith cs f = foldr step (const cs)
  where step x g [] = cs
        step x g (y:ys) = f x y : g ys

Снова получив zipWith и zip довольно легко:

zipWith = zipOntoWith []
zip = zipWith (\a b -> (a,b))

Теперь, если мы используем эти функции общего назначения, ваша реализация становится довольно легко:

ptri :: (Num a) => [[a]]
ptri = [] : map mkptri ptri
  where mkptri xs = zipOntoWith [1] (+) xs (0:xs)

Ответ 12

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

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]