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 章的第一部分),一个很好的地方就是代数数据类型介绍类型变量类型参数

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

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

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

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

在 haskell 中,我们有三种方法来定义新类型,使用三个不同的关键字typenewtypedata

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

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。这就是我们所说的高阶函数

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

现在,您自己推断应该足以回答您的问题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 回答