4

幅広い入力をフォールディングする汎用関数を作成したかった (リスト、バイト文字列、テキスト (およびおそらく他の同様の表現) で単一の関数を機能させるを参照)。1つの答えが示唆したように、ListLikeはまさにそのためのものです。そのFoldableLLクラスは、折り畳み可能なあらゆるものの抽象化を定義します。ただし、モナドフォールドが必要です。したがって、 /foldMの観点から定義する必要があります。foldlfoldr

これまでのところ、私の試みは失敗しました。定義してみた

foldM'' :: (Monad m, LL.FoldableLL full a) => (b -> a -> m b) -> b -> full -> m b
foldM'' f z = LL.foldl (\acc x -> acc >>= (`f` x)) (return z)

しかし、大規模な入力ではメモリが不足します。未評価の大きな計算ツリーが構築されます。たとえば、大きなテキスト ファイルを

main :: IO ()
main = getContents >>= foldM'' idx 0 >> return ()
  where
    -- print the current index if 'a' is found
    idx !i 'a' = print i >> return (i + 1)
    idx !i _   =            return (i + 1)

すべてのメモリを消費して失敗します。

問題は、モナド計算が間違った順序で構成されていることだと感じています-((... >>= ...) >>= ...)代わりに、(... >>= (... >>= ...))しかしこれまでのところ、それを修正する方法がわかりませんでした。

回避策:ListLikeが公開されているので、アキュムレータを状態モナドにラップして smapM_を構築foldMしました。ListLike

modifyT :: (Monad m) => (s -> m s) -> StateT s m ()
modifyT f = get >>= \x -> lift (f x) >>= put

foldLLM :: (LL.ListLike full a, Monad m) => (b -> a -> m b) -> b -> full -> m b
foldLLM f z c = execStateT (LL.mapM_ (\x -> modifyT (\b -> f b x)) c) z

これは大規模なデータ セットでは問題なく機能しますが、あまり適切ではありません。そして、元の質問には答えません。それを単にFoldableLL(なしでmapM_) データで定義できる場合です。

4

1 に答える 1

8

したがって、目標は、またはのいずれかfoldMを使用して再実装することです。どちらにするべきですか？入力を遅延処理し、無限のリストを許可する必要があります。これにより、除外されます。そうなるでしょう。foldrfoldlfoldlfoldr

foldMそれで、これが標準ライブラリからの定義です。

foldM             :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM _ a []      =  return a
foldM f a (x:xs)  =  f a x >>= \fax -> foldM f fax xs

覚えておくべきことfoldrは、その引数が単に置き換え[]られ:、リストに含まれていることです（ListLikeそれを抽象化しますが、それでも指針として機能します）。

[]では、何に置き換える必要がありますか？明らかにreturn a。しかし、どこaから来たのでしょうか？a渡されるのはイニシャルではfoldMありません。リストが空でない場合、リストfoldrの最後に到達すると、アキュムレータが変更されているはずです。したがって[]、アキュムレータを受け取り、それを基になるモナドに返す関数に置き換えます:(\a -> return aまたは単にreturn）。foldrこれにより、計算するもののタイプもわかりますa -> m a。

そして、何に置き換える必要:がありますか？b -> (a -> m a) -> (a -> m a)これは、リストの最初の要素、処理されたテール（もちろん、怠惰な）、および現在のアキュムレータを取得する関数である必要があります。上記のコードからヒントをとることで、それを理解することができます\x rest a -> f a x >>= rest。したがって、の実装は次のfoldMようになります（上記のコードで型変数が一致するように型変数を調整します）。

foldM'' :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM'' f z list = foldr (\x rest a -> f a x >>= rest) return list z

そして実際、プログラムは任意の大きな入力を消費し、結果を吐き出すことができます。

定義が意味的に等しいことを帰納的に証明することさえできます（ただし、無限のリストに対応するために、おそらく共誘導または取得誘導を行う必要があります）。

見せたい

foldM f a xs = foldM'' f a xs

すべてのためにxs :: [b]。xs = []私たちが持っているのは

  foldM f a []
≡ return a     -- definition of foldM
≡ foldr (\x rest a -> f a x >>= rest) return [] a -- definition of foldr
≡ foldM'' f a [] -- definition of foldM''

そして、私たちがそれを持っていると仮定してxs、私たちはそれを次のように示しますx:xs：

  foldM f a (x:xs)
≡ f a x >>= \fax -> foldM f fax xs --definition of foldM
≡ f a x >>= \fax -> foldM'' f fax xs -- induction hypothesis
≡ f a x >>= \fax -> foldr (\x rest a -> f a x >>= rest) return xs fax -- definition of foldM''
≡ f a x >>= foldr (\x rest a -> f a x >>= rest) return xs -- eta expansion
≡ foldr (\x rest a -> f a x >>= rest) return (x:xs) -- definition of foldr
≡ foldM'' f a (x:xs) -- definition of foldM''

もちろん、この等式の推論は、あなたが興味を持っていたパフォーマンス特性について何も教えてくれません。

于 2012-10-14T10:04:53.480 に答える