13

ディレクトリのすべての内容を幅優先順でリストすると効率が低下するという質問で、効率が低いのは再帰モナド関数の奇妙な動作によるものであることがわかりました。

試す

sequence $ map return [1..]::[[Int]]
sequence $ map return [1..]::Maybe [Int]

そしてghciは無限の計算に陥ります。

次のように、より読みやすい形式でシーケンス関数を書き直すと:

sequence' []     = return []
sequence' (m:ms) = do {x<-m; xs<-sequence' ms; return (x:xs)}

そして試してください：

sequence' $ map return [1..]::[[Int]]
sequence' $ map return [1..]::Maybe [Int]

同じ状況、無限ループが発生します。

有限リストを試す

sequence' $ map return [1..]::Maybe [Int]

Just [1,2,3,4..]長い間待った後、期待される結果が飛び出します。

私たちが試したことから、sequence' の定義は怠惰に見えますが、厳密であり、sequence' の結果を出力する前にすべての数値を作成する必要があるという結論に達することができます。

シーケンスだけでなく、関数を定義すると

iterateM:: Monad m => (a -> m a) -> a -> m [a]
iterateM f x = (f x) >>= iterateM0 f >>= return.(x:)

そして試してみてください

iterateM (>>=(+1)) 0

その後、無限の計算が発生します。

ご存知のように、非モナド iterate は上記の iterateM と同じように定義されますが、なぜ iterate が遅延で iterateM が厳密なのかを説明します。上記からわかるように、 iterateM と sequence' はどちらも再帰的なモナド関数です.再帰的なモナド関数で奇妙なことはありますか?

4

3 に答える 3

15

問題は の定義ではなくsequence、基礎となるモナドの操作です。特に、 の厳密さを決定するのはモナドの>>=操作の厳密さですsequence。

十分に怠惰なモナドの場合sequence、無限リストで実行し、結果を段階的に消費することは完全に可能です。検討：

Prelude>  :m + Control.Monad.Identity
Prelude Control.Monad.Identity> runIdentity (sequence $ map return [1..] :: Identity [Int])

リストは、必要に応じて段階的に印刷 (消費) されます。

と でこれを試すと、啓発されるかもしれませControl.Monad.State.StrictんControl.Monad.State.Lazy:

-- will print the list
Prelude Control.Monad.State.Lazy> evalState (sequence $ map return [1..] :: State () [Int]) ()
-- loops
Prelude Control.Monad.State.Strict> evalState (sequence $ map return [1..] :: State () [Int]) ()

IOモナドでは、>>=は定義により正格です。なぜなら、この正格性は効果の順序付けに関する推論を可能にするために必要な特性だからです。@jberryman の回答は、「strict >>=」の意味をよく示していると思います。IOおよび strict を持つ他のモナドの場合>>=、リスト内の各式は、戻る前に評価する必要がありますsequence。式のリストが無限にある場合、これは不可能です。

于 2013-01-24T08:30:33.670 に答える
13

あなたはバインドの仕組みをよく理解していません:

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

以下は、長さ 3 のリストでのみ機能する sequence の実装です。

sequence3 (ma:mb:mc:[]) = ma >>= (\a-> mb >>= (\b-> mc >>= (\c-> return [a,b,c] )))

外側のコンストラクター (つまり、最も外側のコンスまたは(:)) を返す前に、リスト内の各「モナド アクション」を「実行」する必要があることがわかりますか? 信じられない場合は、別の方法で実装してみてください。

これが、モナドが IO に役立つ理由の 1 つです。つまり、2 つのアクションをバインドすると、効果の暗黙的な順序付けが行われます。

また、「怠け者」や「厳密」という用語の使用にも注意する必要があります。最終結果をラップする前にリスト全体をトラバースする必要があるのは事実sequenceですが、以下は完全にうまく機能します:

Prelude Control.Monad> sequence3 [Just undefined, Just undefined, Nothing]
Nothing
于 2013-01-24T06:36:03.880 に答える
11

モナディックsequenceは一般に、無限リストに対して怠惰に動作することはできません。その署名を検討してください。

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

引数内のすべてのモナド効果を 1 つの効果に結合します。無限のリストに適用すると、無限の数の効果を 1 つに結合する必要があります。可能なモナドもあれば、そうでないモナドもあります。

sequence例として、例で行ったように、に特化したものを検討Maybeしてください。

sequence :: [Maybe a] -> Maybe [a]

結果はJust ...、配列内のすべての要素が である場合Just ...です。いずれかの要素が であるNothing場合、結果はNothingです。これは、入力のすべてのNothing要素を調べない限り、結果がまたはであるかどうかを判断できないことを意味しますJust ...。

sequence特殊化された[]:にも同じことが当てはまりますsequence :: [[a]] -> [[a]]。引数の要素のいずれかが空のリストである場合、結果全体が のように空のリストになりsequence [[1],[2,3],[],[4]]ます。したがってsequence、リストのリストを評価するには、すべての要素を調べて、結果がどのようになるかを確認する必要があります。

一方、Readerモナドに特化したシーケンスは引数を遅延処理できます。これは、Readerのモナド計算に実際の「効果」がないためです。あなたが定義する場合

inf :: Reader Int [Int]
inf = sequence $ map return [1..]

多分

inf = sequence $ map (\x -> reader (* x)) [1..]

を呼び出すとわかるように、遅延して動作しますtake 10 (runReader inf 3)。

于 2013-01-24T07:53:25.697 に答える