4

Foldable クラスには、fold、foldl、foldr、foldl'、foldr' が含まれていますが、fold はありません (厳密なモノイド フォールドの場合)。

フォールドの動作を IntMap でエミュレートするにはどうすればよいですか (ツリーとして実装されていますが、内部ノードに直接アクセスすることはできません)。

動機：

特に、サイズ K (合計サイズ N = M*K) の M 個の IntMap を含む IntMap がある場合、それらを O(N * log(M)) big-O 実行時間で結合したいと考えています。何かのようなもの：

unionMaps :: IntMap (IntMap a) -> IntMap a
unionMaps = fold'

IntMap は、mappend が共用体として定義された Monoid のインスタンスであるため、これは機能します。一般に、foldl' または foldr' を使用すると、最悪の場合の実行時間が Omega(N * log N) になるため、理論的には遅くなります。確かに、これはおそらく実際には取るに足らない違いですが、私は理論的に最適な境界を気にするのに十分な知識を持っています.

おっと、上記は間違っています。もっと注意深く調べてみたところ、fold を使用するか、foldl を使用するか、foldr を使用するかは問題ではないことがわかりました。実行時間は O(N * log(M)) になります。したがって、この質問に対する動機はもうありません。

4

1 に答える 1

3

完全なライブラリが見つからなかったのでFoldable fold'、基本的な質問に答えるために、上記のコメントから@Carlの提案のコードをいくつか書きました（WHNFのみ）：

{-# LANGUAGE BangPatterns #-}
import Data.Monoid
import Data.Foldable

newtype StrictM m = StrictM { getStrict :: m }

instance Monoid m => Monoid (StrictM m) where
    mempty = StrictM mempty
    mappend (StrictM !x) (StrictM !y) = StrictM (mappend x y)

fold' :: (Foldable t, Monoid m) => t m -> m
fold' = getStrict . foldMap StrictM
于 2014-06-17T00:53:21.890 に答える