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

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

2 голосов
/ 04 мая 2019

В настоящее время я изучаю складки в смысле структурной рекурсии / катаморфизма. Я реализовал силу и факториал, используя складку для натуральных чисел. Обратите внимание, что я почти не знаю 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 у меня есть пара в качестве второго аргумента, чьи поля меняются местами при каждом рекурсивном вызове. Я застрял в этой точке, потому что я не понимаю механику процесса преобразования.

[EDIT]

Как отмечено в комментариях, моя 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)

1 Ответ

2 голосов
/ 04 мая 2019

Пусть типы ведут вас. Вот ваш 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))

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

...