5

Maybe Listたとえば、エラー処理を除いて、リストはMaybeそれ自体が少しあるため、通常は表示されません。リストには独自の " Nothing":[]と独自の " Just":があり(:)ます。私は、Maybe と関数を使用して、標準リストと「実験的」リストに変換するリスト型を作成しました。toStd . toExp == id.

data List a = List a (Maybe (List a))
    deriving (Eq, Show, Read)

toExp [] = Nothing
toExp (x:xs) = Just (List x (toExp xs))

toStd Nothing = []
toStd (Just (List x xs)) = x : (toStd xs)

繰り返しを減らし、一般化する試みとして、それについてどう思いますか?

これらのリストを使用して、ツリーも定義できます。

type Tree a = List (Tree a, Tree a)

ただし、この最後のコードはテストしていません。

4

5 に答える 5

9

Haskellではさまざまな方法でリストを定義できます。たとえば、関数として：

{-# LANGUAGE RankNTypes #-}

newtype List a = List { runList :: forall b. (a -> b -> b) -> b -> b }

nil :: List a
nil = List (\_ z -> z )

cons :: a -> List a -> List a
cons x xs = List (\f z -> f x (runList xs f z))

isNil :: List a -> Bool
isNil xs = runList xs (\x xs -> False) True

head :: List a -> a
head xs = runList xs (\x xs -> x) (error "empty list")

tail :: List a -> List a
tail xs | isNil xs = error "empty list"
tail xs = fst (runList xs go (nil, nil))
    where go x (xs, xs') = (xs', cons x xs)

foldr :: (a -> b -> b) -> b -> List a -> b
foldr f z xs = runList xs f z

この実装の秘訣は、リストがリストの要素に対してフォールドを実行する関数として表されていることです。

fromNative :: [a] -> List a
fromNative xs = List (\f z -> foldr f z xs)

toNative :: List a -> [a]
toNative xs = runList xs (:) []

いずれにせよ、本当に重要なのは、タイプとその操作が従う契約（または法律）、および実装のパフォーマンスです。基本的に、契約を履行する実装は正しいプログラムを提供し、より高速な実装はより高速なプログラムを提供します。

リストの契約は何ですか？まあ、私はそれを完全に詳細に表現するつもりはありませんが、リストは次のようなステートメントに従います：

  1. head (x:xs) == x
  2. tail (x:xs) == xs
  3. [] == []
  4. [] /= x:xs
  5. xs == ysとの場合x == y、x:xs == y:ys
  6. foldr f z [] == z
  7. foldr f z (x:xs) == f x (foldr f z xs)

編集：そしてこれをオーガストの答えに結びつけるために：

newtype ExpList a = ExpList (Maybe (a, ExpList a))

toExpList :: List a -> ExpList a
toExpList xs = runList xs (\x xs -> ExpList (Just (x, xs))) (ExpList Nothing)

foldExpList f z (ExpList Nothing) = z
foldExpList f z (ExpList (Just (head, taill))) = f head (foldExpList f z tail)

fromExpList :: ExpList a -> List a
fromExpList xs = List (\f z -> foldExpList f z xs)
于 2012-07-06T16:55:33.320 に答える
9

すべての ADT は(,)、、Either、()、(->)、VoidおよびMu

data Void --using empty data decls or
newtype Void = Void Void

Muファンクターの不動点を計算します

newtype Mu f = Mu (f (Mu f))

例えば

data [a] = [] | (a:[a])

と同じです

data [a] = Mu (ListF a)
data ListF a f = End | Pair a f

それ自体はに同形です

newtype ListF a f = ListF (Either () (a,f))

以来

data Maybe a = Nothing | Just a

に同形です

newtype Maybe a = Maybe (Either () a)

あなたが持っている

newtype ListF a f = ListF (Maybe (a,f))

これは mu にインライン化できます

data List a = List (Maybe (a,List a))

そしてあなたの定義

data List a = List a (Maybe (List a))

Mu の展開と外側の Maybe の削除です (空でないリストに対応)

そして、あなたは終わった...

いくつかのこと

  1. カスタム ADT を使用すると、明確さと型の安全性が向上します

  2. この普遍性は便利です: GHC.Generic を参照してください

さて、私はほとんど同型だと言いました。正確にはそうではありません。

hmm = List (Just undefined)

[a] = [] | (a:[a])リストの定義には同等の値はありません。これは、Haskell のデータ型が共導的であるためであり、遅延評価モデルに対する批判の的となっています。これらの問題は、厳密な合計と積 (および値関数による呼び出し) のみを使用し、特別な "Lazy" データ コンストラクターを追加することで回避できます。

data SPair a b = SPair !a !b
data SEither a b = SLeft !a | SRight !b
data Lazy a = Lazy a --Note, this has no obvious encoding in Pure CBV languages,
--although Laza a = (() -> a) is semantically correct, 
--it is strictly less efficient than Haskell's CB-Need

そして、すべての同型を忠実に符号化できます。

于 2012-07-07T00:05:55.703 に答える
7

の観点からリストを定義できますがMaybe、そのようにはできません。Listタイプを空にすることはできません。Maybe (List a)それともの代わりになるつもりでしたか[a]。リストとおそらくタイプを区別しないため、これは悪いようです。

これはうまくいくでしょう

newtype List a = List (Maybe (a, List a))

これにはいくつかの問題があります。最初にこれを使用すると、通常のリストよりも冗長になります。次に、ペアを取得したため、ドメインはリストと同型ではありません (定義されていない可能性があります。ドメインに余分なレベルを追加します)。

于 2012-07-06T15:51:09.423 に答える
1

Haskellを最初に使い始めたとき、私も、冗長性を避けるのが良いという理由で、できる限り既存のタイプで物事を表現しようとしました。私の現在の理解（動くターゲット！）には、トレードオフの多次元ウェブのアイデアが含まれる傾向があります。ここでは、例を貼り付けて「意味がわかりますか？」と尋ねるほどの「答え」はしません。とにかくお役に立てば幸いです。

Darcsコードを少し見てみましょう。

data UseCache = YesUseCache | NoUseCache
    deriving ( Eq )

data DryRun = YesDryRun | NoDryRun
    deriving ( Eq )

data Compression = NoCompression
                 | GzipCompression
    deriving ( Eq )

これらの3つのタイプがすべてBool'sであった可能性があることに気づきましたか？なぜDarcsハッカーは、コードにこの種の冗長性を導入する必要があると判断したと思いますか？別の例として、数年前に変更したコードを次に示します。

type Slot = Maybe Bool                  -- OLD code
data Slot = InFirst | InMiddle | InLast -- newer code

2番目のコードが最初のコードよりも改善されていると判断したのはなぜだと思いますか？

最後に、これが私の日常業務の一部からのコードです。これは、newtypeオーガストが言及した構文を使用しています。

newtype Role = Role { fromRole :: Text }
  deriving (Eq, Ord)

newtype KmClass = KmClass { fromKmClass :: Text }
  deriving (Eq, Ord)

newtype Lemma = Lemma { fromLemma :: Text }
  deriving (Eq, Ord)

Textここで、私が完全に良いタイプを取り、それを3つの異なるものにまとめるという奇妙なことをしたことに気付くでしょう。普通の古いものと比較して、3つのものには新しい機能がありませんText。彼らはただ違うだけです。正直なところ、これを行うのが良い考えだったかどうかは完全にはわかりません。暫定的には、さまざまな理由でさまざまなビットやテキストを操作したためだと思いますが、時間が経てばわかります。

私が何をしようとしているのか分かりますか？

于 2012-07-07T05:56:28.067 に答える
1

それがリストの場合、それは のインスタンスであるはずFunctorですよね?

instance Functor List
  where fmap f (List a as) = List (f a) (mapMaybeList f as)

mapMaybeList :: (a -> b) -> Maybe (List a) -> Maybe (List b)
mapMaybeList f as = fmap (fmap f) as

ここに問題があります:Listのインスタンスを作成できますFunctorが、Maybe List はそうではありません:それ自体Maybeが のインスタンスでなかったとしてもFunctor、構造のようなものを何かのインスタンスに直接作成することはできませんMaybe . List(必要になるでしょう)。ラッパータイプ)。

他の型クラスについても同様です。

そうは言っても、あなたの定式化ではこれを行うことができますが、これは標準の Haskell リストでは行うことができません:

instance Comonad List
  where extract (List a _) = a
        duplicate x @ (List _ y) = List x (duplicate y)

ただし、Maybe List はまだ一般的ではありません。

于 2012-07-06T17:48:36.857 に答える