Что происходит в этой функции (haskell)?
У меня есть эта функция haskell, которую я не совсем понимаю.
ns :: [Integer]
ns = 0 : [n+k | (n, k) <- zip ns [1,3..]]
Меня попросят "взять 3 нс".
Я думал, что ns был постоянным, поэтому он будет только зацикливаться на первом элементе списка, давая (0,1). Затем, когда добавляется ответ 1. Затем он говорит: "возьмите 3 нс", поэтому я закрепил 0 с помощью первых 5 элементов списка, указав... (0,1), (0,3), (0,5), а затем при добавлении я получаю окончательный ответ [1,3,5]. Однако это не правильный ответ.
Что на самом деле происходит с ns? Я пытаюсь понять...
Ответы
Ответ 1
haskell ленив, поэтому вы можете иметь рекурсивные определения. Здесь он изложен.
ns = 0 : something
(n,k) <- zip (0 : something ) [1,3,5,7...]
(n,k) <- [(0,1) : something )
ns = 0 : 1 : something
(n,k) <- zip ( 0 : 1 : something ) [3,5,7...]
(n,k) <- (0,1) : (1,3) : something
ns = 0 : 1 : 4 : something
(n,k) <- zip ( 0 : 1 : 4 : something ) [5,7...]
(n,k) <- (0,1) : (1,3) : (4,5) : something
ns = 0 : 1 : 4 : 9 : something
....
Посмотрите, как мы определяем, что следующий кортеж затем добавляет два его элемента. Это позволяет нам определить следующий элемент.
Ответ 2
Все в Haskell лениво, поэтому пока ns является постоянным, это не означает, что элементы в списке не могут быть "добавлены" (или, точнее, "вычисленны" ) в более позднее время. Кроме того, поскольку ns рекурсивно определен, значения, которые появляются позже в списке, могут зависеть от значений, которые появляются ранее в списке.
Переходим к этому шаг за шагом.
Сначала мы знаем, что ns начинается с 0, поэтому пока ns выглядит следующим образом:
ns: 0, ?, ?, ...
Итак, что в первом вопросительном знаке? Согласно вашей функции, n + k, где n - первый элемент в ns, а k - первый элемент в [1, 3..]. Итак, n = 0, k = 1 и n + k = 1.
ns: 0, 1, ?, ...
Далее, следующий элемент также n + k, где мы используем второй элемент ns и [1, 3...]. Теперь мы знаем, что второй элемент ns равен 1, поэтому n = 1, k = 3 и n + k = 4.
ns: 0, 1, 4, ...
И так далее.
Ответ 3
Haskell оценивает вещи лениво, поэтому он будет вычислять точно столько, сколько нужно. Это означает, что нам нужно как-то получить значения ns, чтобы увидеть, как он вычисляется.
head ns
head (0 : ...)
0
Ясно, что head не заставляет достаточно ничего для чего-то интересного, но вы уже можете видеть, что интересная часть ns просто отбрасывается. Этот эффект идет дальше, когда мы просим больше, например, печатать каждый элемент. Пусть просто заставляют каждый элемент один за другим видеть шаблон. Во-первых, замените понимание списка одним эквивалентным вызовом функции
zipWith f [] _ = []
zipWith f _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
ns = 0 : zipwith (+) ns [1,3..]
Теперь мы можем оценивать элементы ns один за другим. Действительно, чтобы быть более подробным, мы оцениваем ns и определяем, что первый конструктор (:), а затем решил оценить второй аргумент (:) как наш следующий шаг. Я буду использовать {...} для представления еще не оцененного текста.
ns
{ 0 } : zipWith (+) ns [1,3...]
{ 0 } : zipWith (+) ({ 0 } : { ... }) [1,3...] -- notice the { 0 } thunk gets evaluated
0 : { 0 + 1 } : zipWith f { ... } [3,5...]
0 : 1 : { 1 + 3 } : zipWith f { ... } [5,7...]
0 : 1 : 4 : { 4 + 5 } : zipWith f { ... } [7,9...]
Важно отметить, что поскольку ns оценивается только по частям, он никогда не требует знать то, что еще не было вычислено. Таким образом, ns образует жесткий, умный маленький цикл сам по себе.
Ответ 4
ns :: [Integer]
ns = 0 : [n+k | (n, k) <- zip ns [1,3..]]
это корекурсивное определение данных. ns - это константа, список, но она "сглаживается" путем доступа, поскольку Haskell ленив.
Иллюстрация:
1 n1 n2 n3 n4 n5 ... -- the list ns, [n1,n2,n3,...],
2 0 1 4 ... -- starts with 0
3 -----------------
4 1 3 5 7 9 -- [1,3..]
5 -----------------
6 1 4 ... -- sum the lines 2 and 4 pairwise, from left to right, and
7 n2 n3 n4 n5 ... -- store the results starting at (tail ns), i.e. from n2
Мы можем точно видеть, каким образом доступ заставляет список ns существовать шаг за шагом, например. после print $ take 4 ns, путем присвоения имен промежуточным объектам:
ns :: [Integer]
ns = 0 : [n+k | (n, k) <- zip ns [1,3..]]
ns = 0 : tail1
tail1 = [n+k | (n, k) <- zip ns [1,3..]]
= [n+k | (n, k) <- zip (0 : tail1) [1,3..]]
= [n+k | (n, k) <- (0,1) : zip tail1 [3,5..]]
= 1 : [n+k | (n, k) <- zip tail1 [3,5..]]
= 1 : tail2
tail2 = [n+k | (n, k) <- zip (1 : tail2) [3,5..]]
= [n+k | (n, k) <- (1,3) : zip tail2 [5,7..]]
= 4 : tail3
tail3 = [n+k | (n, k) <- zip (4 : tail3) [5,7..]]
= 9 : tail4
tail4 = [n+k | (n, k) <- zip (9 : tail4) [7,9..]]
------
ns = 0 : 1 : 4 : 9 : tail4
Ответ 5
Это эквивалентно ns = 0 : (zipWith (+) ns [1,3,...]), что может быть проще понять: k + 1-й элемент - k-й элемент плюс k-е нечетное число с соответствующими начальными условиями.
