12

一部の標準 Haskell ライブラリは、このようなデータ型を定義していますか?

data ListWithEnd e a = Cons a (ListWithEnd e a)
                     | End e

それは、指定された型の値を持つ終端要素を持つリストですか?

ListWithEnd ()は無限ストリームに同型で[]ありListWithEnd Void、無限ストリームに同型です。または、別の見方をすると、ListWithEnd e a非常に近いConduitM () a Identity e..

4

1 に答える 1

5

ListWithEnd次のように定義できます。

import Control.Monad.Free

type LWE a e = Free ((,) a) e

私たちは一般的に、抽象的または一般的な表現によって定型文の全体的な削減が得られることを期待しています。この表現が私たちに何を提供するか見てみましょう。

いずれにせよ、コンス ケースのパターン シノニムを定義します。

{-# LANGUAGE PatternSynonyms #-}

pattern x :> xs = Free (x, xs)
infixr 5 :>

終了要素をマップ、折り畳み、トラバースできます。

fmap (+1) (0 :> Pure 0) == (0 :> Pure 1)
traverse print (0 :> Pure 1) -- prints 1

インスタンスはApplicative非常にきちんとした連結を提供します:

xs = 1 :> 2 :> Pure 10
ys = 3 :> 4 :> Pure 20

xs *> ys          == 1 :> 2 :> 3 :> 4 :> Pure 20 -- use right end
xs <* ys          == 1 :> 2 :> 3 :> 4 :> Pure 10 -- use left end
(+) <$> xs <*> ys == 1 :> 2 :> 3 :> 4 :> Pure 30 -- combine ends

少し曲がりくねった場合、リスト要素をマップできます。

import Data.Bifunctor -- included in base-4.8!

hoistFree (first (+10)) xs == 11 :> 12 :> Pure 10

iterもちろん、を利用することもできます。

iter (uncurry (+)) (0 <$ xs) == 3 -- sum list elements

(and and ) にできれば、より一般的で原則に基づいた方法でリスト要素にアクセスできるので便利LWEです。このためには、間違いなく newtype が必要です。BitraversableBifunctorBifoldable

newtype LWE a e = LWE (Free ((,) a) e) deriving (lots of things)

instance Bifunctor LWE where bimap = bimapDefault
instance Bifoldable LWE where bifoldMap = bifoldMapDefault
instance Bitraversable LWE where bitraverse = ...

しかし、この時点で、単純な ADT を書き出して、Applicative,MonadとBitraversableインスタンスを数行のコードで書くことを考えるかもしれません。または、リスト要素に a を使用lensして記述することもできます。Traversal

import Control.Lens

elems :: Traversal (LWE a e) (LWE b e) a b
elems f (Pure e)  = pure (Pure e)
elems f (x :> xs) = (:>) <$> f x <*> elems f xs

この線に沿ってさらに考えLensて、最後の要素の for を作成する必要があります。これは、一般的なインターフェイスよりも少しおまけです。なぜなら、すべての有限要素には必ず 1 つの終了要素が含まれている必要がFreeあることがわかっているためです。LWELensTraversalPrism

end :: Lens (LWE a e) (LWE a e') e e'
end f (Pure e)  = Pure <$> f e
end f (x :> xs) = (x :>) <$> end f xs
于 2015-03-31T21:03:13.533 に答える