Идиоматический эффективный апплет Haskell? - PullRequest
34 голосов
/ 04 марта 2011

Список и оператор минусов (:) очень распространены в 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

Ответы [ 12 ]

1 голос
/ 04 марта 2011

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

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

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

map = mapOnto []

Мы можем аналогичное определение для других основанных на фолдере функций, таких как 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)
1 голос
/ 04 марта 2011

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

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

[править] Как идея @ Дана, я переписал 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
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...