haskell - `refold::Functor s => (a -> s a, a) -> (s b -> b) -> b` 作为通用类型之间的态射

Question

各种递归方案归结为 refold 的特定实例化

refold :: Functor s => (s b -> b) -> (a -> s a) -> a -> b
refold f g = go where go a = f (fmap go (g a))

refold的有意义的解释是什么?
数据类型 data Nu f = forall a. Nu (a -> f a) a和 newtype Mu f = Mu {unMu :: forall b. (f b -> b) -> b}可以看作是余代数和代数中忘记仿函数的上界和极限， refold是它们之间的态射，但它是否揭示了 refold ?

refold' :: forall s. Functor s => Nu s -> Mu s
refold' (Nu g (a :: a)) = Mu mu where

  mu :: forall b. (s b -> b) -> b
  mu f = go a where

    go :: a -> b
    go a = f (fmap go (g a))

Answer 1

我想这取决于您所说的“有意义的解释”是什么意思。
如果 s是递归数据类型和核心递归余数据类型的基本仿函数，如以下仿函数 s ~ ListF e对于递归列表数据类型[e] (在 Haskell 中，它也是一种核心递归流 codata 类型):

{-# LANGUAGE DeriveFunctor #-}
data ListF e b = Nil | Cons e b deriving (Show, Functor)

然后是 s - a -> s a 类型的代数连同起始种子 a可以生成 codata 类型的值 [e]通过从那颗种子展开，而 s - s b -> b 类型的代数可以使用数据类型 [e] 的值通过折叠成 b 类型的值. refold函数只是结合了从 a 展开的操作并折叠成 b ，而无需实际创建中间 codata/data 类型。
例如，您可以生成(有限)余数据流 [10,9..1]通过从 Integer 展开种子使用起始值/代数对 (a,g)如下:

a :: Integer
a = 10

g :: Integer -> (ListF Integer) Integer
g 0 = Nil
g n = Cons n (n-1)

并折叠一个列表来计算它的 Int使用代数的长度:

f :: (ListF Integer) Int -> Int
f Nil = 0
f (Cons _ b) = 1 + b

refold函数只是结合了这些操作:

main = print $ refold f g a

在这种特殊情况下，它计算长度 10流/列表的 [1..10]没有实际创建任何中间流/列表。
我猜直觉是，如果一个操作可以被想象为一个 F 递归应用于同一个仿函数 F 的 F 核递归，那么它就是 refold。 .或者，也许更实际地，如果算法具有与仿函数 F 匹配的内部递归结构，则它可以表示为 refold . documentation对于 refold在 recursion-schemes给出了具有与二叉树匹配的递归结构的快速排序示例，尽管您可能已经看过该示例。
注意:以下内容是错误的，或者充其量是不精确的，但我会尝试多考虑一下。
在实践中， refold不仅用作通用数据类型之间的态射，而且如果你有一个余数据类型的最终 s-coalgebra C与仿函数相关 s :

eatC :: C -> ListF Integer C

和数据类型 D 的初始 s 代数也与仿函数 s 相关联:

makeD :: ListF Integer D -> D

然后 refold makeD eatC应该是来自 codata 类型 C 的自然态射数据类型 D .也就是说，它应该是满足的唯一态射:

fmap h . refold makeD eatC = refold makeD eatC . fmap h

我不确定这方面是否非常有趣......