Лень и хвостовая рекурсия в Haskell, почему это отказывает?
попытайтесь использовать сброс css как , eric Мейер сбросил или , YUI сбрасывают . поможет только никакой простой способ или лучший способ заставить вещи выглядеть идентичными в каждом браузере
3 ответа
Я подробно написано об этом:
Во-первых, да, если вы хотите требовать строгой оценки аккумуляторов, используйте 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' - это оболочка над строгим атомарным типом 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 выше.
Функция 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 s программа выполняется нормально, без использования чрезмерного количества памяти.
Другим решением проблемы было бы просто включить оптимизацию в GHC при компиляции программы ( -O или -O2 ). Оптимизатор распознает ненужную лень и создает код, который не выделяет ненужную память.
Вы правы в своем понимании, что seq s (s + x) принудительно вычисляет s . Но это не заставляет s + x , поэтому вы все еще накапливаете thunks.
Используя $! , вы можете принудительно вычислить добавление (два раза, для обоих аргументов). Это дает тот же эффект, что и при использовании паттернов взрыва:
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)) , что явно неверно.