Pytania startowe Haskell ... proszę mi to wytłumaczyć

Question

Mam napisać program haskell, ale tak naprawdę nie wiem od czego zacząć. Będę naprawdę wdzięczny, jeśli możesz wskazać mi jakieś zasoby, aby przeczytać lub wyjaśnić mi to pytanie. Jestem pewien, że jest to coś całkowicie amatorskiego, ale naprawdę potrzebuję punktu wyjścia.

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

Wszelkie wyjaśnienia lub odniesienia do właściwych punktów początkowych będą dla mnie bardzo pomocne. Niestety zadać takie głupie pytanie, ale ja naprawdę nie wiem od czego zacząć :)

Dzięki

Answer 1

Learn You a Haskell for Great Good! to prawdopodobnie najlepszy poradnik Haskell w tej chwili. Polecam lekturę całej sprawy, ale jeśli się spieszysz, wskażę niektóre z bardziej odpowiednich sekcji tego zadania.

Główną rolę w kodzie są podane są deklaracje data, więc gdy jesteś zaznajomiony z podstawami (chapter 2 i first section of chapter 3), dobre miejsce do nurkowania w to Algebraic data types intro, Type variables i Type parameters.

Powyższy powinien być wystarczający dla rozszyfrowania zgłoszenia danych i zrozumieniu wzajemnych zależności między q vs Q i o vs E.

Teraz, aby zaimplementować rzeczywistą funkcję, musisz znać sposób działania deterministic finite automata, a następnie znać wystarczająco Haskell, aby napisać rzeczywistą implementację. Chapter 4 i chapter 5 są najistotniejsze rozdziały do ​​tego w samouczku i może Ci się także przydać przydatna section on standard library list functions.

Gdy dojdziesz do tego punktu, jeśli utkniesz przy implementacji, możesz napisać kolejne pytanie z kodem, który napisałeś do tej pory.

Answer 2

Z trochę rozumiem o deklaracjach typu Haskell, wstępne oświadczenia o DFA i NFA mówią coś jak (patrząc na NFA, na przykład):

(Left hand side :) NFA jest typem, który wykorzystuje dwa typy (q i o) w swojej konstrukcji.
(Prawa strona :) instancja NFA będzie się nazywać NFA i będzie składać się z trzech parametrów:
(1) "(q -> o -> [q])", co oznacza funkcję, która wymaga dwóch parametry, jeden z typu q i jeden z typu o, i zwraca listę q, ([q])
(2) "[q]", co oznacza jedną listę wartości typu q
(3) "[ q]”, kolejna lista wartości typu q

n1 wygląda na budowie instancji NFA i widzimy

n1       = NFA d [Q0] [Q2] 

Możemy więc wywnioskować, że: (1) d jest funkcją, która przyjmuje dwa parametry, "q" i "o" i zwraca listę q's
(2) [Q0] to lista q's i
(3) [Q2] to lista q.

I rzeczywiście, definicja d następuje:
d przyjmuje dwa parametry, "Q" i "E" i zwraca listę Q (która jak wiemy może być albo Q0, Q1, albo Q2) lub pustą listę.

Mam nadzieję, że pomogło to trochę i/lub być może ktoś mógł wyjaśnić i poprawić moje niejasne zrozumienie.

Answer 3

w Haskell mamy trzy drogi do zdefiniowania nowego typu, stosując trzy różne słowa kluczowe, typu, newtype i dane.

W twoim przykładzie jest to słowo kluczowe data, skupmy się nieco na nim.
Lepiej zacząć od najprostszych jeden pochodzący z kodem

data E = A | B 

Tutaj mamy zdefiniować nowy typ E, która może przyjmować tylko dwie tryb lub państwowej lub wartość.
Typ taki jak ten nazywamy typem sumy . Jak możemy go użyć?
Głównie z pasującym wzorcem .

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

Teraz bardziej złożona deklaracja danych z kodu.

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

Ponownie jak już wspomniano wcześniej, że mają typu suma które określają nowego typu Q, przyjmowane trzy wartości, Q0, Q1 lub Q2. Ale mamy klauzulę wywodzącą , która mówi kompilatorowi, że ten nowy typ implementuje metodę (lub funkcję) wyprowadzającą (lub odziedziczoną) z Eq, Enum, Bounded class. Co to znaczy?
Spójrzmy na funkcję.
Wyobraź sobie, że chcesz powiązać liczbę dla każdej wartości Q, w jaki sposób możemy to wykonać?

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

Jeśli chcesz więcej wgląd o tej konkretnej funkcjonalności dostarczenie przez wynikających klauzulę, przeczytaj zasobów, które zostały wskazane i spróbuj : info Enum pod ghci. Zauważ, że poprzedni typ mógł również pochodzić z tej samej klasy. Ponieważ te typy są w pełni opisane jako suma przeliczalnego zestawu wartości (dyskryminowanego przez |), lepiej rozumiemy, dlaczego nazywamy je sumą typu sumą typu.

Wreszcie najtrudniejsza deklaracja danych.

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

Jeśli fakt, że są prawie takie same dane definicja wtedy pójdę koryta pierwszy i niech ci analiz drugi jako ćwiczenie.

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

Tym razem musimy mówić o konstruktora danych i typ konstruktora.

• Z lewej strony równości istnieje konstruktor dane, do budowanych danych i nadać mu nazwę. Po tej stronie mamy wymagany parametr użyty do zbudowania tych nowych danych.
• Po prawej stronie równości znajduje się konstruktor typu, do , który zbudował ten nowy typ. Po tej stronie mamy wyraźne hydraulikowanie , które pokazuje czytelnikowi, jak ten nowy typ (dane) jest zbudowany przy użyciu istniejącego typu.

Teraz mając na uwadze, że po to typ,

• [x] ::: Rodzaj reprezentujący polimorficzny listy, przykład [Int] => Lista Int
• x ::: podstawowy typ, jeden z istniejącą (int, char, string ...)
• x -> y ::: Rodzaj które definiują funkcję zrobieniu typu x do prod ui a typ: y.
• x -> y -> z ::: Typ definiujący funkcję typu x i y, aby utworzyć typ z. Który może być widokiem jako funkcją przyjmującą inną funkcję typu (x-> y) i tworzącą typ z. To nazywamy funkcją wysokiego rzędu .

Następnie nasze zgłoszenie danych znajdująca się w tym kontekście to konstruktor danych, paszy przez dwa parametru typu, q i O i w rezultacie powrót nowy typ jako iloczyn funkcja wyższego rzędu to typ podstawowy i typ listy. Co tłumaczy, dlaczego nazywamy to produktem typu :.

Powinno wystarczyć, teraz, wnioskowanie przez siebie, aby odpowiedzieć na pytanie: co robi n1?

Powodzenia.