Лень и хвост рекурсии в Haskell, почему это грохот?
У меня есть эта довольно простая функция для вычисления среднего числа элементов большого списка, используя два аккумулятора для хранения суммы до сих пор и подсчета до сих пор:
mean = go 0 0
where
go s l [] = s / fromIntegral l
go s l (x:xs) = go (s+x) (l+1) xs
main = do
putStrLn (show (mean [0..10000000]))
Теперь, на строгом языке, это будет хвост-рекурсивным, и проблем не будет. Однако, поскольку Haskell ленив, мой поисковик привел меня к пониманию того, что (s + x) и (l + 1) будут переданы по рекурсии в виде thunks. Таким образом, все это сбой и ожоги:
Stack space overflow: current size 8388608 bytes.
После дальнейшего поиска в Google я нашел seq и $!. Кажется, что я не понимаю, потому что все мои попытки использовать их в этом контексте оказались бесполезными, а сообщения об ошибках говорили о бесконечных типах.
Наконец, я нашел -XBangPatterns, который решает все это путем изменения рекурсивного вызова:
go !s !l (x:xs) = go (s+x) (l+1) xs
Но я не доволен этим, так как -XBangPatterns в настоящее время является расширением. Я хотел бы знать, как сделать оценку строгой без использования -XBangPatterns. (И, может быть, тоже научитесь!)
Просто, чтобы вы поняли мое отсутствие понимания, вот что я пробовал (единственная попытка скомпилировать, то есть):
go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs
Из того, что я мог понять, seq должен здесь заставить оценивать аргументы s и l, тем самым избегая проблемы, вызванной thunks. Но я все равно получаю переполнение стека.
Ответы
Ответ 1
Я подробно писал об этом:
Во-первых, да, если вы хотите потребовать строгой оценки аккумуляторов, используйте seq и оставайтесь в Haskell 98:
mean = go 0 0
where
go s l [] = s / fromIntegral l
go s l (x:xs) = s `seq` l `seq`
go (s+x) (l+1) xs
main = print $ mean [0..10000000]
*Main> main
5000000.0
Во-вторых: анализ строгости начнется, если вы дадите аннотации некоторого типа и скомпилируйте с помощью -O2:
mean :: [Double] -> Double
mean = go 0 0
where
go :: Double -> Int -> [Double] -> Double
go s l [] = s / fromIntegral l
go s l (x:xs) = go (s+x) (l+1) xs
main = print $ mean [0..10000000]
$ ghc -O2 --make A.hs
[1 of 1] Compiling Main ( A.hs, A.o )
Linking A ...
$ time ./A
5000000.0
./A 0.46s user 0.01s system 99% cpu 0.470 total
Потому что "Двойной" является оболочкой над строгим атомным типом Double #, с оптимизацией и точным типом, GHC проводит анализ строгости и сообщает, что строгая версия будет в порядке.
import Data.Array.Vector
main = print (mean (enumFromToFracU 1 10000000))
data Pair = Pair !Int !Double
mean :: UArr Double -> Double
mean xs = s / fromIntegral n
where
Pair n s = foldlU k (Pair 0 0) xs
k (Pair n s) x = Pair (n+1) (s+x)
$ ghc -O2 --make A.hs -funbox-strict-fields
[1 of 1] Compiling Main ( A.hs, A.o )
Linking A ...
$ time ./A
5000000.5
./A 0.03s user 0.00s system 96% cpu 0.038 total
Как описано в главе RWH выше.
Ответ 2
Функция seq принудительно оценивает первый параметр после вызова функции. Когда вы передаете seq s (s+x) в качестве параметра, функция seq не вызывается немедленно, потому что нет необходимости оценивать значение этого параметра. Вы хотите, чтобы вызов seq оценивался до рекурсивного вызова, так что это, в свою очередь, может заставить его параметр быть оцененным.
Обычно это делается ссылкой:
go s l (x:xs) = s `seq` l `seq` go (s+x) (l+1) xs
Это синтаксическая вариация seq s (seq l (go (s+x) (l+1) xs)). Здесь вызовы seq являются внешними вызовами функций в выражении. Из-за лени Haskell это заставляет их сначала оценивать: seq вызывается с еще невыплаченными параметрами s и seq l (go (s+x) (l+1) xs), оценка параметров откладывается до точки, где кто-то действительно пытается получить доступ к своим значениям.
Теперь seq может заставить свой первый параметр быть оценен перед возвратом остальной части выражения. Тогда следующим шагом в оценке будет второй seq. Если вызовы на seq где-то захоронены каким-то параметром, они могут не выполняться в течение длительного времени, превзойдя их цель.
С измененными позициями seq программа выполняет штраф, не используя чрезмерные объемы памяти.
Другим решением проблемы было бы просто включить оптимизацию в GHC при компиляции программы (-O или -O2). Оптимизатор распознает неприемлемую лень и создает код, который не выделяет ненужную память.
Ответ 3
Вы правы в своем понимании, что seq s (s+x) заставляет оценивать s. Но он не заставляет s+x, поэтому вы все еще создаете громкие трюки.
Используя $!, вы можете принудительно выполнить оценку добавления (два раза для обоих аргументов). Это обеспечивает тот же эффект, что и при использовании шаблонов взлома:
mean = go 0 0
where
go s l [] = s / fromIntegral l
go s l (x:xs) = ((go $! s+x) $! l+1) xs
Использование функции $! приведет к переводу go $! (s+x) в эквивалент:
let y = s+x
in seq y (go y)
Таким образом, y сначала принудительно переходит в слабую гласную нормальную форму, что означает, что применяется внешняя функция. В случае y самая внешняя функция +, поэтому y полностью вычисляется до числа перед передачей в go.
О, и вы, вероятно, получили сообщение об ошибке бесконечного типа, потому что у вас не было круглых скобок в нужном месте. У меня такая же ошибка, когда я впервые написал вашу программу: -)
Поскольку оператор $! является правильным ассоциативным, без круглой скобки go $! (s+x) $! (l+1) означает то же самое, что: go $! ((s+x) $! (l+1)), что, очевидно, неверно.
