4

type の関数を考えてみましょう(Monad m) => a -> m a。例えば：

ghci> let f x = Just (x+1)

何度でも応募できるようにしたいです。最初に試したのは

ghci> let times n f = foldr (>=>) return $ replicate n f

問題は、大規模な場合は機能しないことですn:

ghci> 3 `times` f $ 1
Just 4
ghci> 1000000 `times` f $ 1
Just *** Exception: stack overflow

他の方法でも機能しません:

ghci> let timesl n f = foldl' (<=<) return $ replicate n f
ghci> 3 `timesl` f $ 1
Just 4
ghci> 1000000 `timesl` f $ 1
Just *** Exception: stack overflow

実際、機能するのは($!)厳密性演算子を使用することです

ghci> let timesStrict n f = foldr1 ((>=>) . ($!)) $ replicate n f
ghci> 3 `timesStrict` f $ 1
Just 4
ghci> 10000000 `timesStrict` f $ 1
Just 10000001

より良い、またはより慣用的な解決策はありますか? それとももっと厳しいものですか？f重い関数の場合でも、スタック オーバーフローが発生しやすいです。

UPD:ポイントフルな形式で書いtimesても、重いモナドアクションを作成する問題を解決できないことがわかりました。これは fx = Just (x+1) で機能しますが、現実の世界では失敗します:

times f 0 a = return a
times f i a = (f $! a) >>= times f (i - 1)
4

3 に答える 3

4

f次のように厳密にする場合

f x = let y = x+1 in y `seq` Just y

また

-- remember to enable -XBangPatterns
f !x = Just (x+1)

残りはそのままにしておくと、非常に大きなn.

ghci> 回 4000000000 f 3
ただ4000000003
于 2010-02-10T18:01:05.547 に答える
2

おそらく、既存の関数のより厳密なバリアントをいくつか作成するでしょう。

{-# LANGUAGE BangPatterns #-}
iterate' f !x = x : iterate' f (f x)
ma >>=! f = do !a <- ma; f a
times' n f a = iterate' (>>=! f) (return a) !! n

seqおそらく、あなたの問題は、WHNF の最初の引数のみを評価するという事実から生じているのでしょうか? 複雑な構造に取り組んでいる場合は、deepseqseqなどのdeep が必要になる場合があります。

于 2010-02-10T15:55:12.103 に答える
1

私はこれを思いついた：

 last $ take n $ iterate (>>= f) $ Just 1

しかし、大量のn. 今は詳しく調べる時間がありません:-(

于 2010-02-10T15:13:22.713 に答える