Сколько раз здесь вычисляется (+ 1)?

Question

На экзамене по функциональному программированию у меня возник следующий вопрос:

Сколько раз (+ 1) функция вычисляется в следующем коде?

(map (+ 1) [1 .. 10]) !! 5

, где указатель является функциейопределяется следующим образом:

(h:_) !! 0 = h
(_:t) !! x = t !! (x-1)

Я бы сказал, 6 раз, но правильный ответ, кажется, 1, и я не могу понять, почему.Я не смог найти достаточно хорошего объяснения ленивой оценки в Haskell, поэтому я хотел бы знать, каков правильный ответ и почему.Заранее спасибо!

Answer 1

много раз (+ 1) функция вычисляется в следующем коде?

Она рассчитывается только один раз .map не заставляет вычислять f x<sub>i</sub> для элементов в списке результатов.Эти вычисления откладываются (как и все остальное в Haskell), только когда нам нужно вычислить стоимость определенного элемента, мы делаем это.

map указано в главе 9 Haskell'10 сообщают как:

-- Map and append  
map :: (a -> b) -> [a] -> [b]  
map f []     = []  
map f (x:xs) = f x : map f xs

Здесь нет seq, паттернов взрыва и т. Д., Чтобы принудительно оценить f x, поэтому функция mapдействительно «выдаст» f x, но без оценки f x будет отложено до необходимости (и может случиться, что мы не заинтересованы в некоторых из этих значений и, следовательно, можем сохранитьнекоторые циклы процессора).

Мы можем посмотреть, как Haskell оценит это:

   (!!) (map (+ 1) [1 .. 10]) 5
-> (!!) ((+1) 1 : map (+1) [2..10]) 5
-> (!!) (map (+1) [2..10]) 4
-> (!!) ((+1) 1 : map (+1) [3..10]) 4
-> (!!) (map (+1) [3..10]) 3
-> (!!) ((+1) 1 : map (+1) [4..10]) 3
-> (!!) (map (+1) [4..10]) 2
-> (!!) ((+1) 1 : map (+1) [5..10]) 2
-> (!!) (map (+1) [5..10]) 1
-> (!!) ((+1) 1 : map (+1) [6..10]) 1
-> (!!) (map (+1) [6..10]) 0
-> (!!) ((+1) 6 : map (+1) [7..10]) 0
-> (+1) 6
-> 7

Это потому, что map f [x1, x2, ..., xn] в конечном итоге отображается в список [f x1, f x2, ..., f xn], но это так не вычисляет f x<sub>i</sub> элементов, это вычисление откладывается до тех пор, пока нам на самом деле не понадобится значение в этом списке, и что-то с ним сделаем (как, например, его печать).

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

Answer 2

Давайте проверим это, делая что-то ужасное.Для этого вам нужно будет импортировать модуль Debug.Trace.

ghci> (map (\x -> trace "Performing..." (x + 1)) [1..10]) !! 5

Теперь мы получим абсолютно безопасное действие IO, которое происходит каждый раз, когда вызывается лямбда-выражение.Когда мы запускаем это в GHCi, мы получаем

Performing
7

Так только один раз.

В качестве проверки работоспособности мы можем удалить бит !! 5.

ghci> map (\x -> trace "Performing..." (x + 1)) [1..10]
[Performing
2,Performing
3,Performing
4,Performing
5,Performing
6,Performing
7,Performing
8,Performing
9,Performing
10,Performing
11]

Так что это определенно происходит 10 раз, когда мы просим весь список.