Список и оператор cons (:) очень распространены в Haskell. Минусы - наш друг. Но иногда я хочу добавить в конец списка.
xs `append` x = xs ++ [x]
Это, к сожалению, не является эффективным способом его реализации.
Я написал Треугольник Pascal в Haskell, но мне пришлось использовать :
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
Стандарт Sequence имеет O (1) для добавления из "обоих концов" и O (log (min (n1, n2))) для общей конкатенации:
http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Sequence.html
Отличие от списков состоит в том, что Sequence является строгим
Имейте в виду, что то, что выглядит плохой асимптотикой, на самом деле не может быть, потому что вы работаете на ленивом языке. Строго говоря, добавление к концу связанного списка таким образом всегда будет O (n). В ленивом языке это O (n), только если вы действительно переходите к концу списка, и в этом случае вы бы потратили O (n) в любом случае. Поэтому во многих случаях лень спасает вас.
Это не гарантия... например, k добавлений, за которыми следует обход, все равно будет работать в O (nk), где он мог бы быть O (n + k). Но это несколько меняет картину. Размышление о выполнении отдельных операций с точки зрения их асимптотической сложности, когда результат немедленно принудительно не всегда дает вам правильный ответ в конце.
Что-то вроде этой явной рекурсии позволяет избежать добавления "анти-идиомы". Хотя, я не думаю, что это так же ясно, как ваш пример.
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]
В вашем коде для Pascal Triangle ++ [x] на самом деле не проблема. Поскольку в любом случае вам нужно создать новый список в левой части файла ++, ваш алгоритм по своей сути квадратичен; вы не можете сделать это асимптотически быстрее, просто избегая ++.
Кроме того, в этом конкретном случае, когда вы компилируете -O2, правила слияния списков GHC (должны) исключают копию списка, который обычно создавал ++. Это потому, что zipWith является хорошим производителем, а ++ - хорошим потребителем в нем первого аргумента. Вы можете прочитать об этих оптимизациях в Руководство пользователя GHC.
В зависимости от вашего варианта использования может оказаться полезным метод ShowS (добавление через композицию функции).
Если вы просто хотите, чтобы дешевый 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 для добавления.
иначе можно было бы избежать конкатенации, просто используя бесконечные списки:
ptri = zipWith take [0,1..] ptri'
where ptri' = iterate stepRow $ repeat 0
stepRow row = 1 : zipWith (+) row (tail row)
Я бы не стал называть ваш код "анти-idomatic". Зачастую лучше становится лучше, даже если это означает пожертвовать несколькими тактами.
И в вашем конкретном случае добавление в конце на самом деле не меняет сложность времени большого О! Оценивая выражение
zipWith (+) xs (0:xs) ++ [1]
будет занимать пропорциональное время length xs, и никакая структура данных причудливой последовательности не изменится. Во всяком случае, будет затронут только постоянный фактор.
У Криса Окасаки есть проект для очереди, которая решает эту проблему. См. Стр. 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)
Я написал пример подхода @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
Если вы ищете решение общего назначения, то как насчет этого:
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)
Вы можете представлять список как функцию для создания списка из []
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]