mapAndSum
以下のコードブロックの関数は、以下のすべての機能map
を組み合わせたものですsum
(main関数に別の関数が適用されていることを気にしないsum
でください。これは、出力をコンパクトにするためだけに役立ちます)。はmap
遅延してsum
計算されますが、は累積パラメータを使用して計算されます。アイデアはmap
、メモリに完全なリストがなくても結果を消費でき、その後(のみ)sum
「無料」で利用できるようにすることです。main関数は、を呼び出すときに反駁できないパターンに問題があったことを示していmapAndSum
ます。この問題について説明させてください。
Haskell標準によると、反駁できないパターンの例let (xs, s) = mapAndSum ... in print xs >> print s
は次のように翻訳されます。
(\ v -> print (case v of { (xs, s) -> xs })
>> print (case v of { (xs, s) -> s }))
$ mapAndSum ...
したがって、両方のprint
呼び出しはペア全体への参照を運び、リスト全体がメモリに保持されます。
私たち(私の同僚のToni Dietzeと私)は、明示的なcase
ステートメントを使用してこれを解決しました(「bad」と「good2」を比較してください)。ところで、これを見つけるのにかなりの時間がかかりました..!
さて、私たちが理解していないのは2つあります。
mapAndSum
そもそもなぜ機能するのですか?また、反駁できないパターンを使用しているため、リスト全体をメモリに保持する必要がありますが、明らかにそうではありません。そして、をに変換するlet
とcase
、関数は完全に怠惰な動作になります(スタックがオーバーフローするまで、しゃれは意図されていません)。GHCによって生成された「コア」コードを調べましたが、それを解釈できる限り、実際には上記と同じ翻訳が含ま
let
れていました。したがって、ここでは手がかりはなく、代わりにさらに混乱します。なぜ「悪い」のですか?最適化がオフの場合は機能しますが、オンの場合は機能しませんか?
実際のアプリケーションに関する1つの注意点は、大きなテキストファイルのストリーム処理(フォーマット変換)を実現すると同時に、別のファイルに書き込まれる値を蓄積することです。示されているように、私たちは成功しましたが、2つの質問が残っており、回答により、今後のタスクと問題に対するGHCの理解が向上する可能性があります。
ありがとうございました!
{-# LANGUAGE BangPatterns #-}
-- Tested with The Glorious Glasgow Haskell Compilation System, version 7.4.2.
module Main where
import Control.Arrow (first)
import Data.List (foldl')
import System.Environment (getArgs)
mapAndSum :: Num a => (a -> b) -> [a] -> ([b], a)
mapAndSum f = go 0
where go !s (x : xs) = let (xs', s') = go (s + x) xs in (f x : xs', s')
-- ^ I have no idea why it works here. (TD)
go !s [] = ([], s)
main :: IO ()
main = do
let foo = mapAndSum (^ (2 :: Integer)) [1 .. 1000000 :: Integer]
let sum' = foldl' (+) 0
args <- getArgs
case args of
["bad" ] -> let (xs, s) = foo in print (sum xs) >> print s
["bad?"] -> print $ first sum' $ foo
-- ^ Without ghc's optimizer, this version is as memory
-- efficient as the “good” versions
-- With optimization “bad?” is as bad as “bad”. Why? (TD)
["good1"] -> print $ first' sum' $ foo
where first' g (x, y) = (g x, y)
["good2"] -> case foo of
(xs, s) -> print (sum' xs) >> print s
["good3"] -> (\ (xs, s) -> print (sum' xs) >> print s) $ foo
_ -> error "Sorry, I do not understand."