关于Haskell的参数性概念

Question

这是一本名为《Haskell编程入门》的书中的问题。

我正在阅读上述书籍，在第5章练习题“参数化”中，复制自该书。

从书中摘录：

通过查看 a -> a -> a，我们可以更舒适地理解参数化。这个假想函数 a -> a -> a 有两个且仅有两个实现。

我不明白“仅有两个实现”部分的含义？有人能解释一下为什么只有2个实现吗？

- Software Wisdom

---

我不确定我能够正式地解释，但试着想出一些方法，你能够实现一个函数，给定两个相同类型的元素，产生一个该类型的单一元素 - 对于每一个可以想象的类型。这个函数有两种可能的实现方式，而且（不正式地说）"你不能做别的事情"，因为你不能假设这个函数所接受的值的任何信息，因为你不知道它们的类型。 - Robin Zigmond

"\nf x y = x\n f x y = y\n f x y = x + y\n"，所以我定义了3个函数。 - Software Wisdom

最后一个并没有类型 a -> a -> a，而是 Num a => a -> a -> a。 - Li-yao Xia

假设我给你两个盒子，并告诉你这两个盒子里装的是同一种东西，但我没有告诉你具体是什么。现在我要求你以确定性的方式（不能使用 IO 翻转硬币），“诚实地”（不能打开盒子看里面装了什么，不能对我撒谎，也不能拿着盒子跑路不归）将同类物品交还给我。由于你对盒子里装的东西一无所知，因此你不能只是制造出同类物品——你必须将我给你的其中一个盒子还回去，而你只有两个可能的选择。 - Jon Purdy

@JonPurdy，那个解释相当不错，谢谢。 - Software Wisdom

Answer 1

我认为“implementations”这个词在一开始可能会有点令人困惑。

假设我们只有函数类型f :: a -> a -> a，没有其他信息；我们不能窥探f的内部。该函数必须返回一个a，且你只有两个可能的输入a。因此该函数必须返回第一个a或第二个a，只有两个可能的函数。

你不能使用f x y = x + y，因为你不知道如何将给定f :: a -> a -> a的两个a相加。如果你有一个函数h :: Int -> Int -> Int，那么h x y = x + y是合法的函数，但你没有给出f的此类信息。

同样地，如果f :: a -> a -> a，并且你声称f x y = x + y是有效的。那么，我可以通过将两个Fruit传递给f来打破你的说法：f Apple Orange = ???。那么Apple + Orange是不明确的，代码将无法工作。因此，保持类型多态性会“限制”两个可能的“实现”：f x y = x或f x y = y。

这个视频帮助我理解了。我建议整个视频，但链接是相关部分。(31:28)

它展示了类型级推理和参数化的强大之处。所有这种推理所需的信息都在类型中。

另一个例子，假设你只有一个函数类型g :: b -> b。那么，这个函数必须返回一个b，而唯一的参数也是一个b，因此它必须返回那个b。因此，只有一个这样的函数具有类型b -> b。

- dopamane

---

这是三个函数中的第三个返回undefined: f a b = undefined。还有更多的定义，例如f a b = f a b、f a b = f b a和f a b = f (f a b) (f b a)，但它们都会“返回”undefined。 - Will Ness

任何签名的函数都有可能返回undefined，而且它可以在根本不检查其参数/形参的情况下这样做。因此，它不算是参数化的。你提供的无限递归示例根本没有返回值，因此也不算。@DavOS：回答得好！ - AntC

@AntC 是的，我所说的是它们都会“返回”undefined（错误和循环都被视为底部）。因此，除去那种“解决方案”，实际上只有两个。但我们确实需要将它们排除在外。 - Will Ness

参数性是全函数的一个属性；返回undefined的东西被称为部分函数。 （术语“全函数”有点像回文词; 从历史上看，按定义，函数将其域的每个值映射到其共域中的一个值。在那种意义上，部分函数根本不是函数。） - chepner

对于部分函数，也存在参数性，只是稍微复杂一些，但仍然可以从类型中推导出规律。然而，在实践中，我认为每个人都使用完全的规律；在实际的 Haskell 中，假装大多数情况下一切都是完整的非常好，并将底部作为逃生口，如果事情变得非常微妙。但总体来说，“快速和松散”的推理方法效果还不错。 - luqui

Answer 2

有五个函数（在 Haskell 的纯表达式（非 IO 部分）中观察等价）具有最一般的类型 a -> a -> a。

f0 a b = f0 (f0 b a) (f0 a b) 

f1 a b = if True then a else b

f2 = flip f1

f3 a b = seq a (f2 a b)

f4 = flip f3

- Dave Sands

---

目前你的回答不够清晰，请编辑并添加更多细节，以帮助其他人理解它如何回答问题。你可以在帮助中心找到有关如何编写好答案的更多信息。 - Community