haskell - 堆栈溢出成单倍折叠，超过大列表

首先一些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)

我要在上面计算一个平均值，

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 (+)类型空间泄漏，您在其中积累了一大堆杂物，试图将您的输入列表减少到平均水平。它类似于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/