列表特有的同构类型是什么？它是如何实现的？

Question

我正在学习递归方案，事实证明它对我实现特定于列表类型的方案非常有帮助。但是，我卡在同构上了。

这是我最近发现的关于 apo 的 tails 的实现：

import Data.Functor.Foldable

tailsApo :: [a] -> [[a]]
tailsApo = apo coalgTails
    where
    coalgTails = \case
        [] -> Cons [] (Left [])
        li@(_:xs) -> Cons li (Right xs)

不幸的是，我无法使用 GHCi 导入 Data.Functor.Foldable，因为我遇到了找不到包的错误。另一项搜索揭示了特定于列表的 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

The type is

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] we'll have

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)
}                           }

Answer 2

Data.Functor.Foldable 由 recursion-schemes 包提供。 apo的类型有：

apo :: Corecursive t => (a -> Base t (Either t a)) -> a -> t

这里，t是展开生成的结构，Base t是它的基函子。从广义上讲，基函子代表递归结构的一个层次，其思想是如果我们无限期地将它嵌套在自身中，我们将得到一个等同于整个结构的类型——事实上，这正是 Fix来自 Data.Functor.Foldable 确实如此。（在元注释中，这里似乎没有专门针对 recursion-schemes 中的 Base 的问答；有一个可能会有用。）

Base 对于列表是：

data ListF a b = Nil | Cons a b

所以 apo 专门用于：

apo @[_] :: (b -> ListF a (Either [a] b)) -> b -> [a]

如果我们想在不使用 recursion-scheme 基础设施的情况下编写它，我们可以利用 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，在recursion-schemes version) 信号列表的生成应该通过用空尾来加盖来停止。这就是为什么您仍然需要 Maybe，即使您还使用 Either 以 short-circuit 以其他方式展开。

此 apoList 的实现与您问题中的实现非常相似，除了此签名不将种子（b 类型）限制为列表，并将Left 和 Right 的角色（因此 Left 信号 short-circuiting）：

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

列表特有的同构类型是什么？它是如何实现的？

What is the type of apomorphism specific to list and how is it implemented?

haskell

unfold

recursion-schemes