完成 haskell 命令的正确路径指南

Question

我完全是 haskell 的新手。我的 java 知道怎么对我帮助不大。

我需要有关完成代码的任何帮助或指导。我已经尝试了大部分部分，并且还对我倾向于实现的目标进行了评论。

一个DFA定义如下 (original image of DFA definition):

Q = {q1,q2,q3,q4,q5}
qs = q1
F = {q4}
delta = {
  <q1,0,q2>,<q1,1,q2>,<q1,.,q3>,
  <q2,0,q2>,<q2,1,q2>,<q2,.,q4>,
  <q3,0,q4>,<q3,1,q4>,<q3,.,q5>,
  <q4,0,q4>,<q4,1,q4>,<q4,.,q5>,
  <q5,0,q5>,<q5,1,q5>,<q5,.,q5>
  }
Sigma = {0,1,.}

任务：

创建一个Haskell语言程序，可以用来执行任意与上述 FDA 定义相对应的确定性有限自动机。代表作为四元组的 DFA

一个。将每个州的名称表示为字符串

b。将所有状态表示为状态列表

c。将每个转换表示为三元组，将转换列表表示为列表.
为帮助您，请在您的解决方案中实现以下功能：

一个。 stateFactory – returns 一个 DFA 定义（即四元组）

b。 allStates、firstState、finalStates 和 allTransitions – 采用 DFA 和 return DFA 的相应组件。例如，在上面的 DFA 实例中， allStates 将 return 状态列表，q₁、q₂、q₃、q₄ 和 q₅。

c。 transFrom、transInput 和 transTo – 进行转换，return 转换的相应组件

d. findTransition – 获取一个状态、一个标签和一个转换列表以及 returns 一个列表包含与给定状态和字符匹配的单个转换（注意从状态发出的转换由每个字符标签唯一确定

e。 findNextState——接受一个 DFA、一个标签和一个状态，returns 一个状态

f。 dfaAccept – 采用 DFA 和输入字符串，如果 DFA 接受输入则 returns 为真，否则为假（即一次分解字符串一个字符，不要匹配整个字符串，因为您的解决方案必须适用于任何 DFA）。这有助于将其分成两个函数，每个函数具有不同的参数集（一个用于空列表和一个非空列表）。一个函数接受一个当前状态，一个简单地接受一个 DFA，其状态被假定为 DFA 的初始状态。

这是我的代码，有很多错误，但正在尝试修复它们

allStates = ["q1","q2","q3","q4","q5"] -- iniitialize all states
firstState = "q1"
finalStates = "q4"

--define all transitions as a tuple

t1 = ("q1",'0',"q2")
t2 = ("q1",'1',"q2")
t3 = ("q1",'.',"q3")

-- place all transitions in a list
allTransitions = [t1,t2,t3]

lst =[]

stateFactory = (allStates, firstState, finalStates, allTransitions)

findTransition state label listOfTransition = 
    if (state , label , "q1") elem listOfTransition
        then lst ++ [] -- if the tuple matches the one in transition add to list
    else
        lst -- no match dont add

    if (state , label , "q2") elem listOfTransition
        then lst ++ [] -- if the tuple matches the one in transition add to list
    else
        lst -- no match dont add

    if (state , label , "q3") elem listOfTransition
        then lst ++ [] -- if the tuple matches the one in transition add to list
    else
        lst -- no match dont add

findNextState DFA label state = 
    --get the transition and extract the last element which is the state
    last findTransition state label allTransitions

dfaAccept DFA inputString = 
    if inputString == null then False

预期输出

Prelude> dfaAccept stateFactory “”
False
Prelude> dfaAccept stateFactory “1”
False
Prelude> dfaAccept stateFactory “1.0”
True
Prelude> dfaAccept stateFactory “11.11”
True
Prelude> dfaAccept stateFactory “10.10.10”
False

Answer 1

这是您正在学习的 class 作业，还是 self-guided Haskell 学习？如果这是 self-guided，我想你可能正在尝试一个在这个阶段对你来说太难的练习。我建议看看这个答案：Getting started with Haskell. Even though it's an old answer, it's been updated now and again, and most of the resources there are still useful. The http://www.haskell.org 网站在 "Documentation" 部分也有很多学习资源的链接 Haskell。

如果这是你正在学习的 class 的家庭作业，你可能有麻烦了。您在代码中犯了一些非常基本的错误（在需要 `elem` 的地方使用 elem；尝试将 last 应用于四个参数；使用大写标识符 DFA 作为变量名称），这表明您还没有确定 Haskell 基础知识。

也许你应该和你的教授谈谈，让他或她知道这项作业超出了你的能力范围。也许你可以获得延期，或者你可以提供 Java 解决方案以获得部分学分（假设这门课程不是专门的 Haskell 课程）。

如果你坚持进取，这里有一个提示。您正在寻求帮助来编写最难的函数之一 findTransition，但您甚至还没有编写 "easy" 函数，例如 allStates、firstState 等等. （您在解决方案中使用了相同的名称，但您已将它们定义为特定 DFA 的常量，而不是将它们的函数应用于一般 DFA 元组，这是赋值所要求的）。

那么，您能否通过填写下划线来完成以下模板，以回答第 1 部分和第 2(b) 部分？

-- simple type synonyms to make things easier to read
type State = String
type Symbol = Char

-- some more complicated type synonyms
type Transition = (State, Symbol, State)
type DFA = ( [State]        -- all states
           , State          -- first state
           , [State]        -- final states
           , [Transition]   -- all transitions
           )

allStates :: DFA -> [State]
allStates _ = _

firstState :: DFA -> State
firstState _ = _

finalStates :: DFA -> [State]
finalStates _ = _

allTransitions :: DFA -> [Transition]
allTransitions _ = _

一旦您能够做到这一点，请编写第 2(c) 部分中的函数。完成所有之后，您可能就可以开始 findTransition 了。此时，您可能需要了解 find 或 filter 函数，否则您将需要学习如何编写递归列表函数。

完成 haskell 命令的正确路径指南

A guide to the right path on accomplishing the haskell commands

haskell

dfa

declarative