Ленивая оценка для функций генерации списков?

Question

Я сейчас читаю Программирование в Хаскелле, Грэхем Хаттоном.

В стр.40, тест игрушки на простоту представлена:

factors :: Int -> [Int] 
factors n = [x | x <- [1..n], n `mod` x == 0] 

prime :: Int -> Bool 
prime n = factors n == [1,n] 

Затем автор продолжает объяснять, как

«, решив, что число не простое число не требует функцию , чтобы произвести все его факторы, потому что при ленивой оценке получается результат False, как только будет произведен какой-либо другой фактор, кроме одного или самого номер «

Как кто-то, прибывающий с C и Java, я нахожу это шокирующим. Я бы ожидал, что вызов factors завершится первым, сохраните результат в стеке и передайте элемент управления вызывающей функции. Но, по-видимому, здесь выполняется совсем другая программа: должен быть цикл над пониманием списка в factors, и проверка равенства в prime проверяется на каждый новый элемент, добавленный в список факторов.

Как это возможно? Разве это не затрудняет рассуждение о порядке выполнения программы?

Answer 1

Вы найдете это "шокирующим", потому что вы этого не ожидаете. Как только вы привыкнете к этому ... ОК, на самом деле он все еще путешествует. Но через некоторое время вы в конце концов обманетесь вокруг.

Как работает Haskell: когда вы вызываете функцию, ничего не происходит! Звонок отмечен где-то, и все. Это занимает совсем немного времени. Ваш «результат» на самом деле просто «я должен вам», говоря компьютеру, какой код запускать, чтобы получить результат. Не весь результат, заметьте; просто первый шаг. Для чего-то вроде целого, есть is всего один шаг. Но для списка каждый элемент представляет собой отдельный шаг.

Позвольте мне показать вам простой пример:

print (take 10 ([1..] ++ [0])) 

Я говорил с C++ программист, который был «в шоке», что это работает. Несомненно, часть «++[0]» должна «найти конец списка», прежде чем она сможет добавить к ней нуль? Как этот код может завершиться за конечное время?

Это выглядит как это создает [1..] (в бесконечном списке), а затем ++[0] сканирование до конца этого списка и вставляет нуль, а затем take 10 обрезает покинуть только первые 10 элементов, а затем она печатает. То, что будет, конечно, занимает бесконечное время.

Итак, вот что такое на самом деле. Основная функция - take, так что мы начинаем. (Не ожидали, что ль?) Определение take что-то вроде этого:

take 0 ( _) = [] 
take n ( []) = [] 
take n (x:xs) = x : (take (n-1) xs) 

Так ясно 10!= 0, поэтому первая строка не применяется. Таким образом, применяется либо вторая, либо третья строка. Итак, теперь take смотрит на [1..] ++ [0], чтобы узнать, есть ли пустой список или непустой список.

Внешняя функция здесь (++). Это определение похоже на

( []) ++ ys = ys 
(x:xs) ++ ys = x : (xs ++ ys) 

Итак, нам нужно выяснить, какое уравнение применимо. Либо левый аргумент представляет собой пустой список (применяется одна строка), либо нет (применяется строка 2). Ну, поскольку [1..] - бесконечный список, строка вторая всегда. Таким образом, «результатом» [1..] ++ [0] является 1 : ([2..] ++ [0]). Как вы можете видеть, это не полностью выполнено; но он выполнен достаточно далеко, чтобы сказать, что это непустой список. Это все, о чем заботится take.

take 10 ([1..] ++ [0]) 
take 10 (1 : ([2..] ++ [0])) 
1 : take 9 ([2..] ++ [0]) 
1 : take 9 (2 : ([3..] ++ [0])) 
1 : 2 : take 8 ([3..] ++ [0]) 
1 : 2 : take 8 (3 : ([4..] ++ [0])) 
1 : 2 : 3 : take 7 ([4..] ++ [0]) 
... 
1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : take 0 ([11..] ++ [0]) 
1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : [] 

Вы видите, как это расслабляется?

---

Теперь, возвращаясь к вашему конкретному вопросу: оператор (==) занимает пару списков и итерацию по обоим из них, сравнивая их поэлементно, чтобы гарантировать, что они равны. Как только разница обнаруживается, он сразу же прекращает и возвращает ложь:

