Числа Фибоначчи

@PrestoConFuoco · Регистрация: 11.11.2018

Студворк — интернет-сервис помощи студентам

Здравствуйте.
Я начал осваивать Haskell недавно.
В Википедии набрёл на следующее описание функции для получения бесконечной последовательности из чисел Фибоначчи за
линейное время:

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

Я пытался полазить по различным форумам, чтобы понять, как это работает, но никакой конкретики не нашёл.
Как формально доказать, что эта функция работает за линейное время? (например если использовать take n fibs)

Если попробовать попытаться посчитать, например, четвертое число Фибоначчи "в лоб", то получается нечто такое:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fibs = 0:1:zipWith (+) fibs (tail fibs)
 
1) 0:1: zipWith (+) (0:1:zipWith (+) fibs (tail fibs)) (1:zipWith (+) fibs (tail fibs))
 
2) 0:1:1: zipWith (+)    (1:zipWith (+) fibs (tail fibs))    (zipWith (+) fibs (tail fibs))
 
3) 0:1:1: zipWith (+)    (1:zipWith (+) fibs (tail fibs))
         (zipWith (+)    0:1:1:zipWith (+)       (1:zipWith (+) fibs (tail fibs))       (zipWith (+) fibs (tail fibs))
 (tail 0:1:1: zipWith (+)        (1:zipWith (+) fibs (tail fibs))       (zipWith (+) fibs (tail fibs)) ))
 
4) 0:1:1: zipWith (+) (1:zipWith (+) fibs (tail fibs))
         (zipWith (+)     {   0:1:1:zipWith (+)      (1:zipWith (+) fibs (tail fibs)) (zipWith (+) fibs (tail fibs)) }
  {  1:1: zipWith (+) (1:zipWith (+) fibs (tail fibs)) (zipWith (+) fibs (tail fibs))   }     )
 
5) 0:1:1: zipWith (+) (1:zipWith (+) fibs (tail fibs)) 
         (1:2:zipWith (+)     {   1:zipWith (+)      (1:zipWith (+) fibs (tail fibs)) (zipWith (+) fibs (tail fibs)) }
  {  zipWith (+) (1:zipWith (+) fibs (tail fibs)) (zipWith (+) fibs (tail fibs))   }     )
 
6) 0:1:1:2: zipWith (+) (zipWith (+) fibs (tail fibs))  
         (2:zipWith (+)     {   1:zipWith (+)      (1:zipWith (+) fibs (tail fibs)) (zipWith (+) fibs (tail fibs)) }
  {  zipWith (+) (1:zipWith (+) fibs (tail fibs)) (zipWith (+) fibs (tail fibs))   }     )

(Фигурные скобки добавлены для большей наглядности)

Если всё происходит так, как тут написано, то это совсем не похоже на линейное время. Третье число Фибоначчи мы считаем условно за два шага, а четвертое - за четыре. Даже боюсь представить, что будет происходить для 5 и далее чисел.

Я четко осознаю, что скорее всего то ,что я тут написал, - это конченая ересь. Прошу не кидаться тапками, а помочь разобраться.
Спасибо за понимание

@Catstail · 19.11.2018, 08:19

Сообщение от PrestoConFuoco

Третье число Фибоначчи мы считаем условно за два шага, а четвертое - за четыре. Даже боюсь представить, что будет происходить для 5 и далее чисел.

- не стоит бояться... Пятое будет за пять, шестое - за 6 и т.д. Это и есть - за линейное время. Сравните этот алгоритм с "лобовым" вычислением:

Haskell
1
2
3
fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

Здесь из-за параллельной рекурсии будет происходить многократное перевычисление одних и тех же чисел. В этом легко убедиться даже "экспериментально": на моем компьютере я не дождался вычисления 40-го числа Фибоначчи (лобовым алгоритмом). А 40 членов бесконечного ряда вычислены мгновенно.

@PrestoConFuoco · 19.11.2018, 08:59 **[ТС]**

Сообщение от Catstail

не стоит бояться... Пятое будет за пять, шестое - за 6 и т.д. Это и есть - за линейное время.

Получается, за линейное время мы вычисляем не сам список чисел, а каждое из них.
Если просуммировать, то получится грубо говоря арифметическая прогрессия:

Sigma(i,N) N = N*(N-1)/2

В итоге получается тот же квадрат.
А, например, итеративное решение занимает именно линейное время, ведь ресурсоемкость итераций цикла практически не меняется.

Может быть, на самом деле эта функция работает не так, как я написал?

@Catstail · 19.11.2018, 09:14

Сообщение от PrestoConFuoco

Если просуммировать, то получится грубо говоря арифметическая прогрессия:

- это если сначала вычислить второе, потом (с начала) третье и т.п. - то да. Но при однократном вычислении время линейно. Не верите? Ну проведите выч. эксперимент.

@PrestoConFuoco · 19.11.2018, 09:21 **[ТС]**

Сообщение от Catstail

- это если сначала вычислить второе, потом (с начала) третье и т.п. - то да. Но при однократном вычислении время линейно. Не верите? Ну проведите выч. эксперимент

Вот именно, что верю, но хочу понять, почему так происходит.

А как можно вычислить с помощью

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

сразу нужное нам число Фибоначчи? Здесь же "некуда подставлять" даже номер. Я думал, что вычисляется всегда список до того элемента, когда можно будет остановиться (например при использовании take).

@Mysterious Light · 19.11.2018, 09:33

