Haskell ленивая оценка

Question

Если я позвоню по следующему коду Haskell

find_first_occurrence :: (Eq a) => a -> [a] -> Int
find_first_occurrence elem list = (snd . head) [x | x <- zip list [0..], fst x == elem]

с аргументами

'X' "abcdXkjdkljklfjdlfksjdljjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj"

сколько из сжатого списка [('a',0), ('b',1), ] будет построено?

UPDATE:

Я пытался запустить

find_first_occurrence 10 [1..]

и возвращает 9 почти мгновенно, так что я предполагаю, что он использует ленивую оценку по крайней мере для простых случаев? Ответ также вычисляется «мгновенно», когда я запускаю

let f n = 100 - n
find_first_occurrence 10 (map f [1..])

Answer 1

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

Длинный ответ: позвольте мне объяснить, почему с парой примеров:

ghci> head [a | (a,b) <- zip [1..] [1..], a > 10]
11

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

Теперь позвольте мне рассмотреть еще одну проблему:

ghci> find_first_occurrence 1 [0, 0, 1 `div` 0, 1]
*** Exception: divide by zero
ghci> find_first_occurrence 1 [0, 1, 1 `div` 0, 0]
1
it :: Int
(0.02 secs, 1577136 bytes)

Поскольку весь сжатый список не построен, haskell, очевидно, не будет даже оценивать каждое выражение, встречающееся в списке, поэтому, когда элемент находится перед div 1 0, функция корректно оценивается без возникновения исключений: деление на ноль не выполнялось происходят.

Answer 2

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

find_first_occurrence 'X' ("abcdX" ++ undefined)

Вы можете видеть, что он производит результат, что означает, что он даже не смотрит за пределы «X», которое он нашел (в противном случае он вызвал бы исключение). Очевидно, что сжатый список не может быть построен без просмотра исходного списка.

Другой (возможно, менее надежный) способ анализа вашей лени - использовать функцию trace из Debug.Trace:

> let find_first_occurrence elem list = (snd . head) [x | x <- map (\i -> trace (show i) i) $ zip list [0..], fst x == elem]
> find_first_occurrence 'X' "abcdXkjdkljklfjdlfksjdljjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj"

Отпечатки

('a',0)
('b',1)
('c',2)
('d',3)
('X',4)
4

Answer 3

Все это.

Поскольку StackOverflow не позволяет мне публиковать такой краткий ответ: вы не можете уйти с выполнением меньшего количества работы, чем просмотр всего списка, если то, что вы ищетене там.

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

('a',0):('b',1):('c',2):('d',3):('X',4):<thunk>

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