3

GHC 是否足够智能以在“半并行”的列表上运行多个操作？

考虑这个（简化的）代码：

findElements bigList = do
  let special = head . filter isSpecial $ bigList
  let others  = filter isSpecialOrNormal $ bigList

  return (special, others)

（由于原始代码的Monad）

我猜 GHC 将运行第一个列表操作并将所有元素保留在内存中，以便第二个操作能够处理它们。

我的问题是我在处理较大的文件时遇到了空间泄漏。但我相信它应该能够在恒定空间中运行。有没有办法做到这一点？

更新 1

像这样写下来，解决这个问题的方法当然是改变两行的顺序。

但我的问题仍然存在：GHC 是否足够智能，可以在未在 monad 中完成时找出这种半并行处理？

4

1 回答 1

4

我不认为 GHC 足够聪明来合并这两个遍历，或者，通常情况下，GHC 可能足够聪明，但是在某些情况下你不想要这种行为，所以 GHC 不会这样做。

这是我将如何使用幺半群和foldMap.

import Data.Monoid
import Data.Foldable

首先，这是使用幺半群编写specialwith的方法。foldMapFirst

specialF :: a -> First a
specialF a = First $ if isSpecial a then Just a else Nothing

special :: [a] -> a
special as = let (First (Just s)) = foldMap specialF as in s

与 specialOrNormal 类似，使用列表 monoid。

specialOrNormalF :: a -> [a]
specialOrNormalF a = if isSpecialOrNormal a then [a] else []

specialOrNormal :: [a] -> [a]
specialOrNormal = foldMap specialOrNormalF

关于幺半群的一个巧妙之处在于，一个幺半群元组也是一个幺半群，这使得合并这些折叠变得容易：

findElements :: [a] -> (a, [a])
findElements bigList =
  let (First (Just s), son) = 
    foldMap (\a -> (specialF a, specialOrNormalF a)) bigList
  in (s, son)

如果你喜欢无点代码，你可以这样写：

findElements :: [a] -> (a, [a])
findElements = 
  first (fromJust . getFirst) . 
  foldMap 
    (   First . mfilter isSpecial . return 
    &&& mfilter isSpecialOrNormal . return
    )
于 2012-06-25T10:43:02.823 回答