Функцията mapAndSum в кодовия блок докрай комбинира map и sum (няма значение, че в главната функция е приложено друго sum, то просто служи, за да направи изхода компактен). map се изчислява лениво, докато sum се изчислява с помощта на натрупващ се параметър. Идеята е, че резултатът от map може да бъде консумиран, без изобщо да има пълния списък в паметта, и (само) след това sum е достъпен "безплатно". Основната функция показва, че сме имали проблем с неопровержими модели при извикване на 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 (сравнете "лошо" срещу "добро2"). Между другото, намирането на това ни отне значително време..!
Това, което не разбираме, е две:
Защо
mapAndSumработи на първо място? Той също така използва неопровержим модел, така че трябва също да пази целия списък в паметта, но очевидно не го прави. И преобразуването наletвcaseби накарало функцията да се държи напълно нелениво (до степен, че стекът препълва; не е предназначена игра на думи).Разгледахме „основния“ код, генериран от GHC, но доколкото можехме да го интерпретираме, той всъщност съдържаше същия превод на
letкато този по-горе. Така че тук няма представа и вместо това има повече объркване.Защо "лошо?" работи, когато оптимизацията е изключена, но не и когато е включена?
Една забележка относно нашето действително приложение: искаме да постигнем поточна обработка (преобразуване на формат) на голям текстов файл, като същевременно натрупваме някаква стойност, която след това се записва в отделен файл. Както беше посочено, успяхме, но двата въпроса остават и отговорите може да подобрят разбирането ни за 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."
mapAnsSumфункция може да бъде подобрена чрез използване наmapAccumLот Data.Traversable. - person Laar schedule 24.07.2012