值构造函数和元组有什么区别？

Question

据说 Haskell 元组只是代数数据类型的不同语法。同样，有一些例子展示了如何使用元组重新定义值构造函数。

例如，在 Haskell 中，Tree 数据类型可以这样写：

data Tree a = EmptyTree | Node a (Tree a) (Tree a)

这些内容可以转换为“元组形式”，如下所示：

data Tree a = EmptyTree | Node (a, Tree a, Tree a)

第一个例子中的Node值构造函数和第二个例子中的实际tuple有什么区别？即Node a (Tree a) (Tree a)与(a，Tree a，Tree a)（除了语法之外）？

在底层，Node a (Tree a) (Tree a)只是每个位置上适当类型的3元组的不同语法吗？

我知道可以部分应用值构造函数，例如Node 5，其类型为：(Node 5) :: Num a => Tree a -> Tree a -> Tree a 你也可以使用(,,)作为函数来部分应用元组...但这并不知道未绑定条目的潜在类型，例如：

Prelude> :t (,,) 5
(,,) 5 :: Num a => b -> c -> (a, b, c)

除非你使用::明确声明类型，否则不会有区别。

除了这种语法上的特殊性以及类型范围的最后一个示例之外，在Haskell中，“值构造器”实际上与用于存储相同类型的位置值的元组在本质上有什么区别吗？

- ely

Answer 1

概念上讲，实际上并没有区别，事实上其他语言（OCaml、Elm）也是以这种方式呈现标记联合的——即将标记放在元组或一级记录的前面（Haskell缺乏这一点）。我个人认为这是Haskell的一个设计缺陷。

不过，还是有一些实际的区别：

1. 惰性（Laziness）。Haskell的元组是惰性的，你不能改变这一点。但你可以把构造函数的字段标记为严格求值（strict）：

   data Tree a = EmptyTree | Node !a !(Tree a) !(Tree a)
   

2. 内存占用和性能。绕过中间类型可以减少占用空间并提高性能。您可以在这个很好的答案中阅读更多相关信息。

   您还可以使用UNPACK语法标记严格字段，以进一步减少内存占用。或者，您可以使用-funbox-strict-fields编译器选项。对于最后一个选项，我只是更喜欢在所有项目中默认启用它。例如，请参见Hasql的Cabal文件。

---

考虑到上述内容，如果你正在寻找惰性类型，那么以下代码段应该编译生成相同的结果：

data Tree a = EmptyTree | Node a (Tree a) (Tree a)

data Tree a = EmptyTree | Node {-# UNPACK #-} !(a, Tree a, Tree a)

所以我想说，使用元组来存储构造函数的延迟字段是可能的，而不会有任何惩罚。尽管应该提到这种模式在Haskell社区中有点不寻常。

如果你想要严格的类型和占用空间减小，那么除了直接将元组去规范化为构造函数字段外别无选择。

- Nikita Volkov

---

根据第2点，引入数据类型（而不是基于元组约定的函数）似乎主要是为了给模块的使用者带来的语义化效果：一种组织思考和阅读代码的方式。如果这样做不会对性能造成很大影响（我认为几乎总是如此，鉴于在Haskell中创建数据类型的普遍性），那么这种额外的语义收益就胜出了。但是，如果某个部分对性能非常关键，或者它是模块的私有部分，只有少数使用者需要，那么最好还是坚持使用元组约定。 - ely

当我说“元组约定”时，我的意思是设计用于操作未命名或未在数据类型中使用的元组的函数。我这样说是因为（我可能会被混淆），看起来你不能仅使用tuple创建递归数据类型，而不使用data或newtype关键字，否则将涉及到内存方面的考虑，对吗？ - ely

newtype 是一个仅在编译时存在的概念，在编译期间会被擦除。与 data 不同，它不会在包装的类型上引入任何内存开销。我的答案更新应该可以解释其余部分。 - Nikita Volkov

@prpl.mnky.dshwshr 没有理由出于性能原因而更喜欢元组而不是自定义数据类型。data CustomTuple a b c = CustomTuple a b c在 GHC 中的表示与(a, b, c)完全相同。尝试编译和运行main = print (unsafeCoerce (CustomTuple "hi" 32 True) :: (String, Integer, Bool))来验证这个说法（虽然编译很重要——runhaskell 和 ghci 在这里不起作用）。 - Daniel Wagner

@DanielWagner 关于元组内的递归，你怎么看？似乎只能通过值构造函数方法实现。你不能在右侧给一个包含 Foo 的元组赋予一个简写类型同义词，比如 Foo。（或者也许可以通过某种相互递归的方式实现？） - ely

@prpl.mnky.dshwshr 正确，有理由优先选择自定义数据类型而不是元组。我仅声称在性能方面没有理由优先选择元组而不是自定义数据类型。 - Daniel Wagner

Answer 2

它们被称为同构，意思是“具有相同的形状”。你可以写成这样

data Option a = None | Some a

而这与...同构

data Maybe a = Nothing | Just a

这意味着您可以编写两个函数。

f :: Maybe a -> Option a
g :: Option a -> Maybe a

对于所有可能的输入，使得f . g == id == g . f。然后我们可以说(,,)是一个与构造函数同构的数据构造函数。

data Triple a b c = Triple a b c

因为你可以写作

f :: (a, b, c) -> Triple a b c
f (a, b, c) = Triple a b c

g :: Triple a b c -> (a, b, c)
g (Triple a b c) = (a, b, c)

而 Node 作为构造函数是 Triple 的一个特殊情况，即 Triple a (Tree a) (Tree a)。实际上，你甚至可以说你对 Tree 的定义可以写成

newtype Tree' a = Tree' (Maybe (a, Tree' a, Tree' a))

newtype是必需的，因为你不能让type别名是递归的。你只需要声明EmptyLeaf == Tree' Nothing和Node a l r = Tree' (Just (a, l, r))即可。你可以编写相互转换的函数。

请注意，这一切都是从数学角度来看的。编译器可以添加额外的元数据和其他信息来标识特定构造函数，使它们在运行时表现略有不同。

- bheklilr

---

是的，我不是在讨论数学同构性.. 我对实际的内存表示感兴趣，以及是否存在实质上的差异。你可以说用 Py_Object 实现的 C 结构体表面上与 Python 类同构，但编写自己的 C 类型与使用 Python 的 class 或 type 工具之间显然存在差异。 - ely

@prpl.mnky.dshwshr，那么Nikita的回答更符合您的需求。 - bheklilr

是的，但这个也很好保留，以防数学能力较弱的人有同样的疑问并偶然发现这个问题。 - ely