haskell 在函数式编程中,为什么Maybe函子没有被定义为数据Maybe a = Nothing| a?

70gysomp  于 2023-06-06  发布在  其他
关注(0)|答案(4)|浏览(216)

我想知道为什么在Haskell(和一般的FP)中,像Maybe这样的函子被定义为

data Maybe a = Nothing | Just a

而不是简单地

data Maybe a = Nothing | a

第二个选项仍然是函子,因为Maybe函子将类型a转换为类型Nothing + a。我错过了什么?

emeijp43

emeijp431#

这就是所谓的“非歧视性联合”,与“歧视性”联合相对-Just是“歧视者”。一些语言确实有它们-例如。TypeScript。
但他们也有自己的困难。采取类型推断:如果我写let x = "foo"x是什么类型?是String还是Maybe String
不过,最终这只是语言设计者的选择。在实践中,有歧视的工会比无歧视的工会更有用,所以Haskell有这些工会。

ar7v8xwq

ar7v8xwq2#

data定义的右侧必须定义 data 构造函数。裸a只是一个类型变量。

data Maybe a = Nothing | Just a

Nothing是类型为Maybe a的空值数据构造函数。Just是类型为a -> Maybe a的一元数据构造函数。与函数类似,它接受a类型的参数以生成Maybe a类型的值。(与函数不同,您可以使用它进行模式匹配。)

> :t Nothing
   Nothing :: Maybe a
   > :t Just
   Just :: a -> Maybe a
   > :t Just 'c'
   Just 'c' :: Maybe Char
   > :t Just 3
   Just 3 :: Num a => Maybe a
lmvvr0a8

lmvvr0a83#

让我们从最基本的东西开始:可以在Maybe a上进行模式匹配。这意味着在运行时求值器需要能够查看内存中Maybe a类型的值,并在以下代码中告诉哪个分支:

case (mx :: Maybe a) of
  Nothing -> ...
  Just x -> ...

