Haskell starter questions... please explain it to me

Question

I am supposed to write some haskell program but I don't really know where to start. I will be really really grateful if you can point me to some resources to read or explain me the question. I am sure this is something totally amateurish, but I really need a starting point.

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

Any explanations or references to proper starting points will be really helpful to me. Sorry to ask such a dumb question, but I really don't know where to start :)

Thanks

Answer 1

Learn You a Haskell for Great Good! is probably the best Haskell tutorial at the moment. I recommend reading through the whole thing, but if you are in a hurry, I'll point out some of the more relevant sections for this assignment.

The main part in the code you are given are the data declarations, so once you're familiar with the basics (chapter 2 and the first section of chapter 3), a good place to dive in is the Algebraic data types intro, Type variables and Type parameters.

The above should be enough for deciphering the data declarations and understanding the relationship between q vs Q and o vs E.

Now to implement the actual function, you need to be familiar with how deterministic finite automata work and then know enough Haskell to write the actual implementation. Chapter 4 and chapter 5 are the most relevant chapters for this in the tutorial and you might also find the section on standard library list functions useful.

Once you get to this point, if you are stuck with the implementation, you can post another question with the code you have written so far.

Answer 2

In haskell we have three way to define new type, using three distinct keywords, type, newtype, and data.

In your example it's data keyword which is in use, let's focus a bit more on it.
It's better to start with the easiest one coming from your code

data E = A | B

Here, We have define a new type E which can take only two mode or state or value.
A type like this is what we call a sum type. How can we use a it ?
Mostly with pattern matching.

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

Now, a more complex data declaration from your code.

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

Again, as said previously we have a sum type which define a new type Q, taken three value, Q0, Q1 or Q2. But we have a deriving clause, which tell to the compiler that this new type implement the method (or function) deriving (or inherited) from Eq, Enum, Bounded class. What's that mean ?
Let's take a look to a function.
Imagine you want to associate a number for each of the value of Q, how can we perform that ?

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

If you want more insight about this particular functionality provide by deriving clause, read the resources which have been indicated and try :info Enum under ghci. Note that the previous type could also derive from the same class. As these types are fully describe as the sum of an enumerable set of value (discriminated by |) we better understand why we call them sum type.

Finally the most difficult data declaration.

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

If fact they are almost the same data definition then I will go trough the first one and let you the analyses of the second one as an exercise.

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

This time we must talk about data constructor and type constructor.

• On the left hand side of the equality, there is data constructor, to built data and give it a name. On this side we have the required parameter used to built this new data.
• On the right hand side of the equality, there is type constructor, to built this new type. On this side we have the explicit plumbering which show to the reader how this new type (data) is built using the existing type.

Now keeping in mind, that the following are type,

• [x] ::: Type representing the polymorphic list, Example, [Int] => List of Int
• x ::: A basic type, one of the existing one (Int, Char, String ...)
• x -> y ::: Type which define a function taken a type x to produce a type y.
• x -> y -> z ::: Type which define a function taken a type x and a type y to produce a type z. Which can be view as a function taking another function of type (x->y) and producing a type z. This is what we call an High-Order Function.

Then our data declaration, put in this context, is a data constructor, feed by two type parameter, q and o and as a result, it return a new type as the product of a high-order function a basic type and a list type. Which explain why we call this a product type.

It should be enough, now, infering by yourself, to answer your question what does n1 ?

Good luck.

Answer 3

From the little I understand about Haskell type declarations, the initial statements about DFA and NFA are saying something like (looking at NFA, for example):

(Left hand side:) NFA is a type that utilizes two types (q and o) in its construction.

(Right hand side:) an instance of NFA will be called NFA, and be composed of three parameters:
(1) "(q -> o -> [q])" , meaning a function that takes two parameters, one of type q and one of type o, and returns a list of q's, ([q])
(2) "[q]" , meaning one list of values of type q
(3) "[q]" , another list of values of type q

n1 seems like an instance construction of NFA, and we see

n1                          =  NFA d [Q0] [Q2]

So we can infer that:
(1) d is a function that takes two parameters, a 'q' and an 'o' and returns a list of q's
(2) [Q0] is a list of q's, and
(3) [Q2] is a list of q's.

And, indeed, the definition of d follows:
d takes two parameters, a 'Q' and an 'E' and returns a list of Q's (which we know can be either Q0, Q1, or Q2) or an empty list.

I hope that helps a little and/or perhaps someone could clarify and correct my vague understanding as well.