Какой тип апоморфизма характерен для списка и как он реализован?

Question

Я изучаю схемы рекурсии, и для меня оказалось очень полезным реализовать их в соответствии с типом списка. Однако я застрял на апоморфизмах.

Вот реализация tails в терминах апо, которые я недавно нашел:

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].

Похоже, больше нет дружеской информации для начинающих по этому вопросу. Я ценю любую помощь.

Answer 1

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

Answer 2

Тип

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)