( []) == ( []) = True 
(x:xs) == (y:ys) = (x == y) && (xs == ys) 
( _) == ( _) = False 

Если мы теперь попробуйте, скажем, prime 6:

prime 6 
factors 6 == [1,6] 
??? == [1,6] 
1 : ??? == [1,6] 
??? == [6] 
2 : ??? == [6] 
False 

Answer 2

я остановлюсь на этом этапе:

Разве это не затрудняет рассуждение о порядке выполнения программы?

Да, но порядок оценки не имеет большого значения в чисто функциональном программировании. Например:

(1 * 3) + (4 * 5) 

Вопрос: какое умножение выполняется первым? A: нам все равно, результат тот же. Даже компиляторы C могут выбрать любой заказ здесь.

(f 1) + (f 2) 

Вопрос: какой вызов функции выполняется первым? A: нам все равно, результат тот же. Здесь компиляторы C также могут выбрать любой заказ. Однако в C функция f может иметь побочные эффекты, в результате чего сумма вышеуказанной суммы зависит от порядка оценки. В чистом функциональном программировании побочных эффектов нет, поэтому у нас действительно все равно.

Кроме того, лень позволяет расширить семантику расширения любого определения функции. Предположим, мы определим

f x = e -- e is an expression which can use x 

и мы называем f 2. Результат должен быть таким же, как e{2/x}, то есть как e, где каждое (свободное) возникновение x было заменено на 2. Это просто «раскрытие определения», как в математике.Например,

f x = x + 4 

-- f 2 ==> 2 + 4 ==> 6 

Однако предположим, что мы называем f (g 2) вместо этого. Лень делает этот эквивалент e{g 2/x}. Опять же, как и в математике. Например:

f x = 42 
g n = g (n + 1) -- infinite recursion 

тогда мы еще уже f (g 2) = 42 {g 2/x} = 42 так x не используется. Нам не нужно беспокоиться, если определено g 2 (зацикливание навсегда). Определение разворачивается всегда работает.

Это действительно делает проще, чтобы узнать о поведении программы.

Есть некоторые недостатки лень. Главное, что, хотя семантика программы (возможно) проще, оценка производительности программы сложнее. Чтобы оценить производительность, вы должны понимать больше, чем конечный результат: вам нужно иметь модель всех промежуточных шагов, ведущих к такому результату. Особенно в коде высокого уровня, или когда какая-то умная оптимизация начинается, это требует некоторого опыта в том, как работает среда выполнения.

Answer 3

Разве это не затрудняет рассуждение о порядке выполнения программы?

Возможно, по крайней мере, для тех, кто исходит из процедурной/OO-парадигмы. Я много сделал с итераторами и функциональным программированием на других языках с нетерпением оценки, и для меня ленивая стратегия оценки не является основной проблемой обучения Haskell. (Сколько раз вы хотели, чтобы ваш оператор Java-журнала даже не получал данные для сообщения до тех пор, пока не решился на его регистрацию?)

Подумайте обо всей обработке списка в Haskell, как будто она была скомпилирована в итератор реализации под обложками. Если вы делали это на Java с возможными факторами n, указанными в качестве Iterator<Integer>, не хотите ли вы остановить, как только вы нашли тот, который не был 1 или n? И если это так, на самом деле не имеет значения, бесконечен ли итератор или нет!

Когда вы доберетесь до него, заказ исполнения не имеет большого значения. То, что вы действительно заботитесь о:

• Корректность результата
• Своевременное прекращение
• Относительный порядок любых побочных эффектов

Теперь, если у вас есть «чисто функциональной» программы , побочных эффектов нет. Но когда это происходит? Практически все, что может быть полезно за пределами прямого хруста числа/строки и метакода (т.е. функций более высокого порядка), будет иметь побочные эффекты.

К счастью (или к сожалению, в зависимости от того, кого вы спрашиваете), мы имеем monad как шаблон проектирования в Haskell, который служит цели (помимо всего прочего) управления порядком оценки, и, следовательно, побочных эффектов.

Но даже не изучая монады и все эти вещи, на самом деле это примерно так же легко рассуждать о порядке исполнения, как в процедурных языках. Вам просто нужно привыкнуть к этому.