12

用函数式语言设计数据结构时,有两种选择:

  1. 公开它们的构造函数和模式匹配。
  2. 隐藏它们的构造函数并使用更高级别的函数来检查数据结构。

在什么情况下,什么是合适的?

模式匹配可以使代码更具可读性或更简单。另一方面,如果我们需要更改数据类型定义中的某些内容,那么我们对它们进行模式匹配(或构造它们)的所有地方都需要更新。


我自己一直在问这个问题一段时间。我经常会从一个简单的数据结构(甚至是type别名)开始,并且似乎构造函数 + 模式匹配将是最简单的方法,并且可以生成干净易读的代码。但是后来事情变得更复杂了,我必须更改数据类型定义并重构大部分代码。

4

5 回答 5

10

对我来说,最重要的因素是对以下问题的回答:

我的数据类型的结构与外界相关吗?

例如,列表数据类型的内部结构与外部世界非常相关——它有一个归纳结构,这对于暴露给消费者来说肯定非常有用,因为它们构造了通过对列表结构进行归纳的函数。如果列表是有限的,那么这些函数保证会终止。此外,以这种方式定义函数可以很容易地提供关于它们的属性,同样通过归纳。

相比之下,Set数据类型最好保持抽象。在内部,它被实现为containers包中的树。但是,它也可以使用数组来实现,或者(在功能设置中更有用)使用具有略微不同结构并尊重不同不变量(平衡或不平衡,分支因子等)的树。顺便说一句,在构造函数已经通过其类型强制执行的那些不变量之上和之上强制执行任何不变量的需要排除了让数据类型具体化的可能性。

列表示例和集合示例之间的本质区别在于,Set数据类型Set与's上可能的操作相关。而列表是相关的,因为标准库已经提供了许多作用于它们的函数,而且它们的结构相关的。

作为旁注,有人可能会反对实际上列表的归纳结构,它对于编写终止和行为易于推理的函数非常重要,它被两个使用列表的函数抽象地捕获:foldrfoldl。鉴于这两个基本的列表运算符,大多数函数根本不需要检查列表的结构,因此可以说列表过于抽象。这个论点推广到许多其他类似的结构,例如所有Traversable结构、所有Foldable结构等。但是,几乎不可能捕获列表上所有可能的递归模式,事实上许多函数根本不是递归的。只给出foldrand foldl,一个人会写head例如,尽管很乏味,但仍然可以使用:

head xs = fromJust $ foldl (\b x -> maybe (Just x) Just b) Nothing xs

我们最好只是放弃列表的内部结构。

最后一点是,有时数据类型的实际表示与外部世界无关,因为说它是某种优化的并且可能不是规范表示,或者没有单一的“规范”表示。在这些情况下,您需要保持数据类型抽象,但提供数据类型的“视图”,它确实提供了可以进行模式匹配的具体表示。

一个例子是,如果想要定义一种Complex复数数据类型,笛卡尔形式和极坐标形式都可以被认为是规范的。在这种情况下,您将保持Complex抽象,但导出两个视图,即函数polar,并cartesian分别返回一对长度和角度或笛卡尔平面中的坐标。

于 2012-09-06T15:37:28.190 回答
7

好吧,规则很简单:如果使用实际构造函数很容易构造错误值,那么就不要直接使用它们,而是提供智能构造函数。这是一些数据结构所遵循的路径,例如Mapand Set,很容易出错。

然后是不可能或难以构造不一致/错误值的类型,因为该类型根本不允许这样做,或者因为您需要引入底部。长度索引列表类型(通常称为Vec)和大多数 monad 就是这样的例子。

最终这是你自己的决定。站在用户的角度,在方便和安全之间做出权衡。如果没有权衡,则始终公开构造函数。否则你的图书馆用户会因为不必要的不​​透明而讨厌你。

于 2012-09-06T15:30:04.400 回答
5

如果数据类型服务于一个简单的目的(如),并且通过数据构造函数直接构造一个值Maybe a不会违反关于数据类型的任何(显式或隐式)假设,我将公开构造函数。

另一方面,如果数据类型更复杂(如平衡树)和/或其内部表示可能会发生变化,我通常会隐藏构造函数。使用包时,有一条不成文的规则,即非内部模块公开的接口对于给定数据类型使用应该是“安全的”。考虑平衡树示例,公开数据构造函数允许(意外地)构造一棵不平衡树,因此可能会违反假设的搜索树等运行时保证。

