时间戳

首页 > 解决方案 > 阐明 Haskell 中的数据构造函数

haskell - 阐明 Haskell 中的数据构造函数

问题描述

在下面的：

data DataType a = Data a | Datum

我知道数据构造函数是价值级别的函数。我们上面所做的是定义它们的类型。它们可以是多个 arity 或 const 的函数。没关系。我可以说Datum构造Datum。这里对我来说不是那么明确和清楚的是构造函数和它产生的东西之间的区别。如果我做得好，请告诉我：

1-a）基本上写作Data a，是定义数据结构和它的构造函数（如在scala或java中通常类和构造函数具有相同的名称）？

2 - b）所以如果我打开包装并做一个类比。我们Data a都在定义对象（数据结构）、构造函数（数据构造函数/值构造函数）和后者返回该对象结构的对象。最后，对象结构的类型由 Type 构造函数给出。从某种意义上说，对象结构只是围绕某种类型的一堆值的标签。我的理解正确吗？

3 - c) 我可以正式地说：

标签： haskell

解决方案

另一种写法：

data DataType a = Data a | Datum

使用广义代数数据类型 (GADT) 语法，使用GADTSyntax扩展，它允许我们明确指定构造函数的类型：

{-# LANGUAGE GADTSyntax #-}

data DataType a where
  Data  :: a -> DataType a
  Datum ::      DataType a

（GADTs扩展也可以工作；它还允许我们在结果中指定具有不同类型参数的构造函数，例如DataType Intvs. DataType Bool，但这是一个更高级的主题，我们在这里不需要该功能。）

:type如果您使用/询问构造函数的类型，这些正是您在 GHCi 中看到的类型:t：

> :{
| data DataType a where
|   Data  :: a -> DataType a
|   Datum ::      DataType a
| :}

> :type Data
Data :: a -> DataType a

> :t Datum
Datum :: DataType a

我们还可以显式指定类型变量的范围，并通过给它们不同的名称ExplicitForAll来更清楚地表明定义a中的是与构造函数定义中data的独立变量：a

data DataType a where
  Data  :: forall b. b -> DataType b
  Datum :: forall c.      DataType c

使用标准前奏类型的这种表示法的更多示例：

data Either a b where
  Left  :: forall a b. a -> Either a b
  Right :: forall a b. b -> Either a b

data Maybe a where
  Nothing :: Maybe a
  Just    :: a -> Maybe a

data Bool where
  False :: Bool
  True  :: Bool

data Ordering where
  LT, EQ, GT :: Ordering  -- Shorthand for repeated ‘:: Ordering’

我知道数据构造函数是价值级别的函数。我们上面所做的是定义它们的类型。它们可以是多个 arity 或 const 的函数。没关系。我可以说 Datum 构造 Datum。这里对我来说不是那么明确和清楚的是构造函数和它产生的东西之间的区别。

Datum并且Data都是DataType a价值观的“构造者”；既不是Datum也不Data是类型！这些只是在DataType a值的可能种类之间进行选择的“标签”。

产生的总是一个DataType a给定类型的值a；构造函数选择它采用的“形状”。

一个粗略的类似物是union在 C 或 C++ 等语言中，加上“标签”的枚举。在伪代码中：

enum Tag {
  DataTag,
  DatumTag,
}

// A single anonymous field.
struct DataFields<A> {
  A field1;  
}

// No fields.
struct DatumFields<A> {};

// A union of the possible field types.
union Fields<A> {
  DataFields<A>  data;
  DatumFields<A> datum;
}

// A pair of a tag with the fields for that tag.
struct DataType<A> {
  Tag       tag;
  Fields<A> fields;
}

然后，构造函数只是返回具有适当标记和字段的值的函数。伪代码：

<A> DataType<A> newData(A x) {
  DataType<A> result;
  result.tag = DataTag;
  result.fields.data.field1 = x;
  return result;
}

<A> DataType<A> newDatum() {
  DataType<A> result;
  result.tag = DatumTag;
  // No fields.
  return result;
}

联合是不安全的，因为标签和字段可能不同步，但求和类型是安全的，因为它们将它们耦合在一起。

Haskell 中这样的模式匹配：

case someDT of
  Datum  -> f
  Data x -> g x

是测试标签和提取字段的组合。同样，在伪代码中：

if (someDT.tag == DatumTag) {
  f();
} else if (someDT.tag == DataTag) {
  var x = someDT.fields.data.field1;
  g(x);
}

同样，这在 Haskell 中是耦合的，以确保只有通过模式匹配检查了标签才能访问字段。

因此，在回答您的问题时：

1 - a）基本上写数据a，定义数据结构和它的构造函数（如在scala或java中通常类和构造函数具有相同的名称）？

Data a在您的原始代码中没有定义数据结构，因为Data它不是一个单独的类型DataType a，它只是一个值可能具有的可能标签之一。DataType a在内部，类型的值DataType Int是以下之一：

  • Data（在 GHC 中，指向构造函数的“信息表”的指针）的标记，以及对类型值的引用Int。

    x = Data (1 :: Int) :: DataType Int

       +----------+----------------+     +---------+----------------+
x ---->| Data tag | pointer to Int |---->| Int tag | unboxed Int# 1 |
       +----------+----------------+     +---------+----------------+

  • 的标签Datum，没有其他字段。

    y = Datum :: DataType Int

        +-----------+
y ----> | Datum tag |
        +-----------+

在具有unions 的语言中，联合的大小是其所有备选方案中的最大值，因为该类型必须支持表示任何具有突变的备选方案。在 Haskell 中，由于值是不可变的，因此它们不需要任何额外的“填充”，因为它们无法更改。

对于标准数据类型，例如 product 或 sum 类型，情况类似：

(x :: X, y :: Y) :: (X, Y)
  +---------+--------------+--------------+
  | (,) tag | pointer to X | pointer to Y |
  +---------+--------------+--------------+

Left (m :: M) :: Either M N
  +-----------+--------------+
  | Left tag  | pointer to M |
  +-----------+--------------+

Right (n :: N) :: Either M N
  +-----------+--------------+
  | Right tag | pointer to N |
  +-----------+--------------+

2 - b）所以如果我打开包装并做一个类比。使用数据 a 我们都在定义对象（数据结构）、构造函数（数据构造函数/值构造函数）和后者返回该对象结构的对象。最后，对象结构的类型由 Type 构造函数给出。从某种意义上说，对象结构只是围绕某种类型的一堆值的标签。我的理解正确吗？

这是正确的，但同样，构造函数本身Data并不是Datum“数据结构”。它们只是用于引入（构造）和消除（匹配）类型值的名称DataType a，对于构造函数的调用者选择的某些类型a来填充forall

data DataType a = Data a | Datum说：

  • 如果某个术语e具有类型T，则该术语Data e具有类型DataType T

  • 相反，如果某个类型的值DataType T与模式匹配Data x，则x类型T在匹配范围内（case分支或函数方程）

  • 该术语Datum具有DataType T任何类型的类型T

3 - c) 我可以正式地说：

