Понимание прямой самореференция в Haskell

Я только начал изучать Haskell через несколько часов идти, пытаясь понять, что это The Fibonacci sequence делает:Понимание прямой самореференция в Haskell

fibs = 0 : 1 : next fibs 
    where 
    next (a : [email protected](b:_)) = (a+b) : next t

next функция для меня странно, что в конечном итоге получить некоторые " недопустимый»вход, как в первом она выглядит следующим образом:

next (0:1) = (0+1) : next [1]

но next ([1]) не функционирует, так как [email protected](b:_) не имеет входа в него. Итак, как работает next?

И моя следующая путаница fib сама, так как это предполагают, чтобы быть последовательность Фибоначчи, я предполагаю, что он будет получать fibs = 0 : 1 : 1 : next fibs после первого шага, но тогда нам нужно будет вычислять next([0, 1, 1]) ведьма дает (0+1): next([1, 1]) == 1 : next([1, 1]), мы получаем начальный элемент 1, поэтому в next([0, 1, 1]) первое значение списка (в следующих пунктах) будет 1, но прикрепит это 1 к исходному фиду, мы получим 0 : 1 : 1 : 1, который не является последовательностью Фибоначчи.

Я думаю, что я что-то неправильно понял, так как это работает?

источник

2015-08-27 CYC

Ссылка на 'fibs' в первой строке ссылается на * полный (бесконечный) список *, а не только на два элемента, которые были явно определены. Первый шаг не 'next (0: 1)', это 'next (0: 1: next fibs)', и он оценивает '(0 + 1): next (1: next fibs)'. Конечные списки, такие как [0, 1, 1], никогда не участвуют. – Wyzard

Стандартный способ определить результат рекурсивного определения является приблизительно такое значение, начиная с undefined и разворачивающуюся рекурсию оттуда следующим образом:

-- A function describing the recursion 
f x = 0 : 1 : next x 

fibs0 = undefined 
fibs1 = f fibs0 = 0 : 1 : next undefined 
     -- next requires at least 2 elements 
     = 0 : 1 : undefined 
fibs2 = f fibs1 = 0 : 1 : next fibs1 
     = 0 : 1 : next (0 : 1 : undefined) 
     = 0 : 1 : 1 : next (1 : undefined) 
     -- next requires at least 2 elements 
     = 0 : 1 : 1 : undefined 
fibs3 = f fibs2 = 0 : 1 : next fibs2 
     = 0 : 1 : next (0 : 1 : 1 : undefined) 
     = 0 : 1 : 1 : next (1 : 1 : undefined) 
     = 0 : 1 : 1 : 2 : next (1 : undefined) 
     -- next requires at least 2 elements 
     = 0 : 1 : 1 : 2 : undefined 
fibs4 = f fibs3 = 0 : 1 : next fibs3 
     = 0 : 1 : next (0 : 1 : 1 : 2 : undefined) 
     ...

Если мы будем продолжать идти дальше мы будем подходить к полной последовательности «на пределе», приближаясь к нему шаг за шагом. Этот неофициальный аргумент может быть формально оправдан через теорему о неподвижной точке Клейна.

источник

2015-08-27 12:26:01 chi

Чтобы уточнить, поэтому интуитивное мышление 'fib' представляет собой последовательность' [a0, a1, a2 ...] (= x) ', которая фактически удовлетворяет' x = [0,1, (next x)] '(в математическая манера), а 'next (= g)' - это функция, которая действительно удовлетворяет букве g ([a, b0, b1, b2 ....]) = [a + b0, g ([b0, b1, b2. ..])] ', и такие« x и g »существуют и уникальны и могут быть получены путем аппроксимации (путем многозначного значения значения), что гарантируется теоремой о неподвижной точке Клейна? – CYC

@ CYC Грубо, да. И 'fib', и' next' определяются рекурсией, поэтому технически нужно будет применить Kleene дважды, в области списков ('fib') и функций из списков в списки (' next'). Выше я более точно показал приближение в домене списка, в то время как я не продвинулся с тем же уровнем детализации для 'next' и вместо этого работал с использованием интуиции. Действительно, даже игнорируя неподвижные точки, вы можете получить некоторый результат, просто расширив определения «fibs» и «next», делая вид, что их определяющие рекурсивные уравнения просто сохраняются. – chi

Функция next фактически генерирует fibs - поэтому он не позвонит next [0, 1, 1], он назовет next (0 : 1 : 1 : next rest).

Существует то, что происходит в картинках:

fib = 0 : 1 : not-yet-evaluated-part

fib = 0 : 1 : [+] : not-yet-evaluated-part 
    ^^ | 
     *---*----* (applying next to fib)

fib = 0 : 1 : 1 : [+] : not-yet-evaluated-part 
     ^^ | 
      *---*----* (next calls itself)

fib = 0 : 1 : 1 : 2 : [+] : not-yet-evaluated-part 
      ^^ | 
       *---*----* (etc)

next является "железнодорожно-строитель поезд" требуя выполнения некоторых начальных рельсов (0 : 1 : ...).

Потому что есть [] -end из списка, который нигде не указан в списке фишек, он будет бесконечным.

Однако я рекомендую вам начать с менее неясных вещей - например, вы должны попытаться понять списки в одиночку.

источник

2015-08-27 12:25:31 Heimdell

рекурсивный вызов не получит весь список, а только хвост. и есть только один рекурсивный вызов не два. –

Понимание прямой самореференция в Haskell

ответ

Смежные вопросы