于 2012-09-06T15:26:06.213 回答
3

如果该类型用于表示具有规范定义和表示的值(许多数学对象属于此类),并且不可能使用该类型构造“无效”值,那么您应该公开构造函数。

例如,如果您用自己的类型(包括新类型)表示二维点,您不妨公开构造函数。现实情况是,对这种数据类型的更改不会改变 2d 点的表示方式,而是会改变您使用 2d 点的需求(也许您正在推广到 3d 空间,也许您是添加层的概念或其他),并且几乎可以肯定,无论您做什么,都需要注意使用这种类型的值的代码部分。 [1]

表示特定于您的应用程序或领域的事物的复杂类型很可能会在继续支持类似操作的同时对表示进行更改。因此,您只需要取决于操作的其他模块,而不是内部结构。所以你不应该暴露构造函数。

其他类型表示具有规范定义但不是规范表示的事物。每个人都知道映射和集合所期望的属性,但是有很多不同的方式来表示支持这些属性的值。因此,您再次只需要其他模块,具体取决于它们支持的操作,而不是特定的表示。

某些类型,无论它们是否简单,是否具有规范表示,都允许在程序中构造不代表该类型应该表示的抽象概念中的有效值的值。一个简单的例子是表示自平衡二叉搜索树的类型;可以访问构造函数的客户端代码可以很容易地构造无效树。暴露构造函数要么意味着您需要假设从外部传入的这些值可能是无效的,因此即使对于奇怪的值,您也需要做出合理的事情,或者意味着使用您的接口的程序员有责任确保他们不这样做'不违反任何假设。通常最好不要直接在模块外部构建此类类型。

基本上它归结为您的类型应该代表的概念。如果您的概念以一种非常简单和明显[2] 的方式直接映射到某些数据类型中的值,由于编译器无法检查所需的不变量,该数据类型并不比概念“更具包容性”,那么这个概念几乎是“与数据类型相同”,并且暴露其结构就可以了。如果没有,那么您可能需要隐藏结构。


[1] 一个可能的变化是更改您用于坐标值的数字类型,因此您可能必须考虑如何最大限度地减少此类更改的影响。这与您是否公开构造函数非常正交。

[2] 这里的“显而易见”的意思是,如果你让 10 个人独立提出一个代表概念的数据类型,他们都会返回相同的东西,模数更改名称。

于 2012-09-07T01:40:07.787 回答
1

我会提出一个不同的、明显比大多数人更严格的规则。中心标准是:

你保证这种类型永远不会改变吗?如果是这样,暴露构造函数可能是一个好主意。不过,祝你好运!

但是您可以保证的类型往往是非常简单的通用“基础”类型,例如Maybe, Eitheror [],可以说可以编写一次,然后再也不会重新访问。

尽管即使是那些也可能会受到质疑,因为它们确实会不时地被重新审视;出于性能原因,有些人在各种情况下都使用了 Church 编码的版本Maybe,例如:List

{-# LANGUAGE RankNTypes #-}

newtype Maybe' a = Maybe' { elimMaybe' :: forall r. r -> (a -> r) -> r }
nothing = Maybe' $ \z k -> z
just x = Maybe' $ \z k -> k x

newtype List' a = List' { elimList' :: forall r. (a -> r -> r) -> r -> r }
nil = List' $ \k z -> z
cons x xs = List' $ \k z -> k x (elimList' k z xs)

这两个示例强调了一些重要的事情:您可以将Maybe'上面显示的类型的实现替换为任何其他实现,只要它支持以下三个功能:

nothing :: Maybe' a
just :: a -> Maybe' a
elimMaybe' :: Maybe' a -> r -> (a -> r) -> r

...以及以下法律:

elimMaybe' nothing z x  == z
elimMaybe' (just x) z f == f x

这种技术可以应用于任何代数数据类型。对我来说,与具体构造函数的模式匹配不够抽象;它并没有真正为您带来任何您无法摆脱抽象构造函数 + 析构函数模式的东西,并且它失去了实现的灵活性。

于 2012-09-07T17:44:38.697 回答