3

我正在学习递归方案，事实证明，针对列表类型实现它们对我很有帮助。然而，我被困在了同态。

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

似乎没有更多关于这个主题的初学者友好信息。我很感激任何帮助。

4

2 回答 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)
}                           }
于 2019-05-26T12:53:43.300 回答
2

Data.Functor.Foldable由递归方案包提供。那里的类​​型apo有：

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

这里，t是展开生成的结构，Base t是它的基本函子。从广义上讲，基本函子代表了递归结构的一层，其思想是，如果我们将其无限期地嵌套在自身内部，我们将获得与整个结构等效的类型——事实上，这正是FixfromData.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类型）限制为列表，并翻转 and 的角色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
于 2019-05-26T12:54:01.467 回答