Finding Distinct Terminal and Nonterminals Symbols

Question

I am currently working on writing two functions that will be used to return lists of all distinct terminals that appear in a given grammar.

Here is the type for Grammar :

data Grammar = Grammar [Prod]
               deriving (Show, Eq)

Here is what I have so far :

terminals :: Grammar -> [String]                                          
terminals ts = nub [ x | x <-ts]

nonterms  :: Grammar -> [String]
nonterms nt = nub [ x | x <- nt]

Where the grammar that is being placed into the function would be something like this (3 Examples) :

g4 = "P -> true ; P -> false; P -> not P ; P -> P and P"
g5 = "P -> P & N; P -> N; N -> ~ N; N -> t"                                   
g6 = "P -> N & P; P -> N; N -> ~ N; N -> t"

However though, the functions that I am using do not work because GHCI could not match expected type ‘[String]’ with actual type ‘Grammar’.

I am going off of the basic principles of Context-free grammars (CFGs), that a context-free grammar is

 G = (T,N,P,S)

Where T is a set T of terminal symbols ("tokens"), a set N of nonterminal symbols, a set P of productions, and a start symbol S.

How could I use / write two functions that could return lists of all the distinct terminals (respectively nonterminals) that appear in a given grammar. Three examples of grammars above. Thank you.

Grammar isn't a type that's built in to Haskell. Please post its definition. — Joseph Sible-Reinstate Monica

Joseph Sible-Reinstate Monica Joseph Sible-Reinstate Monica · Accepted Answer · 2019-03-07T03:07:29

terminals :: Grammar -> [String]                                          
terminals ts = nub [ x | x <-ts]

Your function terminals is typed as returning a [String]. Its implementation returns the result of nub. nub has type Eq a => [a] -> [a], so for it to return a [String], its input must be a [String] as well. This implies that [ x | x <-ts] must be of type [String], and then that x must be of type String. Doing x <- ts in a list comprehension means that ts must be a list of whatever type x is, so in this case, ts must be [String].

Now the problem becomes apparent. Given the type of the output of your function and its implementation, ts must be of type [String], but given the type of the input of your function, ts must be of type Grammar. Since [String] and Grammar are different types, this causes the type error that you're seeing.

Side note: [ x | x <-ts] is exactly equivalent to just ts, and [ x | x <- nt] is exactly equivalent to just nt.

Finding Distinct Terminal and Nonterminals Symbols

1 Answers