Руководство по правильному пути выполнения команд haskell

Question

Я новичок в Хаскеле. Моя Java знает, как просто не помогает мне много.

Мне нужна помощь или руководство по завершению кода. Я перепробовал большинство частей, а также указал комментарии о том, чего я стремлюсь достичь.

DFA был определен следующим образом ( исходное изображение определения DFA):

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,.}

задача:

1. Создайте программу на языке Haskell, которую можно использовать для выполнения любого произвольного детерминированного конечного автомата, соответствующего приведенному выше определению FDA. Представлять DFA как четыре кортежа

   а. представлять каждый штат с его именем в виде строки

   б. представляет все штаты в виде списка штатов

   с. представлять каждый переход как три кортежа, а список переходов - как список.

2. Чтобы помочь вам, реализуйте следующие функции в вашем решении:

   а. stateFactory - возвращает определение DFA (т.е. четыре кортежа)

   б. allStates, firstState, finalStates и allTransitions - взять DFA и вернуть соответствующий компонент DFA. Например, в приведенном выше экземпляре DFA allStates возвращает список состояний q₁, q₂, q₃, q₄ и q₅.

   с. transFrom, transInput и transTo - принять переход и вернуть соответствующий компонент перехода

   д. findTransition - принимает состояние, метку и список переходов и возвращает список, содержащий один переход, соответствующий данному состоянию и символу (обратите внимание, что переходы, исходящие из состояния, однозначно определяются каждой меткой символа

   е. findNextState - принимает DFA, метку и состояние и возвращает состояние

   е. dfaAccept - принимает DFA и входную строку и возвращает True, если DFA принимает входные данные, и False в противном случае (т.е. разбивает строку по одному символу за раз, не соответствует всей строке, поскольку ваше решение должно работать для любого 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

Это домашнее задание для класса, который вы посещаете, или это самостоятельное обучение на Haskell? Если это самостоятельное руководство, я думаю, вы можете попробовать упражнение, которое слишком сложно для вас на данном этапе. Я бы посоветовал взглянуть на этот ответ: Начало работы с Haskell. Несмотря на то, что это старый ответ, он время от времени обновлялся, и большая часть ресурсов по-прежнему полезна. На веб- сайте http://www.haskell.org/ также есть ссылки на множество ресурсов для изучения Haskell в разделе "Документация".

Если это домашнее задание для класса, который вы посещаете, у вас могут быть проблемы. Вы делаете довольно простые ошибки в своем коде (используя elem где вам нужно `elem`; пытаясь применить last до четырех аргументов; используя заглавный идентификатор DFA как имя переменной), который показывает, что у вас еще нет базовых принципов Haskell.

Возможно, вам следует поговорить со своим профессором и сообщить ему или ей, что это задание за вами. Может быть, вы можете получить расширение, или, может быть, вы можете предложить использовать Java-решение для частичного зачисления (при условии, что этот курс специально не является курсом на Haskell).

Если вы настаиваете на продвижении вперед, вот подсказка. Вы просите о помощи в написании одной из самых сложных функций, findTransition, но вы даже не написали "простые", как allStates, firstState, и так далее. (Вы использовали те же имена в своем решении, но вы определили их как константы для определенного DFA вместо того, чтобы делать их функциями, примененными к общему кортежу DFA, что и требуется для назначения).

Итак, можете ли вы заполнить следующий шаблон, заполнив подчеркивания, чтобы ответить на части 1 и 2(б)?

-- 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(с). После того как вы сделали все это, вы можете быть готовы к решению findTransition, На этом этапе вам, вероятно, нужно узнать о find или же filter функции, иначе вам нужно научиться писать функции рекурсивного списка.