0

文件夹身份是

foldr (:) []

更一般地说，使用折叠，您可以破坏结构并最终得到一个汇总值，或者以这样一种方式注入结构，最终得到相同的输出结构。

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

我想知道展开器/l 是否有类似的身份。

我知道如何获得

Int -> [Int]

与展开/安娜。

我正在寻找某种方式

Int -> Int

使用递归方案。

4

2 回答 2

5

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

data Nat = Zero | Succ Nat

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

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

NatF然而，与 同构Maybe。既然如此，recursion-schemes可以方便地从base生成类型Maybe的 base 函子。例如，这里是专门 to的类型：NaturalanaNatural

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是projectforNatural，project是展开一层递归结构的函数。就递归方案词汇而言，ana project是恒等展开，cata embed是恒等折叠。（特别是，project对于列表是unconsfrom Data.List，除了它是用ListF而不是编码的Maybe。）

顺便说一句，阶乘函数可以表示为自然数的一个变形（如本问题末尾的注释中所指出的那样）。我们也可以用递归方案来实现它：

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

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

注意user11228628 的 hylomorphism可能是一个更有效的实现，如果你碰巧关心的话。（不过，我还没有对它们进行基准测试。）

于 2019-05-06T21:35:48.140 回答
3

处理建立中间结构并将其拆除以使该结构不出现在输入或输出中的递归方案是一种hylomorphism，拼写hylo为recursion-schemes.

要使用hylomorphism，您需要指定一个代数（消耗递归结构的一个步骤的东西）和一个余代数（产生递归结构的一个步骤的东西），并且您需要具有该结构的数据类型当然，您正在使用。

你建议阶乘，所以让我们看看如何把它写成一个hylomorphism。

查看阶乘的一种方法是作为从初始值倒数的数字列表的乘积n。在这个框架中，我们可以将产品视为我们的代数，一次拆下一个缺点列表，将倒计时视为我们的代数，建立n递减的列表。

recursion-schemes为我们ListF提供了一个方便的基础仿函数列表，因此我们将使用它作为由代数产生并由代数使用的数据类型。它的构造函数是Niland Cons，这当然类似于完整列表的构造函数，除了 aListF与递归方案中的任何基本结构一样，在列表将使用实际递归的地方使用类型参数（意味着Cons :: a -> b -> ListF a b代替(:) :: a -> [a] -> [a]）。

所以这决定了我们的类型。现在定义fact是一个相当填空的练习：

import Prelude hiding (product)
import Data.Functor.Foldable

product :: ListF Int Int -> Int
product Nil = 1
product (Cons a b) = a * b

countDown :: Int -> ListF Int Int
countDown 0 = Nil
countDown n = Cons n (n - 1)

fact :: Int -> Int
fact = hylo product countDown
于 2019-05-06T20:56:43.493 回答