Простите мой глупый вопрос, я новичок в Haskell.Понимание Haskell ленивая оценка
Я попытался в Haskell следующее:
sum [fib n| n <- [1..], (even (fib n) && fib n < 4000000)]
который занимает бесконечное время. Если я оставлю n <- [1..], решение приходит сразу.
Я думал, что это не должно иметь значения, потому что Хаскелл оценивает ленивый. Я неправильно понял ленивую оценку?
Обратите внимание, что
sum [ n | n <- [1..], n < 10 ]
не прекращается, а, так как он будет пытаться все возможные n сек на всякий случай еще один элемент оказывается «меньше 10», так что он входит в сумму ,
сравнения,
sum $ takeWhile (< 10) [ n | n <- [1..] ]
закончится, так как takeWhile отбросит остальную часть списка, как только найден элемент не удовлетворяет предикату <10.
Ваш список понимание
sum [fib n | n <- [1..], even (fib n) && fib n < 4000000]
эквивалентно выражению
sum $ map fib $ filter (\n -> even (fib n) && fib n < 4000000) [1..]
Глядя на определение filter:
filter :: (a -> Bool) -> [a] -> [a]
filter predicate [] = []
filter predicate (x:xs)
| predicate x = x : filter predicate xs
| otherwise = filter predicate xs
мы можем видеть, что он всегда будет исследовать каждый элемент в списке, пока он не достигнет конца списка. Список, предоставляемый для фильтрации в вашем выражении, равен [1..], что бесконечно. Это хорошо в Haskell, это просто означает, что фильтр никогда не завершится, если вы заставите оценку всего списка. Затем вы передаете его map fib, который также может обрабатывать бесконечные списки просто отлично, но что вам нужно, так это то, что вы передаете его sum, что требует, чтобы было добавлено конечное количество элементов.
Чтобы исправить это, как @chi указал, вы можете использовать вместо takeWhile:
sum $ map fib $ filter (\n -> even (fib n)) $ takeWhile (\n -> fib n < 4000000) [1..]
Хотя отмечу, что вы подаете fib 3 разное время в этом выражении. Что было бы лучше всего на map fib, тогда вам не придется снова применять его:
sum $ filter even $ takeWhile (< 4000000) $ map fib [1..]