20

更新：さて、この質問は潜在的に非常に簡単になります。

q <- mapM return [1..]

なぜこれが二度と戻らないのですか？

mapMは無限のリストを怠惰に処理しませんか？

以下のコードがハングします。ただし、A行をB行に置き換えると、ハングしなくなります。または、行Aの前に「splitRandom $」を付けても、ハングしません。

Q1は：mapMは怠惰ではありませんか？そうでなければ、なぜ行Aを行Bに置き換えると「これを修正する」コードになるのでしょうか。

Q2：前の行AのsplitRandomが問題を「解決」するのはなぜですか？

import Control.Monad.Random
import Control.Applicative

f :: (RandomGen g) => Rand g (Double, [Double])
f = do
    b <- splitRandom $ sequence $ repeat $ getRandom
    c <- mapM return b -- A
    -- let c = map id b -- B
    a <- getRandom
    return (a, c)

splitRandom :: (RandomGen g) => Rand g a -> Rand g a
splitRandom code = evalRand code <$> getSplit

t0 = do
    (a, b) <- evalRand f <$> newStdGen
    print  a
    print (take 3 b)

このコードは、乱数の無限のリストを怠惰に生成します。次に、単一の乱数を生成します。splitRandomを使用することにより、無限リストの前にこの後者の乱数を最初に評価できます。これは、関数でcの代わりにbを返す場合に実証できます。

ただし、mapMをリストに適用すると、プログラムがハングします。このハングを防ぐために、mapMの前にsplitRandomを再度適用する必要があります。mapMは怠惰にできるという印象を受けました

4

5 に答える 5

32

まあ、 lazy があり、次にlazyがあります。mapM必要以上の仕事をしないという点で、確かに怠け者です。ただし、型シグネチャを見てください。

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

これが何を意味するか考えてみてください: 関数a -> m bと一連のas を与えます。レギュラーmapはそれらを の束に変えることができますm bが、 . にはできませんm [b]。モナドが邪魔にならないようにbs を 1 つに結合する唯一の方法は、 を使用して s を一緒に並べて list を構築することです。[b]>>=m b

実際、mapMは と正確に等価sequence . mapです。

>>=一般に、モナド式では、値が使用された場合、その式につながる s のチェーン全体を強制する必要があるためsequence、無限リストへの適用は決して終了できません。

制限のないモナド シーケンスを使用する場合は、明示的なフロー制御が必要になります。たとえば、単純な再帰関数が好きmapMでsequence提供しない単純な再帰関数が何らかの方法でバインドのチェーンに焼き付けられたループ終了条件、またはステップ。 -ステップごとのシーケンス、次のようなもの：

data Stream m a = Nil | Stream a (m (Stream m a))

...必要な数のモナド層のみを強制するようにします。

編集::に関してsplitRandom、何が起こっているかというと、Rand計算を渡しsplitRandom、それをシード get で評価しreturn、結果を ing するということです。がない場合splitRandom、シングルで使用されるシードはgetRandom、無限リストの順序付けの最終結果から取得する必要があるため、ハングします。extrasplitRandomを使用すると、使用されるシードは 2 つのsplitRandom呼び出しをスレッド化するだけで済むため、機能します。乱数の最終リストが機能するのはRand、その時点でモナドを離れており、その最終状態に依存するものがないためです。

于 2010-07-17T04:49:33.210 に答える
8

さて、この質問は非常に簡単になる可能性があります。

q <- mapM リターン [1..]

なぜこれは決して返されないのですか？

それは必ずしも真実ではありません。それはあなたがいるモナドに依存します。

たとえば、恒等モナドを使用すると、結果を遅延して使用でき、正常に終了します。

newtype Identity a = Identity a

instance Monad Identity where
  Identity x >>= k = k x
  return = Identity

-- "foo" is the infinite list of all the positive integers
foo :: [Integer]
Identity foo = do
  q <- mapM return [1..]
  return q

main :: IO ()
main = print $ take 20 foo -- [1 .. 20]
于 2013-01-06T01:09:54.913 に答える
7

mapM return [1..]これは、終了しない証明の試みです。しばらくの間、モナドにいると仮定しましょうIdentity(この引数は他のモナドにも同様に適用されます):

mapM return [1..] -- initial expression
sequence (map return [1 ..]) -- unfold mapM
let k m m' = m >>= \x ->
             m' >>= \xs ->
             return (x : xs)
in foldr k (return []) (map return [1..]) -- unfold sequence

ここまでは順調ですね...

-- unfold foldr
let k m m' = m >>= \x ->
             m' >>= \xs ->
             return (x : xs)
    go [] = return []
    go (y:ys) = k y (go ys)
in go (map return [1..])

