Как определить последовательность Фибоначчи, используя складку для натуральных чисел?

Question

В настоящее время я изучаю складки в смысле структурной рекурсии / катаморфизма. Я реализовал силу и факториал, используя складку для натуральных чисел. Обратите внимание, что я почти не знаю Haskell, поэтому код, вероятно, неудобен:

foldNat zero succ = go
  where
    go n = if (n <= 0) then zero else succ (go (n - 1))

pow n = foldNat 1 (n*)

fact n = foldNat 1 (n*) n

Далее я хотел адаптировать последовательность Фибоначчи:

fib n = go n (0,1)
  where
    go !n (!a, !b) | n==0      = a
                   | otherwise = go (n-1) (b, a+b)

С fib У меня есть пара в качестве второго аргумента, чьи поля меняются при каждом рекурсивном вызове. Я застрял в этой точке, потому что я не понимаю механику процесса преобразования.

[РЕДАКТИРОВАТЬ]

Как отмечено в комментариях мой fact функция неверна. Вот новая реализация, основанная на параморфизме (надеюсь):

paraNat zero succ = go 
  where 
    go n = if (n <= 0) then zero else succ (go (n - 1), n)

fact = paraNat 1 (\(r, n) -> n * r)

Answer 1

Пусть типы направляют вас. Вот твой foldNat, но с сигнатурой типа:

import Numeric.Natural

foldNat :: b -> (b -> b) -> Natural -> b
foldNat zero succ = go
  where
    go n = if (n <= 0) then zero else succ (go (n - 1))

Имея другой взгляд на go помощник в вашей реализации fib, мы можем отметить, что рекурсивный случай принимает и возвращает (Natural, Natural) пара. Сравнивая это с аргументом преемника foldNat предполагает, что мы хотим b быть (Natural, Natural), Это хороший намек на то, как кусочки go должно соответствовать:

fibAux = foldNat (0, 1) (\(a, b) -> (b, a + b))

(Я пока игнорирую вопрос строгости, но вернусь к этому.)

Это не совсем fib тем не менее, как видно из вида результата. Однако исправить это не проблема, как отмечает Робин Зигмонд:

fib :: Natural -> Natural
fib = fst . foldNat (0, 1) (\(a, b) -> (b, a + b))

На этом этапе вы можете работать в обратном направлении и заменить определение foldNat представить, как это соответствует явно рекурсивному решению.

---

Хотя это очень хорошая реализация fibМежду ним и тем, что вы написали, есть одно существенное различие: это ленивая правая складка (как и норма для катаморфизмов Хаскелла), тогда как ваша была четко обозначена как строгая левая складка. (И да, здесь имеет смысл использовать строгую левую складку: в общем, если то, что вы делаете, выглядит как арифметика, в идеале вам нужно строгое левое, а если это похоже на построение структуры данных, вам нужно ленивое правое). Хорошая новость заключается в том, что мы можем использовать катаморфизм для определения практически всего, что потребляет значение рекурсивно... включая строгие левые сгибы! Здесь я буду использовать адаптированную версию трюка foldl-from-foldr (см. Этот вопрос для подробного объяснения этого в случае списков), который опирается на такую ​​функцию:

lise :: (b -> b) -> ((b -> b) -> (b -> b))
lise suc = \g -> \n -> g (suc n)

Идея состоит в том, что мы используем преимущества композиции функций (\n -> g (suc n) такой же как g . suc) делать вещи в обратном порядке - это как если бы мы поменялись местами succ а также go в правой части вашего определения go, lise suc может быть использован в качестве аргумента преемника foldNat, Это означает, что мы получим b -> b функция в конце концов, а не b, но это не проблема, потому что мы можем применить его к нулевому значению сами.

Так как мы хотим строгую левую складку, мы должны прокрасться в ($!) Чтобы убедиться suc n с нетерпением оценивается:

lise' :: (b -> b) -> ((b -> b) -> (b -> b))
lise' suc = \g -> \n -> g $! suc n

Теперь мы можем определить строгую левую складку (это foldNat какие foldl' от Data.List это к foldr):

foldNatL' :: b -> (b -> b) -> Natural -> b
foldNatL' zero suc n = foldNat id (lise' suc) n zero

Есть заключительная, важная деталь, с которой нужно иметь дело: строгое сгибание будет бесполезным, если мы будем лениво строить пару на этом пути, так как компоненты пары будут строиться лениво. Мы могли бы справиться с этим, используя ($!) вместе с (,) для построения пары в функции преемника. Тем не менее, я считаю, что лучше использовать строгий тип пары вместо этого, чтобы нам не пришлось беспокоиться об этом:

data SP a b = SP !a !b 
    deriving (Eq, Ord, Show)

fstSP :: SP a b -> a
fstSP (SP a _) = a

sndSP :: SP a b -> b
sndSP (SP _ b) = b

! пометьте поля как строгие (обратите внимание, что вам не нужно включать BangPatterns использовать их).

Со всем на месте, мы можем наконец иметь fib как строгая левая складка:

fib' :: Natural -> Natural
fib' = fstSP . foldNatL' (SP 0 1) (\(SP a b) -> SP b (a + b))

---

PS: Как отмечает Амаллой, ваш fac вычисляет n^n, а не n!, Вероятно, этот вопрос лучше оставить для отдельного вопроса; в любом случае, суть в том, что факториал более естественно выражается как параморфизм в натуральном выражении, а не как простой катаморфизм. (Подробнее об этом см., Например, сообщение в блоге " Практические схемы рекурсии " Джареда Тобина, более конкретно раздел о параморфизмах.)