2

Haskell では、Foldable と Traversable が Haskell prelude に登場します。

これらは両方とも、シーケンスに対して操作を行います。

Prelude Data.Sequence> map (\n -> replicate n 'a') [1,3,5]
["a","aaa","aaaaa"]
Prelude Data.Sequence> fmap (\n -> replicate n 'a') (1 <| 3 <| 5 <| empty)
fromList ["a","aaa","aaaaa"]

私の質問は、Haskell の Foldable と Traversable に相当するものは、単純に Clojure のシーケンスですか?

仮定:

4

2 に答える 2

16

いいえFunctor。要素の有限シーケンスを表すあらゆる種類の表現はTraversable(したがって) になりますが、連結の明らかな概念がないという点で、 であるがシーケンスのようなものではないFoldable他の構造がたくさんあります。Traversable含まれている要素のシーケンスを取得する方法はありますが、構造はそのシーケンス以上のもので構成されている場合があります。

Traversable f事実上、 type を持つ構造体は、 typef xの有限個の要素を含むこと、および構造体が の各要素を 1 回だけ訪問するx何らかの方法があることを意味します。したがって、「変数を含むと見なされる構文内の用語」のようなものは.traversexTraversable

data Term x
  = Var x
  | Val Integer
  | Add (Term x) (Term x)

instance Traversable Term where
  traverse f (Var x)    = pure Var <*> f x
  traverse f (Val i)    = pure (Val i)
  traverse f (Add s t)  = pure Add <*> traverse f s <*> traverse f t

traverseすべての要素に対していつでも操作を実行できます。fmap撮って貰ってpure = id普通の<*>アプリとは。

instance Functor Term where
  fmap = fmapDefault

どこ

fmap :: (x -> y) -> Term x -> Term y

同時名前変更を実装します。

その間、Foldableインスタンス

instance Foldable Term where
  foldMap = foldMapDefault

はpureモノイドのニュートラル要素と<*>結合操作を与えるため、reduce のような操作が得られます。例えば、

foldMap (:[]) :: Term x -> [x]

項に現れる変数のリストを与える. つまり、Traversableデータから要素のシーケンスを常に取得できますが、データはそれらの要素以外の構造を持つ場合があります。s には変数 (それらの およびs)Term以外の構造があり、構文ツリーで "cons" が何を意味するかはあまり明確ではありません。ValAdd

そのため、シーケンスよりも多くの構造体が存在しますがTraversable、Traversableインターフェイスではシーケンスのような操作が少なくなります。のポイントは、 list性をキャプチャするのではなく、mapのような操作とreduceTraversableのような操作を一般化することです。

于 2014-08-22T10:09:36.580 に答える
1

Foldable と Traversableに関する Haskell wiki ドキュメントを指摘したいと思います。

まず、FoldableとTraversableは 2 つの異なる型クラスです。Foldableに関しては、Wiki ページで作成されたコメントは、Clojure シーケンスとほとんど同じであることを示唆しているようです。すべてのFoldableには、リストとしての表現があります。

toList :: Foldable a => [a]
toList a = foldr (:) [] a

そして（私が間違っていたら訂正してください）構造を折りたたむことは、関連するリストを折りたたむことと同じようです。

foldr f b a = foldr f b (toList a)

この式でfoldrは、左側が一般的なバージョンで、右側がリストのものです。

ここでの Haskell と Clojure の主な違いは、Clojure ではtoList関数を自分で適用してデータ構造をシーケンスに変換してから折り畳み/縮小する必要があることです。フラットなデータ構造 (つまり、リスト、ベクトル、ハッシュ マップなど)toListの場合は、単なる恒等関数であるため、表示されません。一方、木のようなものについては、tree-seq折りたたむ前に次のような関数を呼び出す必要があります。

于 2014-08-22T17:08:08.853 に答える