Что происходит в этой функции (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]. Однако это не правильный ответ.
Что на самом деле происходит с нс? Я изо всех сил пытаюсь понять...
5 ответов
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
....
Посмотрите, как мы определяем, какой будет следующий кортеж, и добавим два его элемента. Это позволяет нам определить следующий элемент.
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 и определение того, что первый конструктор (:) а затем решив оценить второй аргумент (:) как наш следующий шаг. Я буду использовать {...} представлять еще не оцененный Thunk.
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 образует тесную, умную маленькую петлю в себе.
В Хаскеле все лениво, так что пока 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, ...
И так далее.
Это эквивалентно ns = 0 : (zipWith (+) ns [1,3,...]), что может быть легче понять: k+1-й элемент - это k-й элемент плюс k-е нечетное число с соответствующими начальными условиями.
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