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

Ответ 1

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

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

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

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

Я говорил с программистом на С++, который был "шокирован", что это работает. Конечно, часть "++[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 : []

Вы видите, как это происходит?

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

(  []) == (  []) = 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

Ответ 2

Я остановлюсь на этом:

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

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

(1 * 3) + (4 * 5)

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

(f 1) + (f 2)

Q: какой вызов функции выполняется первым? 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 (зацикливание навсегда). Развертывание определения всегда работает.

Это фактически упрощает рассуждение о поведении программы.

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

Ответ 3

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

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

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

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

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

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

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

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