Haskell Фибоначчи - не может построить бесконечный тип: a0 = [a0]

Question

Я пытался получить бесконечный список чисел Фибоначчи в Haskell, но следующий код не компилируется:

fib1 x = fib1 (x : (last $ init x) + (last x)) 
result1 = fib1 [1,2] 

в конце концов, я получил его работать с этим кодом:

fib2 x y = head y : fib2 y (zipWith (+) x y) 
result2 = fib2 [0,1] [1,1] 

Тем не менее, я не понимаю, почему первый фрагмент кода не компилировать. Ошибка ниже. Я просто ищу ответ, почему первый не компилируется, но второй делает.

p2.hs:3:16: 
    Occurs check: cannot construct the infinite type: a0 = [a0] 
    In the first argument of `(:)', namely `x' 
    In the first argument of `fib1', namely 
     `(x : (last $ init x) + (last x))' 
    In the expression: fib1 (x : (last $ init x) + (last x)) 

p2.hs:3:21: 
    Occurs check: cannot construct the infinite type: a0 = [a0] 
    In the first argument of `(+)', namely `(last $ init x)' 
    In the second argument of `(:)', namely 
     `(last $ init x) + (last x)' 
    In the first argument of `fib1', namely 
     `(x : (last $ init x) + (last x))' 

p2.hs:3:44: 
    Occurs check: cannot construct the infinite type: a0 = [a0] 
    Expected type: [[a0]] 
     Actual type: [a0] 
    In the first argument of `last', namely `x' 
    In the second argument of `(+)', namely `(last x)' 
    In the second argument of `(:)', namely 
     `(last $ init x) + (last x)' Failed, modules loaded: none. 

Answer 1

Проблема с первым примером кода заключается в том, что вы не можете написать аннотацию типа для нее. Это было бы бесконечно. Давайте попробуем это все равно:

fib1 x = fib1 (x : (last $ init x) + (last x))

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

fib1 x = fib1 (x : undefined)

Какого типа fib1-х аргумент. Слева мы видим только x без дополнительной информации. Мы можем предположить, что у него есть какой-то тип a. С правой стороны мы пытаемся вызвать функцию с аргументом, который должен быть списком (потому что он построен оператором :). Элементы списка начинаются с x, который имеет тип a. Поэтому здесь аргументом fib1 является [a]. Поскольку мы не можем вызывать функцию с аргументами двух разных типов, даже на левой стороне x должен иметь тип [a]. Но это заставляет нас обновлять тип на стороне установки до [[a]]. И снова налево. Этот процесс никогда не прекратится, тип будет расти и расти, потому что нет способа объединить a с [a]. Поэтому для выражения не существует допустимого типа, и GHC отклонит его.

С другой стороны, во втором фрагменте нет проблемы.

fib2 x y = head y : fib2 y (zipWith (+) x y)

Мы можем легко задать GHCI тип этой функции, и он с радостью ответит нам:

Prelude> let fib2 x y = head y : fib2 y (zipWith (+) x y) Prelude> :t fib2 fib2 :: Num a => [a] -> [a] -> [a]

Этот тип вполне конечна.