5

最初のいくつかimports、

import Control.Applicative
import Data.Traversable as T
import Data.Foldable as F
import Data.Monoid

値のペアを保持しているファンクターがあるとしましょう。

data Fret a = Fret a a deriving (Show)

instance Functor Fret where fmap f (Fret a b) = Fret (f a) (f b)

instance Applicative Fret where
    pure a = Fret a a
    Fret aa ab <*> Fret ba bb = Fret (aa ba) (ab bb)

instance Monoid a => Monoid (Fret a) where
    mempty = Fret mempty mempty
    a `mappend` b = mappend <$> a <*> b

私はこれらの大きなリストを持っています、

frets = replicate 10000000 (Fret 1 2)

その上で、たとえば平均を計算したい

data Average a = Average !Int !a deriving (Read, Show)

instance Num a => Monoid (Average a) where
    mempty = Average 0 0
    Average n a `mappend` Average m b = Average (n+m) (a+b)

runAverage :: Fractional a => Average a -> a
runAverage (Average n a) = a / fromIntegral n

average = Average 1

これのいくつかの潜在的な実装は次のとおりです。

average1 = runAverage <$> foldMap (fmap average) frets

average2 = pure (runAverage . mconcat) <*> T.sequenceA (map (pure (Average 1) <*>) frets)

残念ながら、これらはすべてスタックオーバーフローを引き起こします。

問題はで過度の怠惰である可能性があると考えてFoldable.foldMap、より厳密なバリアントを実装してみました、

foldMap' :: (F.Foldable f, Monoid m) => (a -> m) -> f a -> m
foldMap' f = F.foldl' (\m a->mappend m $! f a) mempty

average3 = runAverage <$> foldMap' (fmap average) frets

残念ながら、これもオーバーフローします。

アプローチのクリーンな構造を妥協することなく、これをどのように達成できますか？

アップデート

Fret厳密なフィールドを作成すると、期待どおりに機能しているように見えます。これがより大きなアプリケーションで機能するかどうかを確認します。

4

1 に答える 1

7

foldMap怠惰すぎるように見えますが、Fretデータ型は確かに怠惰であり、古典的なfoldl (+)タイプのスペースリークにつながります。そこでは、入力リストを平均に減らそうとする大量のサンクのチェーンが蓄積されます。これは、タプルを使用したリスト平均のスペースリークに類似しています。

明らかに、あなたの唯一のループのアキュムレータは怠惰すぎます-スタックを使用する唯一の場所はfoldMap

ここに画像の説明を入力してください

同じソリューションを使用します-の厳密なペアタイプFretsとfoldl'実装でfoldMap十分であり、一定のスペースで実行されます：

 foldMap' f = F.foldl' (\m -> mappend m . f) mempty

と

 data Fret a = Fret !a !a

ここに画像の説明を入力してください

于 2013-02-23T23:21:51.993 に答える