Я изучаю схемы рекурсии, и мне оказалось очень полезным реализовать их для конкретного типа списка. Однако я застрял на апоморфизмах.
Вот реализация tails
с точки зрения apo, которую я недавно нашел:
import Data.Functor.Foldable
tailsApo :: [a] -> [[a]]
tailsApo = apo coalgTails
where
coalgTails = \case
[] -> Cons [] (Left [])
li@(_:xs) -> Cons li (Right xs)
К сожалению, я не могу импортировать Data.Functor.Foldable
с помощью GHCi, потому что получаю ошибку «Пакет не найден». Другой поиск выявил эту реализацию apo, специфичную для списков:
apoList :: ([b] -> Maybe (a, Either [b] [a])) -> [b] -> [a]
apoList f b = case f b of
Nothing -> []
Just (x, Left c) -> x : apoL f c
Just (x, Right e) -> x : e
Очевидно, что первый аргумент apoList
не совпадает с tailsApo
. Я бы ожидал, что тип будет чем-то вроде apoList :: ([b] -> Either (a, b) [a])) -> [b] -> [a]
.
Кажется, нет более удобной для начинающих информации по этому вопросу. Я ценю любую помощь.
apo :: (a -> Base t (Either t a )) -- g :: a -> Base t r
-> a -> t
apo g a = rec a where -- rec = apo g :: a -> t
rec = embed . fmap (either id rec) . g
{-
type family Base t :: * -> *
embed :: Base t t -> t
fmap (either id rec) :: Base t r -> Base t t
either id rec :: r -> t r ~ Either t a
g :: a -> Base t r r ~ Either t a
rec = apo g :: a -> t
-}
Вот a
семя. Для t ~ [b]
у нас будет
type instance Base [b] = ListF b
data ListF b r = Nil | Cons b r
Base t (Either t a) ~ ListF b (Either [b] a)
~ Maybe (b, Either [b] a)
так в целом будет
apoList :: (a -> Maybe (b, Either [b] a)) -> a -> [b]
apoList coalg a = case coalg a of
Nothing -> [] -- (embed Nil ) -- either
Just (b, Left bs) -> b : bs -- no more seed, no more steps to do! -- id $ bs
Just (b, Right a) -> b : apoList coalg a -- new seed, go on! -- apo g $ a
-- ^^^^^ (embed (Cons b bs))
так
apoTails :: [a] -> [[a]] -- [[a]] ~ [b], b ~ [a]
apoTails = apoList tailsCoalg
where
-- tailsCoalg :: [a] -> Maybe ([a], Either [[a]] [a])
tailsCoalg [] = Just ([], Left [])
tailsCoalg s@(_:xs) = Just (s, Right xs)
редактировать: более простой apoList
с более простой типизированной коалгеброй,
apoListE :: (a -> Either [b] (b, a)) -> a -> [b]
apoListE coalg a = case coalg a of
Left bs -> bs -- final tail, whether empty or non-empty
Right (b, a) -> b : apoListE coalg a -- new element and seed, go on!
кажется проще в использовании:
apoTailsE :: [a] -> [[a]]
apoTailsE = apoListE tailsCoalgE
where
-- tailsCoalgE :: [a] -> Either [[a]] ([a], [a])
tailsCoalgE [] = Left [[]]
tailsCoalgE s@(_:xs) = Right (s, xs)
Похоже, что два типа эквивалентны:
type instance Base [b] = ListF b
data ListF b r = Nil | Cons b r
Base t (Either t a) ~ ListF b (Either [b] a)
~ Maybe (b, Either [b] a)
~ Either [b] (b, a)
--------------------------------------------------------------------
Maybe (b, Either [b] a) ~ Either [b] (b, a)
{ Nothing, ~ { Left [],
Just (b, Left bs), Left (b:bs),
Just (b, Right a) Right (b, a)
} }
Что означает s@(_:xs)
?
это называется "шаблон". s
относится к целому и одновременно соответствует (_:xs)
.
Оба ответа очень полезны, и я хотел бы принять оба в общем режиме. Принятие не должно быть бинарным в SO в некоторых случаях.
Data.Functor.Foldable
предоставляется пакетом схемы рекурсии. Тип apo
есть:
apo :: Corecursive t => (a -> Base t (Either t a)) -> a -> t
Здесь t
— структура, порождаемая развёрткой, а Base t
— её базовый функтор. Вообще говоря, базовый функтор представляет один уровень рекурсивной структуры, и идея состоит в том, что если мы неопределенно вложим его внутрь себя, мы получим тип, эквивалентный типу всей структуры — на самом деле именно это и делает Fix
из Data.Functor.Foldable
. (В мета-примечании, похоже, здесь нет вопросов и ответов конкретно о Base
в схемы рекурсии; было бы полезно иметь его.)
Base
для списков:
data ListF a b = Nil | Cons a b
Итак, apo
специализируется на:
apo @[_] :: (b -> ListF a (Either [a] b)) -> b -> [a]
Если мы хотим написать его без использования инфраструктуры схема рекурсии, мы можем использовать тот факт, что ListF a b
изоморфен Maybe (a, b)
:
Nil | Cons a b
Nothing | Just (a, b)
С точки зрения Maybe (a, b)
подпись будет выглядеть так:
apoList :: (b -> Maybe (a, Either [a] b)) -> b -> [a]
В коалгебре (то есть аргумент функции для apo
), Nothing
(или Nil
, в версии схемы рекурсии) сигнализирует, что генерацию списка следует остановить, закрыв его пустым хвостом. Вот почему вам по-прежнему нужен Maybe
, даже если вы также используете Either
, чтобы сократить развертывание другими способами.
Реализация этого apoList
очень похожа на ту, что указана в вашем вопросе, за исключением того, что эта подпись не ограничивает начальное число (типа b
) списком и меняет роли Left
и Right
(так что Left
сигнализирует о коротком замыкании ):
apoList :: (b -> Maybe (a, Either [a] b)) -> b -> [a]
apoList f b = case f b of
Nothing -> []
Just (x, Left e) -> x : e
Just (x, Right c) -> x : apoList f c
Вы можете установить пакет с помощью
cabal install recursion-schemes
.