10

dlist パッケージDListには、多数のインスタンスを持つデータ型が含まれていますが、Foldableorは含まれていませんTraversable。私の考えでは、これらは最も「リストに似た」型クラスの 2 つです。DListこれらのクラスのインスタンスではないパフォーマンス上の理由はありますか?

また、パッケージはと を実装しますが、他の折りたたみ機能は実装foldrしません。unfoldr

4

2 に答える 2

23

代わりに考慮すべき 1 つの選択肢DListは、Church でエンコードされたリストを使用することです。アイデアは、リストに対して a を実行する方法を知っている不透明な値としてリストを表すことですfoldr。これには、RankNTypes拡張機能を使用する必要があります。

{-# LANGUAGE RankNTypes #-}

import Prelude 
import Control.Applicative
import Data.Foldable (Foldable)
import qualified Data.Foldable as F
import Data.Traversable (Traversable)
import qualified Data.Traversable as T

-- | Laws:
--
-- > runList xs cons nil == xs
-- > runList (fromList xs) f z == foldr f z xs
-- > foldr f z (toList xs) == runList xs f z
newtype ChurchList a = 
    ChurchList { runList :: forall r. (a -> r -> r) -> r -> r }

-- | Make a 'ChurchList' out of a regular list.
fromList :: [a] -> ChurchList a
fromList xs = ChurchList $ \k z -> foldr k z xs

-- | Turn a 'ChurchList' into a regular list.
toList :: ChurchList a -> [a]
toList xs = runList xs (:) []

-- | We can construct an empty 'ChurchList' without using a @[]@.
nil :: ChurchList a 
nil = ChurchList $ \_ z -> z

-- | The 'ChurchList' counterpart to '(:)'.  Unlike 'DList', whose
-- implementation uses the regular list type, 'ChurchList' doesn't
-- rely on it at all.
cons :: a -> ChurchList a -> ChurchList a
cons x xs = ChurchList $ \k z -> k x (runList xs k z)

-- | Append two 'ChurchList's.  This runs in O(1) time.  Note that
-- there is no need to materialize the lists as @[a]@.
append :: ChurchList a -> ChurchList a -> ChurchList a
append xs ys = ChurchList $ \k z -> runList xs k (runList ys k z)

-- | Map over a 'ChurchList'.  No need to materialize the list.
instance Functor ChurchList where
    fmap f xs = ChurchList $ \k z -> runList xs (\x xs' -> k (f x) xs') z

-- | The 'Foldable' instance is trivial, given the 'ChurchList' law.
instance Foldable ChurchList where
    foldr f z xs = runList xs f z

instance Traversable ChurchList where
    traverse f xs = runList xs step (pure nil)
        where step x rest = cons <$> f x <*> rest

これの欠点は、 a の効率的なtail操作がないことです — a のChurchList折り畳みChurchListは安価ですが、テールを繰り返すのはコストがかかります...

于 2013-03-23T23:38:56.243 に答える
12

DList aは反変の位置にある の newtype ラッパー[a] -> [a]であるため、 orを実装することも、直接実装することもできません。それらを実装する唯一の方法は、通常のリストとの間で変換することです (実装を参照)。これは、差分リストのパフォーマンス上の利点を無効にします。aFoldableTraversableFunctorfoldr

于 2013-03-23T17:34:30.953 に答える