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

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

Вот реализация 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].

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

Вы можете установить пакет с помощью cabal install recursion-schemes.

Willem Van Onsem 26.05.2019 14:35
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
3
1
386
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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)

редактировать: более простой 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)?

Iven Marquardt 26.05.2019 15:08

это называется "шаблон". s относится к целому и одновременно соответствует (_:xs).

Will Ness 26.05.2019 15:09

Оба ответа очень полезны, и я хотел бы принять оба в общем режиме. Принятие не должно быть бинарным в SO в некоторых случаях.

Iven Marquardt 26.05.2019 15:30
Ответ принят как подходящий

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

Другие вопросы по теме