Что происходит в этой функции (haskell)?

Ответ 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-е нечетное число с соответствующими начальными условиями.