为什么这段代码不是恒定空间?

Tor*_*iel 33 performance haskell

我目前正在学习Haskell(通过交易成为程序员,但这是我第一次尝试使用函数式语言).

我想编写一个扫描列表的函数,并返回该列表的最小和最大元素.排序Prelude的功能minimum和maximum做法,但两者同时进行.我想出了以下代码:

import Data.List

-- Declaration of rand

minMax :: [Int] -> Maybe (Int, Int)
minMax []   = Nothing
minMax (x:xs) = Just (foldl' f (x, x) xs)
                where
                  f (a, b) c = (if c < a then c else a, if c > b then c else b)
Run Code Online (Sandbox Code Playgroud)

rand是一个生成无限数字列表的函数.问题是,当我追加以下main功能时:

main = print $ minMax $ take 1000000 $ rand 7666532
Run Code Online (Sandbox Code Playgroud)

使用profiling编译并运行所有这些,它显示它使用超过200 MB的内存,所以它绝对不是一个恒定空间函数(我希望它是).

问题是为什么以及我应该改变什么来解决它.据我所知foldl',从左侧折叠列表(它生成的方式相同)并且不是懒惰的,所以我不明白为什么内存使用率如此之高.我很确定这minMax是不正确的功能,只需打印上述列表即可

main = print $ take 1000000 $ rand 7666532
Run Code Online (Sandbox Code Playgroud)

给我1MB的使用量,这是我理解和期待的.

Bak*_*riu 26

请注意,foldl'强制累加器为弱头正常形式.由于累加器是一个元组,因此它不会强制对元组的两个元素进行求值.

如果明确强制使用这两个元素,则会得到一个常量空间函数:

f (a, b) c = a `seq` b `seq` (if c < a then c else a, if c > b then c else b)
Run Code Online (Sandbox Code Playgroud)

在原来的计划正在构建的类型的元组:(<thunk>, <thunk>)和每一次f应用于您只需建立一个元组与越来越大的thunk.当最后通过强制print调用消耗时show,对元组进行全面评估,并在此时进行所有比较.

在此时使用seq您强制f评估比较,因此在执行比较之前评估累加器中包含的thunk.因此,结果是存储在累加器中的thunk具有恒定的大小.

什么foldl'只是避免建立thunk : f (f (f ...) y) x.

Jubobs建议的另一种避免明确使用的解决方案seq是使用具有严格字段的​​数据类型:

data Pair a b = Pair !a !b
    deriving Show
Run Code Online (Sandbox Code Playgroud)

所以代码将成为:

minMax :: [Int] -> Maybe (Pair Int Int)
minMax []   = Nothing
minMax (x:xs) = Just (foldl' f (Pair x x) xs)
                where
                  f (Pair a b) c = Pair (if c < a then c else a) (if c > b then c else b)
Run Code Online (Sandbox Code Playgroud)

这完全避免了thunk.


oba*_*adz 12

该seq函数主要用于foldl'强制其第一个参数被评估为WHNF(弱头范式).

正如这里所解释的,WHNF评估在每次应用构造函数时都会停止.(a, b)因此,在WHNF始终,即使a和b是的thunk,因为你打的元组构造(,)越来越之前a和b.

因此,尽管使用了foldl'以下方法,但这个空间泄漏:

foldl' (\ (a, b) x -> (a + x, b + x)) (0, 1) [1..1000000]
Run Code Online (Sandbox Code Playgroud)

但这不是:

foldl' (\ (a, b) x -> a `seq` b `seq` (a + x, b + x)) (0, 1) [1..10000000]
Run Code Online (Sandbox Code Playgroud)

使用-XBangPatterns扩展名有时也很方便写这个:

foldl' (\ (!a, !b) x -> (a + x, b + x)) (0, 1) [1..10000000]
Run Code Online (Sandbox Code Playgroud)