В чем разница между рекурсией и corecursion?

Какая разница между ними?

• Рекурсия
• корекурсия

В Википедии мало информации и нет четкого кода, объясняющего эти термины.

Каковы некоторые очень простые примеры, объясняющие эти термины?

Как corecursion двойственна рекурсии?

Существуют ли классические corecusive алгоритмы?

Есть несколько хороших способов посмотреть на это. Самая легкая вещь для меня - подумать об отношении между «индуктивными» и «коиндуктивными определениями»

Индуктивное определение множества выглядит следующим образом.

Набор «Nat» определяется как наименьший набор, такой, что «Ноль» находится в Nat, а если n - в Nat, «Succ n» - в Nat.

Что соответствует следующему Ocaml

type nat = Zero | Succ of nat

Об этом определении следует отметить, что число

omega = Succ(omega)

НЕ является членом этого набора. Почему? Предположим, что это так, теперь рассмотрим множество N, которое имеет все те же элементы, что и Nat, за исключением того, что оно не содержит омеги. Ясно, что ноль находится в N, и если y находится в N, Succ (y) находится в N, но N меньше, чем Nat, что является противоречием. Итак, омега не в нат.

Или, может быть, более полезным для ученого:

При некотором наборе «a», набор «List of a» определяется как наименьший набор, такой, что «Nil» находится в List of a, и что, если xs находится в List of a, а x находится в «Cons x xs» находится в списке.

Что соответствует чему-то вроде

type 'a list = Nil | Cons of 'a * 'a list

Оперативное слово здесь «самое маленькое». Если бы мы не сказали «самый маленький», у нас не было бы никакого способа сказать, содержал ли банан Nat набор!

Очередной раз,

zeros = Cons(Zero,zeros)

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

Такое индуктивное определение данных позволяет нам определять функции, которые работают с ними, используя рекурсию

let rec plus a b = match a with
                   | Zero    -> b
                   | Succ(c) -> let r = plus c b in Succ(r)

затем мы можем доказать факты об этом, например, «плюс ноль = а», используя индукцию (в частности, структурную индукцию)

Наше доказательство проводится структурной индукцией по a.
Для базового случая пусть будет ноль. plus Zero Zero = match Zero with |Zero -> Zero | Succ(c) -> let r = plus c b in Succ(r)Итак, мы знаем plus Zero Zero = Zero. Позвольте aбыть нац. Предположим, что индуктивная гипотеза plus a Zero = a. Покажем теперь, что plus (Succ(a)) Zero = Succ(a)это очевидно, так как plus (Succ(a)) Zero = match a with |Zero -> Zero | Succ(a) -> let r = plus a Zero in Succ(r) = let r = a in Succ(r) = Succ(a) по индукции plus a Zero = aдля всех aв

Конечно, мы можем доказать более интересные вещи, но это общая идея.

До сих пор мы имели дело с индуктивно определенными данными, которые мы получили, позволив им быть «наименьшим» набором. Итак, теперь мы хотим работать с кодированными кодами, которые мы получаем, позволяя получить самый большой набор.

Так

Позвольте быть набором. Набор «Поток a» определяется как наибольший набор, такой, что для каждого x в потоке a, x состоит из упорядоченной пары (голова, хвост), так что голова находится в a, а хвост находится в потоке a

В Хаскеле мы бы выразили это как

data Stream a = Stream a (Stream a) --"data" not "newtype"

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

data [a] = [] | a:[a]

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

ones = 1:ones

и это совершенно правильное определение. Более того, мы можем выполнить совместную рекурсию по этим данным. На самом деле, функция может быть одновременно и рекурсивной, и рекурсивной. В то время как рекурсия была определена функцией, имеющей домен, состоящий из данных, ко-рекурсия просто означает, что у нее есть совместная область (также называемая диапазоном), которая является совместной информацией. Примитивная рекурсия означала всегда «звонить самому себе» по меньшим данным до достижения самых маленьких данных. Примитивная совместная рекурсия всегда "вызывает себя" на данных, которые больше или равны тем, которые вы имели ранее.

ones = 1:ones

