Haskell Starter Fragen ... bitte erklären Sie es mir

Question

Ich soll ein Haskell Programm schreiben, aber ich weiß nicht wirklich wo ich anfangen soll. Ich werde wirklich sehr dankbar sein, wenn Sie mich auf einige Ressourcen verweisen können, um mir die Frage zu lesen oder zu erklären. Ich bin mir sicher, dass das etwas total Amateurhaftes ist, aber ich brauche wirklich einen Ausgangspunkt.

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] ?? 

Alle Erklärungen oder Verweise auf die richtigen Startpunkte werden mir sehr hilfreich sein. Leider solch eine dumme Frage zu stellen, aber ich weiß wirklich nicht, wo ich anfangen sollen :)

Dank

Answer 1

Learn You a Haskell for Great Good! wahrscheinlich das beste Haskell Tutorial im Moment ist. Ich empfehle Ihnen, das Ganze durchzulesen, aber wenn Sie es eilig haben, werde ich auf einige der relevanteren Abschnitte für diese Aufgabe hinweisen.

Der Hauptteil in dem Code, den Sie gegeben werden, sind die data Erklärungen, so, wenn Sie mit den Grundlagen vertraut sind (chapter 2 und die first section of chapter 3), ein guter Platz in den Algebraic data types intro, Type variables und Type parameters ist zu tauchen.

Die oben sollte für die Entschlüsselung der Datendeklarationen und das Verständnis der Beziehung zwischen q vs Q und o vs E genug sein.

Nun, um die eigentliche Funktion zu implementieren, müssen Sie vertraut sein, wie deterministic finite automata arbeiten und dann genug Haskell, um die tatsächliche Implementierung zu schreiben. Chapter 4 und chapter 5 sind die relevantesten Kapitel dafür in der Anleitung und Sie könnten auch die section on standard library list functions nützlich finden.

Sobald Sie an diesem Punkt angekommen sind, können Sie, wenn Sie mit der Implementierung fertig sind, eine weitere Frage mit dem Code schreiben, den Sie bisher geschrieben haben.

Answer 2

Vom wenig ich über Haskell Typen Erklärungen verstehen, die ersten Aussagen über DFA und NFA sagen so etwas wie (mit Blick auf NFA, zum Beispiel):

(linke Seite :) NFA ist ein Typ, der zwei nutzt Typen (q und o) in seiner Konstruktion.

(rechte Seite :) eine Instanz von NFA heißt NFA und besteht aus drei Parametern:
(1) "(q -> o -> [q])", was eine Funktion bedeutet, die zwei übernimmt Parameter, einer vom Typ q und einer vom Typ o, und gibt eine Liste von qs zurück, ([q]) (2) "[q]", dh eine Liste von Werten vom Typ q
(3) q]“, eine andere Liste von Werten vom Typ q

n1 wie ein Beispiel Bau von NFA scheint, und wir sehen

n1       = NFA d [Q0] [Q2] 

So können wir folgern:
(1) d ist eine Funktion, die zwei Parameter, a 'q' und ein 'o' und gibt eine Liste von Q nimmt
(2) [Q0] ist eine Liste der qs und
(3) [Q2] ist eine Liste von qs.

Und in der Tat, die Definition von d folgt:
d zwei Parameter nimmt, ein ‚Q‘ und ein ‚E‘ und gibt eine Liste von Q (was wir wissen können entweder Q0, Q1 oder Q2) oder eine leere Liste.

Ich hoffe das hilft ein wenig und/oder vielleicht könnte jemand mein vages Verständnis auch klären und korrigieren.

Answer 3

in Haskell haben wir drei Art und Weise neue Art zu definieren, indem drei verschiedene Schlüsselwörter, Typ, newtype und Daten.

In Ihrem Beispiel ist es Daten Stichwort, das verwendet wird, konzentrieren wir uns ein bisschen mehr darauf.
Es ist besser, mit der einfachste kommt aus dem Code

data E = A | B 

Hier zu beginnen, haben wir einen neuen Typ E definieren, die nur zwei Modus oder Zustand oder Wert annehmen kann.
Ein Typ wie diesen nennen wir Sum Typ. Wie können wir ein es verwenden?
Meistens mit Muster passend.

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

Jetzt eine komplexere Datendeklaration aus Ihrem Code.

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

Wiederum, wie zuvor gesagt, haben wir ein sum Typ, die einen neuen Typ Q definieren, aufgenommen mit drei Werten, Q0, Q1 oder Q2. Aber wir haben eine Ableitungsklausel, die dem Compiler sagen, dass dieser neue Typ die Methode (oder Funktion) implementiert, die von Eq, Enum, Bounded Klasse abgeleitet (oder geerbt) wird. Was bedeutet das?
Werfen wir einen Blick auf eine Funktion.
Stellen Sie sich vor, Sie möchten jedem Wert von Q eine Zahl zuordnen, wie können wir das ausführen?

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

Wenn Sie mehr Einblick über diese besondere Funktionalität von bieten Ableiten Klausel, lesen Sie die Ressourcen, die angegeben wurden, und versuchen : info Enum unter GHCI. Beachten Sie, dass der vorherige Typ auch von derselben Klasse abgeleitet werden kann. Da diese Typen vollständig als die Summe eines aufzählbaren Wertes beschrieben werden (diskriminiert durch |), verstehen wir besser, warum wir sie Sum-Typ nennen.

Endlich die schwierigste Datendeklaration.

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

Wenn Tatsache, dass sie fast die gleiche Datendefinition ist, dann werde ich gehen, um die ersten Trog und Ihnen die Analysen des zweiten als Übung lassen.

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

Dieses Mal müssen wir über Daten Konstruktor und Typkonstruktor sprechen.

• Auf der linken Seite der Gleichung gibt es Daten Konstruktor, gebaut Daten und ihm einen Namen geben. Auf dieser Seite haben wir den erforderlichen Parameter, um diese neuen Daten zu erstellen.
• Auf der rechten Seite der Gleichheit, gibt es Typ Konstruktor, um diesen neuen Typ gebaut. Auf dieser Seite haben wir die explizite Klempner, die dem Leser zeigen, wie dieser neue Typ (Daten) mit dem vorhandenen Typ gebaut wird.

Jetzt im Auge behalten, dass die folgende Art sind,

• [x] ::: Typ der polymorphen Liste darstellt, Beispiel, [Int] => Liste der Int
• x ::: ein Grundtyp, einer der bestehenden (Int, Char, String ...)
• x -> y ::: Art, die eine Funktion eines Typs x entnommen definieren prod uce a Typ y.
• x -> y -> z ::: Geben Sie einen Typ x und einen Typ y ein, um einen Typ z zu erzeugen. Das kann als eine Funktion betrachtet werden, die eine andere Funktion vom Typ (x-> y) nimmt und einen Typ z erzeugt. Dies nennen wir eine High-Order-Funktion.

Dann sind unsere Datendeklaration in diesem Zusammenhang stellen, ein Daten Konstruktor ist, Futtermittel durch zwei Typparameter, q und o und als Ergebnis ist es, einen neuen Typ als das Produkt zurückgeben Eine höherwertige Funktion ist ein Basistyp und ein Listentyp. Was erklären, warum wir dies eine Produktart nennen.

Es sollte genug sein, jetzt, abschließend selbst, um Ihre Frage zu beantworten, was macht n1?

Viel Glück.