我是否需要了解Haskell如何表示能够编写好的Haskell程序的数据？

Question

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

Answer 1

最简洁的答案是不.在Haskell中编程时,您应该将您的数据结构视为纯数学对象,而不必担心它们如何在内存中表示.这样做的原因是,在没有副作用的,没什么好说的,以数据,除了创建它的功能,你可以使用提取出其中它构建了简单的部分功能.

要查看有关数据构造函数的信息(:),或者任何其他术语,请使用GHCi中的:type(或只是:t简称)命令:

: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依次弹出每个s; 因此,访问最后一个元素是O(n),而对头部的访问是恒定时间.一旦你可以根据他们的定义对数据结构进行这种推理,你就可以了.