java - 我需要了解 Haskell 如何表示数据才能编写好的 Haskell 程序吗？

Question

我是从 Java 背景开始学习 Haskell 的。当我编写 Java 程序时，我觉得我对对象在内存中的布局方式及其后果有着深刻的理解。例如，我确切地知道 java.lang.String 和 java.util.LinkedList 是如何工作的，因此我知道我应该如何使用它们。对于 Haskell，我有点迷路了。例如，(:) 是如何工作的？我应该关心吗？是否在某处指定？

Answer 1

简短的回答是否定的。在 Haskell 中编程时，您应该将数据结构视为纯数学对象，而不用担心它们在内存中的表示方式。这样做的原因是，在没有副作用的情况下，除了创建数据的函数和可用于提取构建数据的更简单部分的函数之外，实际上没有任何数据.

要查看有关数据构造函数的信息，如 (:) 或任何其他术语，请使用 :type(或仅使用 :t短)GHCi 中的命令:

:Prelude> :type (:)
(:) :: a -> [a] -> [a]

这告诉您 (:) 构造函数(发音为“cons”)接受任何类型的值和相同类型的列表，并返回相同类型的列表。您还可以使用 :info 命令获取更多信息。这将向您展示数据定义的样子:

Prelude> :info (:)
data [] a = ... | a : [a]   -- Defined in GHC.Types
infixr 5 :

这告诉您 (:) 是将元素添加到现有列表的构造函数。

我也强烈推荐Hoogle不仅可以按名称查找内容，还可以进行反向搜索；你知道你正在寻找的函数的签名，并想知​​道是否有人已经为你编写了它。 Hoogle 很好，因为它提供了描述和示例用法。

归纳数据的形状

我在上面说过，了解数据在内存中的表示形式并不重要...但是，您应该了解正在处理的数据的形状，以避免性能不佳决定。 Haskell 中的所有数据都是归纳定义的，这意味着它具有树状形状，递归地向外展开。您可以通过查看数据的定义来判断数据的形状；一旦您知道如何阅读此内容，它的性能特征就真的没有隐藏的东西了:

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

从定义中可以看出，获得新的 MyList 的唯一方法是通过 Cons 构造函数。如果你多次使用这个构造函数，你最终会得到大致如下形状的东西:

(Cons a5 (Cons a4 (Cons a3 (Cons a2 (Cons a1 Nil)))))

它只是一棵没有分支的树，这就是列表的定义!到达 a1 的唯一方法是依次弹出每个 Cons；因此访问最后一个元素是O(n)，而访问头部是常数时间。一旦您可以根据定义对数据结构进行这种推理，您就大功告成了。