Почему следующий код Haskell не заканчивается:
foldr (||) True $ repeat False -- never terminates
когда что-то вроде этого:
foldr (||) False $ repeat True -- => True
Для меня это второе выражение, которое выглядит более неприятным, чем не завершение. Что не так с моим взглядом на ленивую оценку Хаскелла?
Я думаю, что ваше понимание лени верное, но не для foldr. Давайте рассмотрим его спецификацию"
foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
Затем посмотрите на свое выражение
foldr (||) True $ repeat False -- never terminates
Как вы видите, True (z), который мы "ищем" для получения || для завершения, не будет достигнута до тех пор, пока не будет уничтожен весь список. И это не произойдет, поскольку список бесконечен.
Это также должно объяснять фактически завершающий пример.
Первый расширяется до False || (False || (False || ...)), а второй - до True || (True || (True || ...)). Второй аргумент foldr - красная селедка - он появляется в самом внутреннем приложении ||, а не в самом внешнем, поэтому его никогда нельзя достичь.
Проблема довольно очевидна, если вы разворачиваете foldr вручную:
foldr (||) True $ repeat False == False || (False || (False (False || ... True)))
Итак, чтобы получить окончательный False, код должен был оценить список до его (неэксентирующего) конца. Во втором примере вы повторяете True, поэтому возможно короткое замыкание. Не ожидайте магии от ленивой оценки!
Еще одно понимание для вас состоит в том, что || не коммутативен в Haskell, он предвзято:
Prelude> undefined || True
*** Exception: Prelude.undefined
Prelude> True || undefined
True
Поэтому, в отличие от математики, || и flip (||) - разные функции. Например. сравнить
foldr (||) False $ repeat True и foldr (flip (||)) False $ repeat True
Первый заканчивается, но последний не делает.