Как ты уже, наверное, понял, Хаскель высокоуровневый ЯП, который основан на лямбда-исчислении.
Поэтому все задаваемые вопросы могут быть разделены условно на два класса: те, которые относятся чисто к синтаксису и семантике языка и, как правило, могут быть перефразированы в терминах лямбда-исчисления, и те, которые также касаются реализации языка (интерпретатора, транслятора и т.п.)

Вопрос о времени исполнения как правило рассматривается в контексте конкретной реализации. Впрочем, вне реализации вопрос тоже можно поставить, и он будет интересным.
Если же мы рассматриваем GHC, то он умеет делать (пусть знающие люди подскажут правильное название) графовую редукцию.
Суть заключается в том, что переменной fibs сопоставляется граф выражения по правую сторону, в котором fibs является вершиной. Таким образом, в этом графе появляется цикл. При вычислении граф преобразует, но из-за цикла новые копии fibs не создаются, поэтому будет что-то типа

Haskell
1
2
3
4
5
6
7
8
9
fibs = 0:1:fibs'
fibs' = zipWith (+) fibs (tail fibs)
fibs' = zipWith (+) (0:1:fibs') (tail (0:1:fibs'))
fibs' = zipWith (+) (0:1:fibs') (1:fibs')
fibs' = (0+1):zipWith (+) (1:fibs') fibs'
fibs' = (0+1):fibs''
fibs'' = zipWith (+) (1:fibs') fibs'
fibs'' = zipWith (+) (1:fibs') ((0+1):fibs'')
fibs'' = (1+(0+1)) : zipWith (+) fibs' fibs''

и т.д.
где fibs' и fibs'' указатели на вершины графа значения fib.
Таким образом, время на разворачивание (вычисление) графа линейно.

Что же касается последнего вопрса, то, думаю, всё зависит от доступа к элементам и внутренней реализации структуры данных.
Скажем, самопальный тип списка и take, реализованный через последовательный доступ к 1-му, 2-му ... n-му элементу будет работать квадратичное время. В то же время стандартное определение take с хвостовой рекурсией будет само работать за линейное время. Как устроена стадартная реализация списка в GHC, увы, не знаю.

Но учтите, если будешь писать свой компилятор Haskell, оценка времени может оказаться другой, полиномиальной или экспоненциальной.

Добавлено через 10 минут
Не могу найти литературу. В книге Филд А., Харрисон П. Функциональное программирование (1993) есть раздел 11 про графовую редукцию, но, по-моему, это не про GHC. Похожая занимательная литература легко гуглится, например, Asperti A. On the complexity of beta-reduction, но, опять же, не уверен, что это применимо к GHC.

@Catstail · 19.11.2018, 10:41

Делаем так:

Haskell
1
2
3
import Debug.Trace
 
fibg = 0:1:zipWith (\ x y -> trace ("x="++(show x)++" y="++(show y)) x+y) fibg (tail fibg)

Запускаем этот код:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
*Main> take 5 fibg
x=0 y=1
x=1 y=1
x=1 y=2
[0,1,1,2,3]
*Main> take 10 fibg
x=2 y=3
x=3 y=5
x=5 y=8
x=8 y=13
x=13 y=21
[0,1,1,2,3,5,8,13,21,34]

Вот он - ленивый список в действии! Ну и линейность вполне очевидна...

@Black Fregat · 19.11.2018, 13:44

А можно как-то посмотреть на более низком уровне, во что этот ряд реально разворачивается?

@PrestoConFuoco · 20.11.2018, 00:06 **[ТС]**

Mysterious Light,

Спасибо.
Кажется, до меня немного дошло. Разница между моим вычислением и вашим - в том, что у меня подставляется каждый раз fibs, из-за чего все вычисления нужно проводить по много раз.

Попробую продолжить ваш пример, чтобы убедиться, что я правильно его воспринимаю:

Сообщение от Mysterious Light

Haskell
1
2
3
4
5
6
7
8
9
fibs = 0:1:fibs'
fibs' = zipWith (+) fibs (tail fibs)
fibs' = zipWith (+) (0:1:fibs') (tail (0:1:fibs'))
fibs' = zipWith (+) (0:1:fibs') (1:fibs')
fibs' = (0+1):zipWith (+) (1:fibs') fibs'
fibs' = (0+1):fibs''
fibs'' = zipWith (+) (1:fibs') fibs'
fibs'' = zipWith (+) (1:fibs') ((0+1):fibs'')
fibs'' = (1+(0+1)) : zipWith (+) fibs' fibs''

Haskell
1
2
3
4
fibs'' = (1+(0+1)) : zipWith (+) (0+1):fibs'' fibs''
fibs''' = zipWith (+) (0+1):fibs'' fibs''
fibs''' = zipWith(+) (0+1):fibs'' (1+(0+1)) : fibs'''
fibs''' = ((0+1)+(1+(0+1))) : zipWith(+) fibs'' fibs'''

Последняя строка у меня уже аналогична последней строке у вас, и общий смысл прослеживается.

Что касается графов, я к сожалению мало что понял из того, что вы об этом написали. Но наверное главное, что я понял - что мне нужно заняться в ближайшее время теорией графов

Надеюсь, когда-нибудь дело дойдет и до этого примера.

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это дополнительная запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .

@Black Fregat Фрилансер 3709 / 2083 / 567 Регистрация: 31.05.2009 Сообщений: 6,683
	19.11.2018, 13:44
	А можно как-то посмотреть на более низком уровне, во что этот ряд реально разворачивается? 0

Числа Фибоначчи

Решение