Понимание фибоначчи Хаскелла

Question

fibs :: [Int]
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

Это генерирует последовательность Фибоначчи.

Я понимаю поведение охранников :, zip и tail, но я не понимаю <-. Что он здесь делает?

Answer 1

Из-за голосов, я сделал свой комментарий в ответ.

То, что вы видите, не охрана, а понимание списка . Для начала подумайте об этом как о способе обозначения математического набора, например, A = {x | x элемент N}, что означает что-то вроде: множество A - это множество всех натуральных чисел. В понимании списка это будет [x | x <- [1..] ].

Вы также можете использовать ограничения на свои номера: [x | x <- [1..], x `mod` 2 == 0 ] и многое другое.

Существует множество хороших туториалов по Haskell, которые охватывают понимание списка и даже вопрос StackOverflow относительно ресурсов Haskell.

Answer 2

Единственная хитрая вещь - zip fibs (tail fibs). zip просто создает попарный список из каждого аргумента. Так что если у вас есть два списка, как это:

[ 1, 2, 3, 4 ]
[ "a", "b", "c", "d" ]

Застегнув их, получим:

[ (1,"a"), (2,"b"), (3,"c"), (4,"d") ]

Стрелка влево (назначение в шаблон деструктуризации) просто извлекает парные элементы, чтобы их можно было добавлять вместе. Сжаты два списка: fibs и (tail fibs) - другими словами, последовательность Фибоначчи и последовательность Фибоначчи, смещенная на 1 элемент. Haskell оценивается лениво, поэтому он может вычислить список на сколько угодно элементов. Это касается и почтового индекса.

Answer 3

Давайте расширим это.

zip создает пары из содержимого двух списков. Итак, первая пара zip fibs (tail fibs) дает нам (0, 1), что в сумме составляет 1. Итак, теперь список равен [0,1,1]. Теперь мы знаем три элемента в списке, поэтому понимание списка можно продолжить, взяв следующий элемент из списка и следующий элемент из хвоста, что дает (1,1) - сложить вместе, получив 2. Затем мы получим следующую пару это (1,2), что делает следующий номер в последовательности 3. Это может продолжаться бесконечно, так как понимание всегда обеспечит достаточное количество элементов.

Answer 4

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

fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]
     = 0 : 1 : [ a + b | (a, b) <- zip [0, 1, ??] (tail [0, 1, ??])]

Здесь ?? - это часть, которая еще не была оценена. Мы заполним его по мере продвижения.

     = 0 : 1 : [ a + b | (a, b) <- zip [0, 1, ??] [1, ??])]
     = 0 : 1 : [ a + b | (a, b) <- (0, 1) : zip [1, ??] [??]]

Обратите внимание, что я отказываюсь от оценки zip, так как ее определение здесь не приводится, а детали на самом деле не имеют отношения к текущему вопросу. Это обозначение, которое я буду использовать, чтобы показать, что каждая пара чисел создана zip и используется для понимания списка.

     = 0 : 1 : 0+1 : [ a + b | (a, b) <- zip [1, ??] [??]]
     = 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, ??] [??]]

Теперь мы знаем, что следующим элементом в ?? является 1:

     = 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, 1, ??] [1, ??]]
     = 0 : 1 : 1 : [ a + b | (a, b) <- (1, 1) : zip [1, ??] [??]]
     = 0 : 1 : 1 : 1+1 : [ a + b | (a, b) <- zip [1, ??] [??]]
     = 0 : 1 : 1 : 2 : [ a + b | (a, b) <- zip [1, ??] [??]]

А следующим элементом является 2:

     = 0 : 1 : 1 : 2 : [ a + b | (a, b) <- zip [1, 2, ??] [2, ??]]

Сполосните и повторите.

Answer 5

Для чего это стоит, мне легче понять следующую версию:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Answer 6

Понимание списка в скобках:

[ a + b | (a, b) <- zip fibs (tail fibs)]

возвращает список, содержащий выходные данные (a + b), где переменные a и b происходят из результата

zip fibs (tail fibs)

Answer 7

я до сих пор не понимаю. мне нравится этот ответ: https://stackoverflow.com/a/42183415/246387 (из код-ученик ).

но я не понимаю, как из этой строки:

= 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, ??] [??]]

это перейти к этому:

= 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, 1, ??] [1, ??]]

и кроме этого у меня есть кое-что еще, что беспокоит меня:

как я могу использовать fib внутри списка, если у меня нет fib (кажется, но я ошибаюсь), потому что fib еще не рассчитано он «ждет» (в левой части знака равенства) вычислить в правой части (знака равенства).

Answer 8

Это определяет эту диаграмму потока

           .----->>------->>----.
          /                      \
         /                       /     
         \                      /        
     <---- 0 <---- 1 ---<<--- (+)       
                 /              \         
                 \               \         
                  \              /       
                   *---->>------*       

, который извлекает новый ввод из себя, как только он произведен, но всегда на одну и две позиции перед точкой производства, сохраняя два «обратных указателя» в последовательности как бы. Это отражено в определении fibs = 0:1:[ a+b | a <- fibs | b <- tail fibs] с параллельным пониманием списка (:set -XParallelListComp и т. Д.).

Поскольку он использует только свои последние два элемента, он эквивалентен

    map fst . iterate (\(a, b) -> (b, a+b)) $ (0,1)

Answer 9

Как парсер узнает, что входит в (a, b) иначе?

РЕДАКТИРОВАТЬ: Благодаря ViralShah, я сделаю это немного менее гномично. «<-» указывает синтаксическому анализатору назначить список пар с правой стороны «zip fibs (tail fibs)» левой стороне «(a, b)». </p>