3

GHCは、「半並列」のリストに対して複数の操作を実行するのに十分インテリジェントですか？

この（簡略化された）コードを考えてみましょう。

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

  return (special, others)

（元のコードによるモナド）

GHCは最初のリスト操作を実行し、2番目の操作がそれらを処理できるように、すべての要素をメモリに保持すると思います。

私の問題は、大きなファイルを処理するときにスペースリークが発生していることです。しかし、私はそれが一定の空間で実行できるはずだと信じています。これを達成する方法はありますか？

アップデート1

このように書き留めておけば、もちろんこの問題の解決策は2行の順序を変更することです。

しかし、私の質問は残っています。GHCは、モナドで実行されていない場合に、この半並列処理を理解するのに十分インテリジェントですか？

4

1 に答える 1

4

GHCは、これら2つのトラバーサルをマージするほどスマートではないと思います。または、通常の場合、GHCは十分にスマートである可能性がありますが、この動作を望まない場合があるため、GHCはそれを行いません。

これが、モノイドとを使用して、私がそれを行う方法ですfoldMap。

import Data.Monoid
import Data.Foldable

まず、モノイドspecialをfoldMap使って、で書く方法を説明します。First

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

そして、list monoidを使用して、specialOrNormalについても同様です。

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

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

モノイドの優れた点の1つは、モノイドのタプルもモノイドであるため、これらのフォールドを簡単にマージできることです。

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 に答える