Nullary 的数据构造函数表示常量值 -> 返回常量值本身，其类型由定义站点的类型构造函数给出。

接受参数的数据构造函数表示值的类，其中类是标签？-> 返回该类的无限数量的对象，其类型由定义站点的 Type 构造函数给出。

不完全是。像, , or , or (list)这样的类型构造函数，或多态数据类型，表示具体类型 ( , , , ...) 的“无限”族，但与表示“无限”函数族的方式相同（, , , ...)。DataType :: Type -> TypeMaybe :: Type -> TypeEither :: Type -> Type -> Type[] :: Type -> TypeMaybe IntMaybe CharMaybe (String -> String)id :: forall a. a -> aid :: Int -> Intid :: Char -> Charid :: String -> String

也就是a这里的类型是一个参数，里面填入了调用者给的参数值。通常这是通过类型推断隐含的，但您可以使用TypeApplications扩展名显式指定它：

-- Akin to: \ (a :: Type) -> \ (x :: a) -> x
id        :: forall a. a   -> a
id x = x

id @Int   ::           Int -> Int
id @Int 1 ::                  Int

Data           :: forall a. a    -> DataType a
Data @Char     ::           Char -> DataType Char
Data @Char 'x' ::                   DataType Char

每个实例化的数据构造函数彼此之间没有任何关系。除了它们共享相同的标签名称这一事实之外，实例化Data :: Int -> DataType Int和之间没有任何共同之处。Data :: Char -> DataType Char

用 Java 术语来思考这个问题的另一种方法是使用访问者模式。DataType将表示为接受“<code>DataType visitor”的函数，然后构造函数不对应单独的数据类型，它们只是接受字段并返回一些结果的访问者的方法。用 Java 编写等价的代码是一个值得练习的练习，但这里是在 Haskell 中：

{-# LANGUAGE RankNTypes #-}
-- (Allows passing polymorphic functions as arguments.)

type DataType a
  = forall r.    -- A visitor with a generic result type
  r              -- With one “method” for the ‘Datum’ case (no fields)
  -> (a -> r)    -- And one for the ‘Data’ case (one field)
  -> r           -- Returning the result

newData :: a -> DataType a
newData field = \ _visitDatum visitData -> visitData field

newDatum :: DataType a
newDatum = \ visitDatum _visitData -> visitDatum

模式匹配只是运行访问者：

matchDT :: DataType a -> b -> (a -> b) -> b
matchDT dt visitDatum visitData = dt visitDatum visitData
-- Or: matchDT dt = dt
-- Or: matchDT = id

-- case someDT of { Datum -> f; Data x -> g x }
-- f :: r
-- g :: a -> r
-- someDT :: DataType a
--        :: forall r. r -> (a -> r) -> r

someDT f (\ x -> g x)

同样，在 Haskell 中，数据构造函数只是引入和消除用户定义类型的值的方法。

推荐阅读