求值器需要能够在不知道任何关于a类型的情况下进行区分。所以在运行时,内存中表示mx :: Maybe a的结构必须有足够的信息来进行区分。Nothing很简单,因为它只是一个常数,不包含其他值,所以它可以只是一个已知的固定值;例如,假设我们决定它应该是一个全0位的机器字。然后,当模式匹配是看mx,如果它找到一个全零字,我们采取Nothing分支,如果我们找到一些非零,我们采取Just分支。很简单,对吧?
为此,我们假设Just x的值将不同于Nothing的值**,无论x是什么**。但是这必须在不知道a类型的情况下工作,所以x可以是任何类型的任何值,我们无法控制它们在内存中的表示方式。如果我们只是将Just x值表示为x的内存结构,而没有额外的 Package ,那么任何时候x的表示碰巧是(或以)一个全零字,我们都会认为我们有Nothing,而实际上不是这样。
特别是a类型可能是Maybe b,这意味着我们的Just x可能是Just Nothing;内部的值可以是Nothing,因此根据定义,自动存在一些x值,其在内存中具有与Nothing相同的表示。但是嵌套的maybes绝不是嵌套值可能具有与Nothing冲突的内存表示的唯一情况,所以不要认为这只是一个模糊的情况; False也是一个空构造函数,分配内存表示的算法没有理由不分配与Nothing相同的位模式; LT :: Ordering,或者 any enum类型的第一个值也是如此。基本数字和字符类型也没有理由避免这种特定的位模式(无论是全零还是我们选择其他)。
只有两种方法可以让它工作,真的。
一种是给予Maybe类型作为一种组合类型,它像其他ADT一样工作。相反,您可以将其作为一种特殊情况,即每个类型都有一个“可空”版本,但它不嵌套。你用一些全局可识别的东西(比如一个空指针)来表示null情况,而不是使用所有其他值所使用的内存布局。这是许多命令式语言所采用的方法,它们从提高“空安全性”的方向来处理这个问题,但这不是Haskell所采用的方法。Maybe是一个完全普通的ADT,不需要被烘焙到编译器中,它是可嵌套的和组合的,不强加任何额外的规则,必须由学习者记忆。
第二个是不要试图用与x相同的内存结构来表示Just xJust数据构造函数本身需要有一个内存记录,至少有一个位将其与Nothing区分开来,并且有空间让它包含**x(而不是简单地 * 成为 * x)。现在我们可以依靠能够区分NothingJust,一旦我们知道我们有一个Just,我们就知道在哪里寻找x部分,无论它是什么类型。这就是Haskell所做的。
(还有第三种可以想象的策略,那就是给予独立决定的类型的表示。语言实现将不得不安排一些全局注册表,以便没有两个值在内存中由相同的结构表示,无论涉及的类型如何;有效地跟踪哪些位模式在程序中的所有模块上全局地“已经分配”。但是即使你可以实现它,这个规则 * 本身 * 规定我们不能让Just x :: Maybe ax :: a表示相同,所以它仍然需要一个围绕x的 Package 器。
所以基本上Just构造函数将存在于运行时系统中。你必须对Haskell的工作方式做出相当大的改变,才能避免这种情况。即使定义Maybe的语言语法允许data Maybe a = Nothing | a,第二种情况仍然会有一个 Package 器构造函数,我们只是在表面语法中没有它的名字。

考虑到它必须在那里才能让语言以它的方式工作,它极大地简化了语言的语法,使数据构造函数总是有一个显式的名称,即使它只包含一个值。例如,在模式匹配中,编译器可以通过查看构造函数来判断程序员想要匹配什么。否则,如何在以下代码中区分哪个Nothing分支是哪个:

-- Your proposed syntax
case (mmx :: Maybe (Maybe Int)) of
  Nothing -> ...
  Nothing -> ...
  x -> ...

-- Standard Haskell sytax
case (mmx :: Maybe (Maybe Int)) of
  Nothing -> ...
  Just Nothing -> ...
  Just (Just x) -> ...

对于这个问题,我怎么知道最终的x分支应该与嵌套的maybe中可能包含的Int匹配?这是一个裸变量,所以它在任何级别都是有效的模式?如果我在没有明确的Maybe (Maybe Int)类型注解的情况下看到模式匹配,我怎么知道应该有多少个级别呢?x可以有效地匹配包含在Maybe (Maybe (Maybe (Maybe (Maybe Int))))中的Int(所有其他级别的Nothing都被作为失败的模式匹配而留下)。
如果没有显式构造函数的空值是Maybe的正常数据声明的有效选项,那么它必须是任何其他类型的。许多包定义了类似于data Result a = OK a | Error String的类型;为什么不把它们定义为data Result = a | String?现在,如果我传递一个值"hello"给一个需要Result a的函数,我会给它一个错误情况吗?或者当aString时,我是否给出了成功案例?或者当aMaybe (Identity (SomeOtherTypeWithABareStringCase))时,我是否给出了成功案例?它们看起来都一样。
或者更糟的是,为什么data Either a b = Left a | Right b不应该写成data Either a b = a | b?现在任何表达式都可以被解释为通过任意数量的Either嵌套的任何路径。任何人(或编译器)都不可能通过查看任何代码来了解任何代码的类型。
显然,没有人会设计允许我上面所有愚蠢示例的语言。要么对何时可以使用此功能有很多额外的限制,要么添加额外的语法标记来消除所有困难情况的歧义(或两者兼而有之)。
但是再次记住,构造函数仍然需要在运行时真正存在于系统中。所以这个不需要写Just的特性并没有给系统带来任何 * 能力 *。它节省了我们编写代码的几次按键。作为回报,我们要么必须 * 失去 * 能力(如果编译器限制我们避免可能产生不可能的模糊混乱的情况),要么我们必须到处写标记(这基本上相当于回到显式构造函数)。
我能看到的最接近的工作是,这只允许用于少数内置类型(而不是可以在用户定义类型中使用的语法),并为这些类型添加一些特殊规则以消除常见情况的歧义。基本上是“可空类型”思想的一个限制较少的版本,因此Maybe a仍然是一个“正常”的类型,足以允许用户定义类的示例,即使Maybe a不能由用户定义。
但我不想那样。Haskell的美丽和力量来自于简单而一致的构建块,这些构建块被设计为组合的。我不想用奇怪的特殊情况来保存一些按键。ADT是一组构造函数,每个构造函数都有一个字段列表。您可以通过编写构造函数名称来构建或模式匹配ADT的值。这个基本的语言特性已经覆盖了可空类型特性所获得的所有功能,所以我们根本不需要这样的特性。一个非常普通的ADT,叫做Maybe
(我确实想保存一些按键,因为Haskellers和其他语言的程序员一样懒惰!但我想通过一个可以在整个语言中通用的特性来实现,而不是只针对Maybe的特殊情况。如果你不能让这个“没有构造函数的裸值”作为ADT的一般特性工作,我根本不想要它。

oyt4ldly

oyt4ldly4#

我错过了什么?
x` | `y不是类型。
它只是data定义的简短语法的一部分。您可以在没有它的情况下用GADT语法写出完整的定义。

data Maybe a = Nothing | Just a
data Maybe (a0 :: Type) :: Type where
  Nothing :: forall (a1 :: Type). Maybe a1
  Just    :: forall (a2 :: Type). a2 -> Maybe a2

竖线是为了说明有效值的语法,比如BNF,以及它们的类型规则:

  • 对于任何a :: Type,如果n = Nothing,则n :: Maybe a
  • 对于任何a :: Type,如果j = Just xx :: a,则j :: Maybe a

类型系统对看起来很小的变化非常敏感。如果你用上面同样的方式解释data Maybe a = Nothing | a,它会说:

  • 对于任意a :: Type,如果x :: a,则x :: Maybe a

这将彻底改变其含义:

  • 每个类型t都是Maybe t的 * 子类型 *
  • |表示 * 未标记 * 联合(上限/连接)
  • Maybe (Maybe t) * 等价于Maybe t(并集是幂等的)
  • Maybe t表示“nullablet

相关问题