6

给定以下函数定义并假设所有正整数的定义相似，给出一个名为 plus 的函数的类型定义和代码，该函数将两个表示整数的此类函数作为参数，并返回一个表示两个输入整数之和的函数。例如，应该评估一个接受两个参数并返回(plus one two)的函数。f x(f(f(f x)))

one f x = f x
two f x = f (f x)
three f x = f (f (f x)))

等等

我是函数式编程的新手，我无法理解这一点。我首先不知道如何在不写出所有正整数的情况下定义函数（这显然是不可能的）。如，如果我有plus(sixty, forty)，我的函数如何识别 f 应用了 60 次 60 次x？

我打算用 Miranda 写这篇文章，但我对 Haskell 更熟悉，所以欢迎任何帮助。

4

3 回答 3

9

应用等式推理1和抽象。你有

one   f x =       f x                       -- :: (a -> b) -> a -> b
two   f x =    f (f x)   -- = f (one f x)   -- :: (a -> a) -> a -> a
three f x = f (f (f x))  -- = f (two f x)   -- :: (a -> a) -> a -> a
--                            ~~~~~~~~~~~

因此，自然定义了后继函数next，因此three = next two. 是的，它就像写next two而不是three上面的等式一样简单：

next :: ((b -> c) -> a -> b) -> (b -> c) -> a -> c
-- three f x = next two f x = f (two f x)   -- `two` is a formal parameter
--                            ~~~~~~~~~~~
next                num f x = f (num f x)   -- generic name `num`

zero :: t -> a -> a
zero f x = x

这捕捉到了继承的模式。f将用作后继函数，并x用作零值。其余的紧随其后。例如，

plus :: (t -> b -> c) -> (t -> a -> b) -> t -> a -> c
plus two one f x = two f (one f x)   -- formal parameters two, one
              -- = f (f (one f x))   -- an example substitution
              -- = f (f (f x)        --   uses the global definitions
              -- = three f x         --   for one, two, three

ie将被（而不是“通常” ）one f x用作零值，因此表示. “数字”表示连续的n 个操作。twoxthreen +1

同样，上面实际上定义了一般plus操作，因为two和one只是两个形式函数参数：

Prelude> plus three two succ 0    -- built-in `succ :: Enum a => a -> a`
5
Prelude> :t plus three two
plus three two :: (a -> a) -> a -> a
Prelude> plus three two (1:) [0]
[1,1,1,1,1,0]

这里要喘口气的关键是，函数是一个在调用时会产生值的对象。它本身就是一个不透明的物体。我们应用于它的“观察者”参数，为它提供了“意义”，它意味着什么是零，或者找到一个后继者，从而定义当我们观察一个数字的值时会产生什么结果。

1即在任何表达式中用定义的 RHS 自由替换 LHS，或者用 LHS 替换 RHS，如您认为合适的（直到变量重命名，当然，不捕获/隐藏现有的自由变量）。

于 2014-03-07T10:33:23.960 回答
5

要将数字转换为数字，您可以使用以下内容：

type Numeral = forall a . (a -> a) -> (a -> a)

toChurch :: Int -> Numeral
toChurch 0 _ x = x
toChurch n f x = f $ toChurch (pred n) f x

fromChurch :: Numeral -> Int
fromChurch numeral = numeral succ 0
于 2014-03-07T10:20:29.770 回答
1

您不需要知道函数调用了多少次f。例如，要实现succ将 1 加到 Church 数字上，您可以执行以下操作：

succ n f x = f (n f x)

然后你首先使用它需要多次n申请，然后你自己做最后的。你也可以反过来做，先自己申请一次，然后让其他人做。fffn

succ n f x = n f (f x)

您可以使用类似的技术来实现plus.

于 2014-03-07T10:09:53.743 回答