haskell - 使用函数创建列表类型

Question

对于一个愚蠢的挑战，我尝试使用尽可能少的前奏而不使用任何自定义类型(data 关键字)来实现列表类型。

我可以使用元组构造一个修改列表，如下所示:

import Prelude (Int(..), Num(..), Eq(..))

cons x = (x, ())
prepend x xs = (x, xs) 
head (x, _) = x
tail (_, x) = x

at xs n = if n == 0 then xs else at (tail xs) (n-1)

我想不出如何编写 at (!!) 函数。这甚至可以在静态语言中实现吗？
如果可能的话，您能否在不告诉我答案的情况下尝试将我推向正确的方向。

Answer 1

有一个标准技巧称为 Church encoding这使得这很容易。这是一个让您入门的通用示例:

data Foo = A Int Bool | B String
fooValue1 = A 3 False
fooValue2 = B "hello!"

现在，想要使用这条数据的函数必须知道如何处理每个构造函数。所以，假设它想要产生一些 r 类型的结果。 ，它至少必须有两个函数，一个是 Int -> Bool -> r 类型。 (处理 A 构造函数)，另一个类型为 String -> r (处理 B 构造函数)。事实上，我们可以这样写类型:

type Foo r = (Int -> Bool -> r) -> (String -> r) -> r

您应该阅读类型 Foo r这里的意思是“一个消耗 Foo 并产生 r 的函数”。类型本身“存储”一个 Foo在一个闭包内——这样它就可以有效地将它的一个或另一个参数应用于它关闭的值。使用这个想法，我们可以重写 fooValue1和 fooValue2 :

fooValue1 = \consumeA consumeB -> consumeA 3 False
fooValue2 = \consumeA consumeB -> consumeB "hello!"

现在，让我们尝试将这个技巧应用到实际列表中(尽管不使用 Haskell 的花哨语法糖)。

data List a = Nil | Cons a (List a)

遵循与以前相同的格式，使用这样的列表需要给出 r 类型的值。 (如果构造函数是 Nil )或告诉如何处理 a和另一个 List a ， 所以。起初，这似乎有问题，因为:

type List a r = (r) -> (a -> List a -> r) -> r

不是很好 type (它是递归的!)。但是我们可以要求我们首先将所有递归参数减少到 r。首先...然后我们可以调整这种类型以使其更合理。

type List a r = (r) -> (a -> r -> r) -> r

(同样，我们应该将类型 List a r 理解为“一个消耗 a 列表并产生 r 的事物”。)

最后一个技巧是必要的。我们想做的是强制要求 r我们的 List a r return 实际上是由我们传递的参数构造的。这有点抽象，所以让我们举一个碰巧类型为 List a r 的错误值的示例。 ，但我们想排除。

badList = \consumeNil consumeCons -> False

现在， badList有类型 List a Bool ，但它并不是一个真正使用列表并产生 Bool 的函数，因为从某种意义上说，没有列表被消耗。我们可以通过要求该类型适用于任何 r 来排除这种情况。 ，无论用户想要什么 r成为:

type List a = forall r. (r) -> (a -> r -> r) -> r

这强化了获得 r 的唯一方法的想法。让我们起步的方法是使用(用户提供的) consumeNil功能。你能看到如何对我们原来的 Foo 进行同样的改进吗？类型？