На этом шаге мы рассмотрим понятие корекурсии и ее использование при конструировании списков.
Понятие "корекурсия" определяется с помощью понятия "коданные".
- Определение (описательное) [1 ,с.37].
- Коданные обладают следующими свойствами:
- (1) они скрывают свою структуру (в отличие от данных);
- (2) они не содержат атрибутов, имеющих смысл "значение";
- (3) они обладают только методами доступа, некоторые из которых возвращают данные, некоторые - коданные;
- (4) они обычно являются бесконечными структурами.
В языке Haskell интерпретацией коданных являются рекурсивные абстрактные типы данных, например, списки.
Отметим, что в языке Haskell идиома коданных отсутствует; другими словами, это понятие в языке не определено в явном виде.
Поэтому мы будем моделировать коданные с помощью потенциально бесконечных списков, которые ещё называются потоками или ленивыми списками (от англ. lazy lists).
- Определение (содержательное).
- Корекурсия (в программировании) - это тип операции, дуальной к рекурсии. Более точно, правило использования корекурсии на коданных
дуально правилу применения рекурсии на данных:
- (1) рекурсия "сворачивает" структуру данных, исходя из начального значения аргумента, т.е. рекурсия анализирует и порождает конечные структуры данных. Другими словами, рекурсивные определения работают с данными, осуществляя "спуск" от начальных значений входных параметров к таким значениям, на которых происходит остановка рекурсивного процесса;
- (2) корекурсия "разворачивает" результат на основе начального значения аргумента, т.е. корекурсия порождает бесконечные структуры данных. Другими словами, корекурсия работает с коданными, производя "накрутку" значений на начальные величины входных параметров, никогда не останавливаясь;
- (3) рекурсия не применима к коданным, поскольку процесс анализа может никогда не остановиться;
- (4) корекурсия не может применяться в случаях, если результатом её работы должны являться данные, поскольку данные всегда конечны.
- Определение.
- Корекурсивное определение - это рекурсивное определение, не содержащее базисный пункт, но содержащее рекурсивный пункт. Оно всегда определяет бесконечные объекты; другими словами, результатом применения корекурсии являются коданные.
Механизм корекурсии используется с механизмом ленивых вычислений для генерации потенциально бесконечных структур данных на базе потенциально бесконечных списков (потоков).
Примеры (классические).
-- Функция конструирует потенциально бесконечный -- список натуральных чисел вида [1,1,1,...] -------------------------------------------- ones:: [Integer] ones = 1 : ones -- *********************************************** -- Функция конструирует потенциально бесконечный -- список натуральных чисел вида [n+1,n+2,n+3,...] -------------------------------------------------- subNats:: Integer -> [Integer] subNats n = n : subNats (n+1)
Выделим паттерны корекурсии, основанные на использовании функционалов map, iterate, zipWith.
Пример паттерна корекурсии map.
-- Функция конструирует потенциально бесконечный -- список натуральных чисел вида [1,1,1,...] -------------------------------------------- ones':: [Integer] ones' = 1 : map id ones' -- *********************************************** -- Функция конструирует потенциально бесконечный -- список натуральных чисел [0,1,2,...] --------------------------------------- nats:: [Integer] nats = 0 : map (+ 1) nats -- *********************************************** -- Функция конструирует потенциально бесконечный -- список нечётных натуральных чисел [1,3,5,...] ------------------------------------------------ odds:: [Integer] odds = 1 : map (+ 2) odds -- *********************************************** -- Функция конструирует потенциально бесконечный -- список чётных натуральных чисел [1,3,5,...] с -- помощью комбинатора неподвижной точки (y) -------------------------------------------- evens:: [Integer] evens = y (\f -> 0 : map (+ 2) f) where y f = f (y f)
Пример паттерна корекурсии iterate.
-- Демонстрация моделирования потенциально беско- -- нечных списков с помощью функционала iterate -- -- itarate f x = x : iterate f (f x) -- -- *********************** theOnes = iterate id 1 theNats = iterate (+ 1) 0 theOdds = iterate (+ 2) 1 theEvens = iterate (+ 2) 0
Пример паттерна корекурсии zipWith.
-- Функция конструирует потенциально бесконечный -- список натуральных чисел [0,1,2,...] с помощью -- функционала zipWith -- ************************************* theNats1 = 0 : zipWith (+) ones theNats1
Приведем несколько демонстрационных примеров.
-- Демонстрация конструирования простейших потен- -- циально бесконечных списков (потоков, кодан- -- ных) с помощью корекурсии -- ********************************************* -- Функция конструирует потенциально бесконечный -- список натуральных чисел вида [1,1,1,...] -------------------------------------------- ones:: [Integer] ones = 1 : ones -- ********************************************* -- Функция конструирует потенциально бесконечный -- список натуральных чисел вида [1,1,1,...] -------------------------------------------- ones':: [Integer] ones' = 1 : map id ones' -- *********************************************** -- Функция конструирует потенциально бесконечный -- список натуральных чисел [0,1,2,...] --------------------------------------- nats:: [Integer] nats = 0 : map (+ 1) nats -- *********************************************** -- Функция конструирует потенциально бесконечный -- список нечётных натуральных чисел [1,3,5,...] ------------------------------------------------ odds:: [Integer] odds = 1 : map (+ 2) odds -- *********************************************** -- Функция конструирует потенциально бесконечный -- список чётных натуральных чисел [1,3,5,...] с -- помощью комбинатора неподвижной точки (y) -------------------------------------------- evens:: [Integer] evens = y (\f -> 0 : map (+ 2) f) where y f = f (y f) -- *********************************************** -- Функция конструирует потенциально бесконечный -- список натуральных чисел вида [n+1,n+2,n+3,...] -------------------------------------------------- subNats:: Integer -> [Integer] subNats n = n : subNats (n+1) -- ********************************************* -- Функция конструирует потенциально бесконечный -- список вида [n^2,(n+1)^2,(n+2)^2,...] ---------------------------------------- squares:: Integer -> [Integer] squares n = map (^2) (subNats n) -- ********************************************** -- Демонстрация моделирования потенциально беско- -- нечных списков с помощью функционала iterate -- -- itarate f x = x : iterate f (f x) -- -- *********************** theOnes = iterate id 1 theNats = iterate (+ 1) 0 theOdds = iterate (+ 2) 1 theEvens = iterate (+ 2) 0 -- ********************************************** -- Функция конструирует потенциально бесконечный -- список натуральных чисел [0,1,2,...] с помощью -- функционала zipWith -- ************************************* theNats1 = 0 : zipWith (+) ones theNats1 -- ************************************* -- Неудачные тестовые примеры: ------------------------------------------- test1 = take 5 ones == [1,1,1,1,1] test2 = take 5 nats == [0,1,2,3,4] test3 = take 5 odds == [1,3,5,7,9] test4 = take 5 evens == [0,2,4,6,8] test5 = take 5 (subNats 5) == [5,6,7,8,9] test6 = take 5 (squares 11) == [121,144,169,196,225] ----------------------------------------------------- test7 = take 5 theOnes test8 = take 5 theNats test9 = take 5 theOdds test10 = take 5 theEvens ------------------------ test11 = take 5 theNats1
-- Демонстрация конструирования потенциально бесконечных -- списков (потоков, коданных) с помощью корекурсии -- **************************************************** -- Функция конструирует потенциально бесконечный список -- чисел Фибоначчи вида [0,1,1,2,3,5,8,...] -- (первый способ) ------------------ fibLst1 = abc 0 1 where abc x0 x1 = x0 : abc x1 (x0+x1) ------------------------------------------------------- -- Функция конструирует потенциально бесконечный список -- чисел Фибоначчи вида [0,1,1,2,3,5,8,...] -- (второй способ) ---------------------------------------------------- fibLst2 = 0 : 1 : zipWith (+) fibLst2 (tail fibLst2) -- **************************************************** -- Функция конструирует потенциально бесконечный список -- чисел вида [-1,1,-1,1,-1,1,1-,...] ------------------------------------- abc = pr fibLst1 where pr (x1:x2:x3:lst) = x1*x3-x2*x2 : pr (x2:x3:lst) -- ****************************************************** -- Функция возвращает список простых чисел из [2..] -- (первый способ) ------------------------------ sieve:: [Integer] -> [Integer] sieve (0:xs) = sieve xs sieve (n:xs) = n : sieve (mark xs 1 n) where mark (y:ys) k m | k==m = 0 : mark ys 1 m | True = y : mark ys (k+1) m -- *************************************************** -- Функция возвращает список простых чисел из [2..] -- (второй способ) ---------------------- primes' = sieve' [2..] where sieve' (n:xs) = n : sieve' (filter (\m -> rem m n/=0) xs) -- *************************************************** -- Демонстрация вывода потока строк, которые конструи- -- руются по следующим правилам: -- -- (1) s ="0"; (2) s =s ++inv s , -- 1 k+1 k k -- -- где функция inv инвертирует все "биты" аргумента. -- -- Автор: Швецкий М.В. (08.12.2013, 20:25-20:32) -- *********************************************** morse = iterate inv "0" where inv str = str ++ map (\x -> if x=='1' then '0' else '1') str -- ************************************************************ -- Функция возвращает n-й элемент заданного списка -- (n=0,1,2,...) ----------------------- nth n (x:xs) | n==0 = x | True = nth (n-1) xs -- ******************************* -- Неудачные тестовые примеры: ----------------------------------- test1 = take 20 $ zip fibLst1 [0..] test2 = take 20 $ zip fibLst2 [0..] test3 = (nth 100 fibLst1,nth 100 fibLst2) test4 = (==) (take 2000 $ abc) (take 2000 $ cycle [-1,1]) test5 = take 100 (sieve [2..]) test6 = take 100 primes' test7 = take 10 morse
Корекурсию удобно использовать для генерации потоков, содержащих решения линейных и нелинейных рекуррентных соотношений.
Еще один демонстрационный пример.
-- Демонстрация конструирования потенциально бесконечных -- списков по рекуррентному соотношению второго порядка -- **************************************************** -- Функция возвращает поток по рекуррентному соотноше- -- нию второго порядка -- -- f(x )=f0, f(x )=f1, f(x )=2*x -x -- 0 1 n n-1 n-2 -- ------------------------------- f1 x0 x1 = x0 : f1 x1 (2*x1-x0) -- *************************************************** -- Функция возвращает поток по рекуррентному соотноше- -- нию второго порядка -- -- f(x )=f0, f(x )=f1, f(x )=x ^2 -x ^2 -- 0 1 n n-1 n-2 -- --------------------------------- f2 x0 x1 = x0 : f2 x1 (x1^2-x0^2) -- ********************************** -- Два варианта реализации вычислений ------------------------------------------- f3 x0 x1 k = x0 : f3 x1 (x1^2-x0+k^2) (k+1) ------------------------------------------- f31 n | n==0 = 1 | n==1 = 2 | True = (f31 (n-1))^2-f31 (n-2)+n^2 -- *************************************** -- Неудачные тестовые примеры: ------------------------------ test1 = take 12 (f1 1 3) test2 = take 12 (f2 0 1) test3 = take 12 (f3 1 2 2) == take 12 (map f31 [0..])
Разумеется, что можно построить корекурсивные функционалы, например, функционал comap:
comap f (x:xs) = f x : comap f xs
------------------------------------------
test1 = take 10 (comap (\x -> x^2) [1..5])
test2 = take 10 (comap (\x -> x^2) [1..])
test3 = take 10 (map (\x -> x^2) [1..])
Замечание (важное). Формально понятия "коданные" и "корекурсия" определяется в теории категорий.
(1)Душкин Р.В. Функциональное программирование на языке Haskell. - М.: ДМК Пресс, 2007. - 608 с.
На следующем шаге мы рассмотрим конструирование потенциально бесконечных списков с помощью двух точек "..".
