Почему эта функция рекурсивного отображения применяется только к двум последним элементам в списке?

Question

Вот эта проблема: Каковы первые 8 элементов в следующем списке?

mystery = 0 : 10 : (map(+1)mystery)

Ответ [0,10,1,11,2,12,3,13...]

Но, по моему мнению, ответ должен быть [0,10,1,11,1,11,2,12].Следующие шаги показывают, почему:

1) Нам дано; list [0,10], поэтому после применения функции в первый раз у нас есть список [0,10,1, 11] 2) Теперь у нас есть список [0,10,1,11] такпосле повторного применения функции результирующий список должен выглядеть так: [0,10,1,11,1,11,2,12]

Очевидно, что это не так.Кто-нибудь может объяснить, почему?

Answer 1

Прежде чем углубиться в определение mystery, давайте взглянем на один из законов map подчиняется:

map f (map g xs) == map (f . g) xs

Довольно неформальному доказательству этого закона легко следовать:

map f (map g [x1, x2, ..., xn]) == map f [g x1, g x2, ..., g xn]
                                == [f (g x1), f (g x2), ..., f (g xn)]
                                == [(f.g) x1, (f.g) x2, ..., (f.g) xn]
                                == map (f.g) [x1, x2, ..., xn]

---

Имея это в виду, давайте расширим mystery шаг за шагом:

mystery == 0 : 10 : map (+1) mystery
        -- by definition of mystery
        == 0 : 10 : map (+1) (0 : 10 : map (+1) mystery)
        -- by definition of map and the fact that  0 + 1 == 1
        == 0 : 10 : 1 : map (+1) (10 : map (+1) mystery)
        -- by definition of map and the fact that 10 + 1 == 11
        == 0 : 10 : 1 : 11 : map (+1) (map (+1) mystery)
        -- using the law above, and the fact that (+1) . (+1) == (+2)
        == 0 : 10 : 1 : 11 : map (+2) mystery
        == 0 : 10 : 1 : 11 : map (+2) (0 : 10 : map (+1) mystery)
        == 0 : 10 : 1 : 11 : 2 : map (+2) (10 : map (+1) mystery)
        == 0 : 10 : 1 : 11 : 2 : 12 : map (+2) (map (+1) mystery)
        == 0 : 10 : 1 : 11 : 2 : 12 : map (+3) mystery
        -- etc

Вы не начинаете с конечного списка [0, 10];вы начинаете с бесконечного списка, который начинается с 0 и 10, а остальные элементы определены рекурсивно.

В некотором смысле для списка нет закрытой формы, но это не имеет значения;лень означает, что вы применяете map к mystery только по мере необходимости, чтобы получить запрошенные предметы.Например, ни head mystery, ни head (tail mystery) никогда не нужно оценивать вызов на map, а head (tail (tail mystery)) нужно только сопоставить (+1) с head mystery, а не весь бесконечный список.

Лень стирает различие между списком и алгоритмом для вычисления списка.

Answer 2

Давайте просто проработаем его, используя рекурсивное определение map:

map _ [] = []
map f (x:xs) = f x : map f xs

Поскольку у нас есть

mystery = 0:10:(map (+1) mystery)

, мы уже знаем, что

mystery = [0, 10, ...]

и ... означает map (+1) mystery.Итак, давайте воспользуемся приведенным выше определением для его вычисления.

Список, к которому мы его применяем, явно не пустой - он начинается с 0 и 10. Поэтому мы используем вторую строку с x как 0и xs как 10:(map (+1) mystery):

map (+1) mystery = 1:(map (+1) (10:(map (+1) mystery)))

или, снова используя формулу для первого уровня вложенности:

map (+1) mystery = 1:11:(map (+1) (map (+1) mystery))

Итак, возвращаясь к самому mystery,теперь мы знаем его первые 4 элемента:

mystery = [0, 10, 1, 11, ...]

, а ... обозначает содержимое map (+1) (map (+1) mystery).То есть, исходя из приведенного выше результата:

map (+1) (1:11:(map (+1) (map (+1) mystery)))

Я избавлю вас от деталей оценки здесь, потому что теперь должно быть ясно, что происходит: первые 2 элемента (которые будут 5-ми 6-е в mystery) будет 2 и 12, а остальные будут map (+1) ((map (+1) (map (+1) mystery))).Который, точно так же, начнёт с 3 и 13. И так далее, насколько вы могли бы рассчитывать.

Answer 3

Поскольку

mystery = 0 : 10 : map (+1) mystery

по определениям (!!) и (:) и map, это тот случай, когда

mystery !! 0 = 0          -- pseudocode
mystery !! 1 = 10
mystery !! n | n > 1
             = (0 : 10 : map (+1) mystery) !! n
             = (10 : map (+1) mystery) !! (n-1)
             = (map (1+) mystery) !! (n-2)
             = 1 + (mystery !! (n-2))

, и есть ваш ответ.

Иллюстрация:

--         0   1  2   3  4   5  6        -- n
mystery = [0, 10, 1, 11, 2, 12, 3, ...
--               /   /  /   /  /
--               0   1  2   3  4         -- n-2
--              [0, 10, 1, 11, 2, ...

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

Таким образом, другой способ записать то же самое, сделав явное сопряжение (нет zipping ), - это

mystery = 0 : 10 : zipWith (+) mystery
                              (repeat 1)

Переведенный в императивный псевдокод, программа

main = print mystery

фактически совпадает с

main :
    a = 0
    b = 10
    print "[" 
    while( True ) :
       print a , 
       print b ,
       a += 1
       b += 1

---

A принципиальным подход к решению таких проблем - назвать все вашивременные лица.Тогда тайна исчезает:

mystery = 0  : 10 : map (+1) mystery
        = x0 : t1 
  where 
  x0 = 0
  t1 = 10 : map (+1) mystery
     = x1 : t2
    where
    x1 = 10
    t2 = map (+1) mystery
       = map (+1) (x0 : t1)
       = x0+1 : map (1+) t1
       = x2 : t3
      where
      x2 = x0+1 = 0+1 = 1
      t3 = map (1+) t1 = map (1+) (x1 : t2)
         = x1+1 : map (1+) t2
         = x3 : t4
        where
        ....

Ни в коем случае мы не получим никакой функции, кроме функции (1+) в этом процессе сокращения, или более одной из них.

Все, что мы получаем, это x<sub><b>n</b></sub> := 1 + x<sub><b>n-2</b></sub>, многократно, для всех n выше 1.