примитивно ко-рекурсивный. В то время как функция map(вроде как «foreach» в императивных языках) является примитивно рекурсивной (как бы) и примитивно ко-рекурсивной.

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = (f x):map f xs

То же самое касается функции, zipWithкоторая берет функцию и пару списков и объединяет их вместе, используя эту функцию.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = (f a b):zipWith f as bs
zipWith _ _ _           = [] --base case

классическим примером функциональных языков является последовательность Фибоначчи

fib 0 = 0
fib 1 = 1
fib n = (fib (n-1)) + (fib (n-2))

который является примитивно рекурсивным, но может быть более элегантно выражен как бесконечный список

fibs = 0:1:zipWith (+) fibs (tail fibs)
fib' n = fibs !! n --the !! is haskell syntax for index at

Интересным примером индукции / соиндукции является доказательство того, что эти два определения вычисляют одно и то же. Это оставлено в качестве упражнения для читателя.

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

(говорит на Хаскеле сейчас). Вот почему foldr(со строгой функцией объединения) выражает рекурсию, и foldl'(со строгой комбинацией. F. ) / scanl/ until/ iterate/ unfoldr/ И т. Д. Выражает corecursion. Corecursion есть везде. foldrс не строгой расческой. е. выражает хвостовую рекурсию по модулю минусов .

И защищенная рекурсия Хаскелла - это как хвостовая рекурсия по модулю минусов .

Это рекурсия:

fib n | n==0 = 0
      | n==1 = 1
      | n>1  = fib (n-1) + fib (n-2)

fib n = snd $ g n
  where
    g n | n==0 = (1,0)
        | n>0  = let { (b,a) = g (n-1) } in (b+a,b)

fib n = snd $ foldr (\_ (b,a) -> (b+a,b)) (1,0) [n,n-1..1]

(читается $как "из"). Это corecursion:

fib n = g (0,1) 0 n where
  g n (a,b) i | i==n      = a 
              | otherwise = g n (b,a+b) (i+1)

fib n = fst.snd $ until ((==n).fst) (\(i,(a,b)) -> (i+1,(b,a+b))) (0,(0,1))
      = fst $ foldl (\(a,b) _ -> (b,a+b)) (0,1) [1..n]
      = fst $ last $ scanl (\(a,b) _ -> (b,a+b)) (0,1) [1..n]
      = fst (fibs!!n)  where  fibs = scanl (\(a,b) _ -> (b,a+b)) (0,1) [1..]
      = fst (fibs!!n)  where  fibs = iterate (\(a,b) -> (b,a+b)) (0,1)
      = (fibs!!n)  where  fibs = unfoldr (\(a,b) -> Just (a, (b,a+b))) (0,1)
      = (fibs!!n)  where  fibs = 0:1:map (\(a,b)->a+b) (zip fibs $ tail fibs)
      = (fibs!!n)  where  fibs = 0:1:zipWith (+) fibs (tail fibs)
      = (fibs!!n)  where  fibs = 0:scanl (+) 1 fibs
      = .....

Складки: http://en.wikipedia.org/wiki/Fold_(higher-order_function)

Проверьте это в блоге Витомира Ковановича . Я нашел это в точку:

Ленивое вычисление в одной очень приятной функции, встречающейся в языках программирования с функциональными возможностями программирования, таких как lisp, haskell, python и т. Д. Это позволяет задерживать оценку значения переменной до фактического использования этой переменной.

Это означает, что, например, если вы хотите создать список из миллиона элементов с чем-то вроде этого, (defn x (range 1000000))он на самом деле не создается, а просто указывается, и когда вы действительно используете эту переменную в первый раз, например, когда вы хотите 10-й элемент этот интерпретатор списка создает только первые 10 элементов этого списка. Таким образом, первый запуск (take 10 x) фактически создает эти элементы, и все последующие вызовы той же функции работают с уже существующими элементами.

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

С другой стороны, corecursion двойственна рекурсии. Что это значит? Ну, как и рекурсивные функции, которые выражаются в терминах самих себя, corecursive переменные выражаются в терминах самих себя.

Это лучше всего выражено на примере.

Допустим, мы хотим список всех простых чисел ...