先来一些 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
我有一个很大的 list ,
frets = replicate 10000000 (Fret 1 2)
我想计算a,例如,平均值,
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
的字段严格,事情似乎按预期工作。检查这是否适用于更大的应用程序。
最佳答案
看起来像 foldMap
太懒了,你的Fret
数据类型肯定是,导致经典foldl (+)
键入空间泄漏,在那里您积累了大量的 thunk,试图将您的输入列表减少到其平均值。它类似于 space leaks in list average with tuples .
很明显,你唯一循环中的累加器太懒了——你唯一使用堆栈的地方是 foldMap
使用相同的解决方案 - Frets
的严格对类型和 foldl'
foldMap
的实现就足够了,它将在恒定空间中运行:
foldMap' f = F.foldl' (\m -> mappend m . f) mempty
和
data Fret a = Fret !a !a
关于haskell - 大列表上的单体折叠中的堆栈溢出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15046547/