从Int-> Int的递归方案？

Question

文件夹标识为

foldr (:) []

更一般而言，通过折叠，您可以销毁结构并以汇总值结束，或者以使结构以相同的输出结构结束的方式注入结构。

[Int] -> [Int] 或 [Int] -> Int 或 [Int] -> ?

我想知道unfoldr / l是否具有相似的身份。

我知道如何得到

Int -> [Int]

与展开/安娜。

我正在寻找某种方式

Int -> Int

递归方案。

Answer 1

从您关于阶乘的评论中可以看出，我们可以注意到自然数可以视为递归数据结构：

data Nat = Zero | Succ Nat

就递归方案机制而言，相应的基函是：

data NatF a = ZeroF | SuccF a
    deriving (Functor)

NatF但是，与是同构的Maybe。既然如此，递归的方案便利地使Maybe的基函子的Natural从型基。例如，这是ana专门用于Natural：

ana @Natural :: (a -> Maybe a) -> a -> Natural

我们可以用它来写以下内容的身份Natural：

{-# LANGUAGE LambdaCase #-}

import Numeric.Natural
import Data.Functor.Foldable

idNatAna :: Natural -> Natural
idNatAna = ana $ \case
    0 -> Nothing
    x -> Just (x - 1)

我们只是给了余代数ana是project对Natural，project在于解开递归结构中的一层的功能。就递归方案词汇而言，ana project身份是展开的，cata embed也是身份折叠的。（特别是，projectfor列表是unconsfrom的Data.List，除了它使用ListF代替编码Maybe。）

顺便说一下，阶乘函数可以表示为自然的同态（如该问题结尾处的注释所指出的）。我们还可以根据递归方案来实现：

fact :: Natural -> Natural
fact = para $ \case
    Nothing -> 1
    Just (predec, prod) -> prod * (predec + 1)

para在每个递归步骤中，都会提供要折叠结构的其余部分（如果我们要折叠一个列表，那将是它的尾部）。在这种情况下，我调用了这样提供的值，predec因为在n从底部到顶部的第-递归步骤中predec为n - 1。

请注意，如果您碰巧的话，user11228628的同胚可能是更有效的实现。（不过，我还没有对它们进行基准测试。）