5

我应该写一些haskell程序，但我真的不知道从哪里开始。如果您能指出一些资源来阅读或解释我的问题，我将非常感激。我确信这完全是业余的，但我真的需要一个起点。

data DFA q o                =  DFA (q -> o -> q) q [q]
data NFA q o                =  NFA (q -> o -> [q]) [q] [q]
-- I really realy don't understand the declarations here
-- I can guess that q is somewhat related to Q and o to E, but don't get what it really means

data Q                      =  Q0 | Q1 | Q2
                               deriving (Eq, Enum, Bounded)

data E                      =  A | B


-- what does n1 do ??
n1                          :: NFA Q E
n1                          =  NFA d [Q0] [Q2] -- i see [Q0] refers to set of initial states and [Q2] refers to final states :)
                               where
                                   d Q0 A = [Q0]
                                   d Q0 B = [Q0, Q1]
                                   d Q1 _ = [Q2]
                                   d Q2 _ = []


-- the following functions are for me to write
starDFA :: Eq q => DFA q o -> [o] -> Bool
--for the above function, what are the arguments the function takes in ?
--how can we relate q with Q and [o] with [E] ??

任何对正确起点的解释或参考都会对我很有帮助。抱歉问了这么愚蠢的问题，但我真的不知道从哪里开始:)

谢谢

4

3 回答 3

17

向您学习 Haskell for Great Good！可能是目前最好的 Haskell 教程。我建议通读整篇文章，但如果你赶时间，我会指出一些与本作业更相关的部分。

给出的代码的主要部分是data声明，所以一旦你熟悉了基础知识（第 2章和第 3 章的第一部分），一个很好的地方就是代数数据类型介绍、类型变量和类型参数。

以上应该足以破译数据声明并理解qvsQ和ovs之间的关系E。

现在要实现实际功能，您需要熟悉确定性有限自动机的工作原理，然后了解足够的 Haskell 来编写实际实现。第 4章和第 5章是本教程中与此最相关的章节，您可能还会发现有关标准库列表函数的部分很有用。

一旦你到达这一点，如果你被实现所困，你可以用你迄今为止编写的代码发布另一个问题。

于 2013-02-20T12:13:01.333 回答
6

在 haskell 中，我们有三种方法来定义新类型，使用三个不同的关键字type、newtype和data。

在您的示例中，它是正在使用的数据关键字，让我们更加关注它。
最好从您的代码中最简单的开始 

data E = A | B

在这里，我们定义了一个新类型 E，它只能采用两种模式或状态或值。
像这样的类型就是我们所说的sum 类型。我们如何使用它？
主要是模式匹配。 

useE :: E -> String
useE A = "This is A"
useE B = "This is B"

现在，来自您的代码的更复杂的数据声明。 

data Q =  Q0 | Q1 | Q2 deriving (Eq, Enum, Bounded)

同样，如前所述，我们有一个sum 类型，它定义了一个新类型 Q，取三个值，Q0、Q1 或 Q2。但是我们有一个派生子句，它告诉编译器这个新类型实现了从Eq, Enum, Bounded class派生（或继承）的方法（或函数） 。那是什么意思 ？
我们来看一个函数。
想象一下，您想为 Q 的每个值关联一个数字，我们该如何执行呢？ 

enumQ :: Q -> Int
enumQ x = fromEnum x

如果您想更深入地了解deriving子句提供的此特定功能，请阅读已指示的资源并尝试ghci 下的:info Enum 。请注意，以前的类型也可以派生自同一个类。由于这些类型被完全描述为一组可枚举值的总和（由|区分），我们更好地理解了为什么我们称它们为sum 类型。

最后是最困难的数据声明。 

data DFA q o =  DFA (q -> o -> q) q [q]
data NFA q o =  NFA (q -> o -> [q]) [q] [q]

如果事实上它们几乎是相同的数据定义，那么我将介绍第一个，并让您分析第二个作为练习。 

data DFA q o = DFA (q -> o -> q) q [q]

这一次我们必须谈谈数据构造函数和类型构造函数。

  • 在等式的左侧，有数据构造函数，用于构建数据并为其命名。在这一方面，我们有用于构建这些新数据的必需参数。
  • 在等式的右侧，有类型构造函数，用于构建这个新类型。在这一方面，我们有明确的管道，它向读者展示了如何使用现有类型构建这种新类型（数据）。

现在请记住，以下是类型，

  • [x] ::: 表示多态列表的类型，Example, [Int] => List of Int
  • x ::: 一种基本类型，现有类型之一（Int、Char、String ...）
  • x -> y ::: 定义函数的类型，采用类型 x 产生类型 y。
  • x -> y -> z ::: 定义函数的类型采用类型 x 和类型 y 来产生类型 z。可以将其视为一个函数，该函数采用另一个类型为 (x->y) 的函数并产生一个类型 z。这就是我们所说的高阶函数。

然后我们的数据声明，放在这个上下文中，是一个数据构造函数，由两个类型参数q和o提供，结果，它返回一个新类型作为高阶函数的乘积，一个基本类型和一个列表类型. 这就解释了为什么我们称之为产品类型。

现在，您自己推断应该足以回答您的问题n1 是什么？

祝你好运。

于 2013-02-20T16:44:36.357 回答
3

根据我对 Haskell 类型声明的了解，关于 DFA 和 NFA 的初始陈述是这样说的（例如，看 NFA）：（

左手边：） NFA 是一种使用两种类型（q 和 o）的类型它的建设。

（右手边：） NFA 的一个实例将被称为 NFA，由三个参数组成：
(1) "(q -> o -> [q])" ，意思是一个接受两个参数的函数，一个是类型q 和 o 类型之一，并返回 q 的列表 ([q])
(2) "[q]" ，表示一个 q
(3) "[q]" 类型的值列表，另一个值的列表类型 q

n1 似乎是 NFA 的实例构造，我们看到

n1                          =  NFA d [Q0] [Q2]

所以我们可以推断：
(1) d 是一个函数，它接受两个参数，一个 'q' 和一个 'o' 并返回一个 q 的列表
(2) [Q0] 是一个 q 的列表，并且
(3) [ Q2] 是 q 的列表。

实际上，d 的定义如下：
d 接受两个参数，一个“Q”和一个“E”，并返回一个 Q 列表（我们知道它可以是 Q0、Q1 或 Q2）或一个空列表。

我希望这会有所帮助和/或也许有人可以澄清和纠正我的模糊理解。

于 2013-02-20T13:31:56.853 回答