12

単純な RPN 計算機を作成する過程で、次の型エイリアスがあります。

type Stack = List[Double]
type Operation = Stack => Option[Stack]

...そして、奇妙なScalaコードの行を書きました:

val newStack = operations.foldLeft(Option(stack)) { _ flatMap _ }

これは値の初期値を取り、そのスタックにstackリストを適用します。operations各操作は失敗する可能性がある (つまり、 が生成されるOption[Stack]) ため、それらを で順序付けますflatMap。これについて (私の考えでは) ちょっと変わっているのは、データのリストを折りたたむのではなく、モナド関数のリストを折りたたんでいることです。

この「フォールド バインド」動作をキャプチャする標準関数があるかどうかを知りたいです。「Name That Combinator」ゲームをプレイしようとしているとき、Hoogle はたいてい私の友達なので、Haskell で同じ頭の体操を試みました。

foldl (>>=) (Just stack) operations

ここでのタイプは次のとおりです。

foldl :: (a -> b -> a) -> a -> [b] -> a
(>>=) :: Monad m => m a -> (a -> m b) -> m b

したがって、 と の型を並べた後のミステリーfoldl (>>=)コンビネータの型は次のようになります。foldl(>>=)

mysteryCombinator :: Monad m => m a -> [a -> m a] -> m a

...これもまた、私たちが期待するものです。私の問題は、Hoogle でその型の関数を検索しても結果が得られないことです。私は合理的であると思われる他のいくつかの順列を試しました: a -> [a -> m a] -> m a(つまり、非モナド値で開始)、[a -> m a] -> m a -> m a(つまり、引数を反転して)、しかし運もありませんでした。私の質問は、私の謎の「フォールドバインド」コンビネーターの標準的な名前を知っている人はいますか?

4

2 に答える 2

15

a -> m aは、引数と結果の型が両方とも であるKleisli 矢印です。Control.Monad.(>=>)は 2 つの Kleisli 矢印を構成します。

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c

と思いますflip (.)が、関数ではなく Kleisli の矢印を使用します。

したがって、このコンビネータをコンポジションと「アプリケーション」の 2 つの部分に分割できます。

composeParts :: (Monad m) => [a -> m a] -> a -> m a
composeParts = foldr (>=>) return

mysteryCombinator :: (Monad m) => m a -> [a -> m a] -> m a
mysteryCombinator m fs = m >>= composeParts fs

さて、(>=>)とflip (.)は単に類似しているだけではなく、より深い意味で関連しています。関数矢印(->)と Kleisli 矢印をラップするデータ型 の両方がControl.Category.CategoryKleisliのインスタンスです。したがって、そのモジュールをインポートする場合、実際には次のように書き換えることができます。composeParts

composeParts :: (Category cat) => [cat a a] -> cat a a
composeParts = foldr (>>>) id

(>>>)(Control.Category で定義) は、より適切な書き方flip (.)です。

したがって、私が知っている標準的な名前はありませんが、関数のリストを構成することの一般化にすぎません。標準ライブラリには、 isとisのモノイドインスタンスEndo aをラップa -> aして持つ型があります。これを任意のカテゴリに一般化できます。memptyidmappend(.)

newtype Endo cat a = Endo { appEndo :: cat a a }

instance (Category cat) => Monoid (Endo cat a) where
  mempty = Endo id
  mappend (Endo f) (Endo g) = Endo (f . g)

次に、次のように実装できますcomposeParts。

composeParts = appEndo . mconcat . map Endo . reverse

これはmconcat . reverse、いくつかのラッピングを行うだけです。ただし、モノイドを反転したモノイドに変換するモノイドを使用するreverseことで、インスタンスが では(.)なくを使用するため、存在する を回避できます。(>>>)Dual amappend

composeParts :: (Category cat) => [cat a a] -> cat a a
composeParts = appEndo . getDual . mconcat . map (Dual . Endo)

これcomposePartsは、ある意味で「明確に定義されたパターン」であることを示しています:)

于 2012-01-03T18:36:27.620 に答える
2

非モナド値で始まるものは (modulo flip)です。

Prelude> :t foldr (Control.Monad.>=>) return
foldr (Control.Monad.>=>) return
    :: Monad m => [c -> m c] -> c -> m c

(またはfoldl)

(はい、これで質問の答えにならないことはわかっていますが、コメント内のコード レイアウトは満足のいくものではありません。)

于 2012-01-03T18:32:40.380 に答える