-- unfold map so we have enough of a list to pattern-match go:
go (return 1 : map return [2..])
-- unfold go:
k (return 1) (go (map return [2..])
-- unfold k:
(return 1) >>= \x -> go (map return [2..]) >>= \xs -> return (x:xs)

return a = Identity aIdentity モナドと Identity モナドでそれを思い出してください(Identity a) >>= f = f a。続き:

-- unfold >>= :
(\x -> go (map return [2..]) >>= \xs -> return (x:xs)) 1
-- apply 1 to \x -> ... :
go (map return [2..]) >>= \xs -> return (1:xs)
-- unfold >>= :
(\xs -> return (1:xs)) (go (map return [2..]))

この時点で に申し込みたいと思っていますが\xs、まだできません。代わりに、適用する値が得られるまで展開を続ける必要があります。

-- unfold map for go:
(\xs -> return (1:xs)) (go (return 2 : map return [3..]))
-- unfold go:
(\xs -> return (1:xs)) (k (return 2) (go (map return [3..])))
-- unfold k:
(\xs -> return (1:xs)) ((return 2) >>= \x2 ->
                         (go (map return [3..])) >>= \xs2 ->
                         return (x2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) ((\x2 -> (go (map return [3...])) >>= \xs2 ->
                        return (x2:xs2)) 2)

この時点では、まだ に申請できませんが\xs、 に申請することはできます\x2。続き:

-- apply 2 to \x2 :
(\xs -> return (1:xs)) ((go (map return [3...])) >>= \xs2 ->
                         return (2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) (\xs2 -> return (2:xs2)) (go (map return [3..]))

\xs これで、どちらも \xs2減らすこともできないところまで来ました。私たちの唯一の選択肢は次のとおりです。

-- unfold map for go, and so on...
(\xs -> return (1:xs))
  (\xs2 -> return (2:xs2))
    (go ((return 3) : (map return [4..])))

ご覧のとおり、 のおかげでfoldr、適用する一連の関数を作成しています。リストの最後から始めて、上に向かって作業を進めています。各ステップで入力リストが無限であるため、この展開が終了することはなく、答えが得られることもありません。

これは、この例を見ると理にかなっています (別の StackOverflow スレッドから借用したもので、現時点ではどれを見つけることができません)。以下のモナドのリスト:

mebs = [Just 3, Just 4, Nothing]

sequenceをキャッチしNothingて、全体の失敗を返すことが期待されます。

sequence mebs = Nothing

ただし、このリストの場合:

mebs2 = [Just 3, Just 4]

シーケンスが私たちに与えることを期待します：

sequence mebs = Just [3, 4]

言い換えれば、正しい答えを見つけるために、モナド計算のリスト全体を見sequence て、それらをつなぎ合わせ、それらすべてを実行する必要があります。sequenceリスト全体を見ないで答えを出す方法はありません。

注：この回答の以前のバージョンでfoldrは、リストの後ろから計算し、無限リストではまったく機能しないと主張していましたが、それは正しくありません! 渡す演算子のfoldr2 番目の引数が遅延していて、リストのような遅延データ コンストラクターを使用して出力を生成する場合、foldrは無限リストで問題なく機能します。例については、を参照foldr (\x xs -> (replicate x x) ++ xs) [] [1...]してください。しかし、私たちの operator はそうではありませんk。

于 2010-07-17T22:31:34.597 に答える
4

この質問は、IO モナドと他のモナドの違いをよく示しています。バックグラウンドで、mapM はすべてのリスト要素間のバインド操作 (>>=) を使用して式を構築し、モナド式のリストをリストのモナド式に変換します。さて、IO モナドの違いは、Haskell の実行モデルが IO モナドのバインド中に式を実行していることです。これはまさに、最終的に (純粋に怠惰な世界で) 何かを強制的に実行させるものです。

したがって、IO Monad はある意味で特別です。bind のシーケンス パラダイムを使用して、実際に各ステップの実行を強制します。これが、プログラムが最終的に何かを実行するために行うものです。その他のモナドは異なります。モナドに応じて、バインド演算子の他の意味があります。IO は実際にはバインド内で物事を実行する 1 つのモナドであり、これが IO タイプが「アクション」である理由です。

次の例は、他のモナド (たとえば Maybe モナド) が実行を強制しないことを示しています。最後に、これは IO モナドの mapM が式を返すという結果につながります。これは、実行されると、最終的な値を返す前に各要素を実行します。

これに関する優れた論文があります。ここから開始するか、表示セマンティクスとモナドを検索してください。

Maybe モナドの例:

モジュールのメイン

fstMaybe :: [Int] -> Maybe [Int] fstMaybe = mapM (\x -> if x == 3 then Nothing else Just x)

main = do let r = fstMaybe [1..] return r

于 2015-01-11T16:16:12.080 に答える