Haskell - "Parse error on input"

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

stone915
Posts: 42
Joined: Wed Jan 07, 2009 4:31 am UTC

Haskell - "Parse error on input"

Postby stone915 » Mon Jan 26, 2009 3:03 am UTC

Hi, I'm working on some code to implement a directed graph for a computer science class. The graph will contain a list of ordered pairs made up of a vertex and a list of vertices connected to that vertex (an adjacency list). I was given a template with type declarations and function type signatures and was told to implement the functions. I have a couple of the functions written, but I'm encountering some difficulty writing the function to add a vertex with an empty adjacency list to the graph. Whenever I try to compile the code, I get this error message.

Code: Select all

ps2.hs:4:16: parse error on input `insertVertex'


Can anyone tell me what this message means? I've tried removing the if-then-else portion since my prof told us it was optional and using (graph Char Int) instead of graph as a parameter, but neither worked. I also added

Code: Select all

type v = Char
type e = Int

to the code and v,e to the module interface given to us in the template, so if that could be causing the problem please let me know and explain why that's a problem. I'd prefer minimal help, such as an explanation of the error message or a syntax correction rather than a step by step solution, as this is for a class and I'm trying to learn these concepts. Thanks!

Code: Select all

-- A module for creating and handling directed graphs

module Digraph (AdjList, Digraph, Edge, v, e
                insertVertex, insertEdge, makeDigraph, getAdj,
                empty, vertexInGraph
               ) where

-- In these type declarations, v is the vertex type
-- and e is the edge label type

type AdjList v e = [(v, e)]
type Digraph v e = [(v, AdjList v e)]
type Edge v e    = (v, v, e)
type v = Char
type e = Int

empty            :: Digraph v e
empty = []

-- Adds a new vertex with an empty adjacency list to the digraph
insertVertex     :: (Eq v) => v -> Digraph v e -> Digraph v e
insertVertex v graph = if (vertexInGraph v graph)
                                        then error "Vertex already in graph"
                                             else graph ++ [(v,[])]

-- Creates a list of the vertices in the graph, then checks to see if
-- any of them are the same as the given vertex, then checks for a
-- value of True in the resulting list
vertexInGraph    :: (Eq v) => v -> Digraph v e -> Bool
vertexInGraph v graph = foldl || false (map (== v) (map fst graph))

stone915
Posts: 42
Joined: Wed Jan 07, 2009 4:31 am UTC

Re: Haskell - "Parse error on input"

Postby stone915 » Mon Jan 26, 2009 3:31 am UTC

Minor update:

I removed the "v,e," from the module interface and the " v = Char, e = Int" type declarations, then updated the insertVertex function to

Code: Select all

insertVertex v (graph Char Int) = if (vertexInGraph v graph)
                                      then error "Vertex already in graph"
                                           else graph ++ [(v,[])]


Now I get

Code: Select all

ps2.hs:20:16: Parse error in pattern

as my error message. Any ideas on what's causing this, or an explanation as to what a parse error is?

dosboot
Posts: 143
Joined: Sun Jul 01, 2007 5:26 am UTC

Re: Haskell - "Parse error on input"

Postby dosboot » Mon Jan 26, 2009 3:52 am UTC

v and e cannot denote types; Types, Constructors and Modules must start with Upper Case.

The code

Code: Select all

insertVertex v (graph Char Int) =

will give an error because this says 'graph' accepts two type arguments (otherwise put: graph has kind *->*->*).

stone915
Posts: 42
Joined: Wed Jan 07, 2009 4:31 am UTC

Re: Haskell - "Parse error on input"

Postby stone915 » Mon Jan 26, 2009 4:18 am UTC

dosboot wrote:v and e cannot denote types; Types, Constructors and Modules must start with Upper Case.

The code

Code: Select all

insertVertex v (graph Char Int) =

will give an error because this says 'graph' accepts two type arguments (otherwise put: graph has kind *->*->*).


Thanks. I was making a stupid mistake; I was trying to define the variable types that were in a type signature in the actual function definition.
Working code:

Code: Select all

-- Adds a new vertex with an empty adjacency list to the digraph
insertVertex     :: (Eq v) => v -> Digraph v e -> Digraph v e
insertVertex v1 graph | (vertexInGraph v1 graph) = error "Vertex already in graph"
                      | otherwise = graph ++ [(v1,[])]


Now I have a new problem

Not working code:

Code: Select all

-- Creates a list of the vertices in the graph, then checks to see if
-- any of them are the same as the given vertex, then checks for a
-- value of True in the resulting list

vertexInGraph v1 graph = foldl || False (map (== v1) (map fst graph))


Error message:

Code: Select all

    Couldn't match expected type `Bool'
           against inferred type `(a -> b -> a) -> a -> [b] -> a'
    In the first argument of `(||)', namely `foldl'


I'm trying to create a list of vertices by mapping the fst function onto the graph, which is a list of ordered pairs, then I'm trying to create a list of Bools by mapping ( == (input vertex)) onto that list, then folding (|| false) across that list to return a single Bool. Any ideas on why this isn't working? Thanks!

dosboot
Posts: 143
Joined: Sun Jul 01, 2007 5:26 am UTC

Re: Haskell - "Parse error on input"

Postby dosboot » Mon Jan 26, 2009 4:24 am UTC

You have to pass || as (||) for parameters. There's also a standard function for what you are trying to do.

Made some changes:

Code: Select all

-- A module for creating and handling directed graphs

module Digraph where --my 2 cents: export all by default unless you ready need to

import Data.List

type AdjList = [(Vertex, Edge)]
type Digraph = [(Vertex, AdjList)]
type Edge = (Vertex, Vertex, Int)
type Vertex = Char

empty :: Digraph
empty = []

-- Adds a new vertex with an empty adjacency list to the digraph
insertVertex :: Vertex -> Digraph -> Digraph
insertVertex v graph =
   if (vertexInGraph v graph)
    then error "Vertex already in graph"
    else (v,[]) : graph --cons is O(1) while ++ is O(n)

-- Creates a list of the vertices in the graph, then checks to see if
-- any of them are the same as the given vertex, then checks for a
-- value of True in the resulting list
vertexInGraph    :: Vertex -> Digraph -> Bool
vertexInGraph v graph = foldl' (||) False (map (== v) (map fst graph)) --use foldl' over foldl

vertexInGraph_alt :: Vertex -> Digraph -> Bool
vertexInGraph_alt v graph = v `elem` verts where verts = fst $ unzip graph --prelude and standard libraries have lots of handy functions.

stone915
Posts: 42
Joined: Wed Jan 07, 2009 4:31 am UTC

Re: Haskell - "Parse error on input"

Postby stone915 » Mon Jan 26, 2009 4:58 am UTC

Awesome, thanks for the advice. I don't think I'm going to use too many of your modifications, partly because it involves code we haven't covered in class yet and partly because I'd rather turn in code I wrote myself (no offense, it's an honor code/pride in my own work thing). However, I do appreciate the recommendations. I did replace the concatenation with (:) for efficiency. I think I'm going to leave the v and e data types generalized though, because that was part of the original template and I think my prof wants it to be applicable to all forms of vertices and edge labels. Just out of curiosity, what is the difference between foldl' and foldl?

Minor problem which you don't have to answer because you've already helped me out a lot: any idea on why I would be getting a parse error on input 'empty' ?

Code: Select all

empty            :: Digraph v e
empty = []

It's supposed to return an empty graph, which is a list, so I thought I could just return an empty list, but apparently I was wrong.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Haskell - "Parse error on input"

Postby Berengal » Mon Jan 26, 2009 5:05 am UTC

stone915 wrote:Minor problem which you don't have to answer because you've already helped me out a lot: any idea on why I would be getting a parse error on input 'empty' ?

Code: Select all

empty            :: Digraph v e
empty = []

It's supposed to return an empty graph, which is a list, so I thought I could just return an empty list, but apparently I was wrong.

That should work just fine. What exact message are you getting?
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

stone915
Posts: 42
Joined: Wed Jan 07, 2009 4:31 am UTC

Re: Haskell - "Parse error on input"

Postby stone915 » Mon Jan 26, 2009 5:24 am UTC

Berengal wrote:That should work just fine. What exact message are you getting?


Code: Select all

ps2.hs:9:16: parse error on input `empty'


EDIT: I counted the lines, and line 16 isn't the definition of the empty function, it's this:

Code: Select all

insertVertex     :: (Eq v) => v -> Digraph v e -> Digraph v e

So now I'm even more confused...

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: Haskell - "Parse error on input"

Postby Qoppa » Mon Jan 26, 2009 5:36 am UTC

line:character#, not the other way around. So it's line 9, character 16 causing the error.

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

dosboot
Posts: 143
Joined: Sun Jul 01, 2007 5:26 am UTC

Re: Haskell - "Parse error on input"

Postby dosboot » Mon Jan 26, 2009 5:38 am UTC

I'm guessing the second 'empty' was indented, making it think you wanted something with type "Digraph v e empty".

stone915
Posts: 42
Joined: Wed Jan 07, 2009 4:31 am UTC

Re: Haskell - "Parse error on input"

Postby stone915 » Mon Jan 26, 2009 5:40 am UTC

Here's the code from the top. Line 9, character 16 is the beginning of the declaration of empty in the module interface. As I was typing that, I realized I forgot to add a comma after insertVertex when I commented out the other functions I need to implement. Problem solved. Thanks guys.

Code: Select all

-- CS 8 Problem Set 2
-- Author: Matt Stone

-- A module for creating and handling directed graphs

module Digraph (AdjList, Digraph, Edge,
                insertVertex
--, insertEdge, makeDigraph, getAdj,
                empty, vertexInGraph
               ) where

-- In these type declarations, v is the vertex type
-- and e is the edge label type

type AdjList v e = [(v, e)]
type Digraph v e = [(v, AdjList v e)]
type Edge v e    = (v, v, e)

empty            :: Digraph v e
empty = []

dosboot
Posts: 143
Joined: Sun Jul 01, 2007 5:26 am UTC

Re: Haskell - "Parse error on input"

Postby dosboot » Mon Jan 26, 2009 5:56 am UTC

foldl is lazy while foldl' is strict. Try this in ghci

Code: Select all

Prelude> let ff = take 1000000 (repeat False)                           
Prelude> import Data.List                                   

Prelude Data.List> foldl' (||) False ff                     
False                                                       

Prelude Data.List> foldl (||) False ff                     
*** Exception: stack overflow                               
 


In the second case foldl creates the entire giant expression (a1 || a2 || a3 ...) first. In the first case each step of the computation is evaluating something to the effect of False || 'rest' where 'rest' is a tail recursive call to foldl'. You can google foldl' vs foldl for some better explanations.

stone915
Posts: 42
Joined: Wed Jan 07, 2009 4:31 am UTC

Re: Haskell - "Parse error on input"

Postby stone915 » Mon Jan 26, 2009 7:04 am UTC

Awesome, thanks for the help and info. Found an article about the different types of folds if anyone else is interested.
http://haskell.org/haskellwiki/Foldr_Foldl_Foldl'

stone915
Posts: 42
Joined: Wed Jan 07, 2009 4:31 am UTC

Re: Haskell - "Parse error on input"

Postby stone915 » Tue Jan 27, 2009 2:26 am UTC

So, new problem. I'm working on the second part of the assignment. My job is to use the Digraph module to create a finite automaton. Basically, it will hold a directed graph, an initial value, and a list of possible final values. The directed graph will hold state values and path labels. In the example my prof gave us, he wants the states to be Chars and the path labels to be either 0 or 1. So the edge ('a','b',1) means that when given the input 1, move from state 'a' to state 'b'. I'm currently trying to write a function (stepDFA) that, when given an automaton, a state name, and an input symbol, will return the state reachable from the given state by using that input. It's supposed to be deterministic; if it is possible to reach more than one state, it should return an error. I haven't written that part yet, I'm waiting until I can get the function itself to work. I'm getting what I think is a syntax error, but I've gone through it a few times and can't see any mistakes. Any ideas on what could be producing this error message

Code: Select all

FA.hs:21:0:
    Occurs check: cannot construct the infinite type: a = b -> a
    When generalising the type(s) for `stepDFA'


when I try to compile this code? Thanks!

Code: Select all

-- CS 8 Problem Set 2
-- FA.hs
-- Author: Matt Stone

module FA where

import Digraph

data Automaton a b = FA {graph :: Digraph a b, start :: a, final :: [a]}
     deriving Show

-- Given a list of states, a list of paths from state to state, a beginning state,
-- and a list of possible final states, will create an automaton
makeAutomaton :: (Eq a, Eq b) => [a] -> [Edge a b] -> a -> [a] -> Automaton a b
makeAutomaton states edges start finals = FA {graph = (makeDigraph states edges), start = start, final = finals}

-- Creates a generic automaton
dfa1 = makeAutomaton ['a', 'b', 'c', 'd'] [('a', 'a', 0), ('a', 'b', 1), ('b', 'a', 1), ('b', 'c', 0), ('c', 'b', 0),
     ('c', 'c', 1), ('d', 'a', 0), ('d', 'b', 1)]
      'd'
        ['a']

stepDFA :: (Eq a, Eq b) => Automaton a b -> a -> b -> a
stepDFA (autom) state input | not (vertexInGraph state (graph autom)) = error "State is not in automaton."
                            | otherwise = checkInput (getAdj state (graph autom))
                                where checkInput :: [(a,b)] -> b -> a
                                      checkInput [] input = error "Invalid input."
                                      checkInput (p1:ps) input | input == (snd p1) = fst p1
                                                               | otherwise = checkInput ps input

Laguana
Posts: 49
Joined: Sat Jan 19, 2008 10:13 pm UTC

Re: Haskell - "Parse error on input"

Postby Laguana » Tue Jan 27, 2009 2:50 am UTC

Have a look at the type of your checkInput function:

Code: Select all

checkInput :: [(a,b)] -> b -> a


and look at where you use it:

Code: Select all

checkInput (getAdj state (graph autom))


See how it has one argument?

This means that the result of that line there is of type b -> a.

However, you've declared the return type of the function is a: This means that a = b->a, which is an infinite type (hence the error). I think you mean to add another argument to that, most likely "input".

stone915
Posts: 42
Joined: Wed Jan 07, 2009 4:31 am UTC

Re: Haskell - "Parse error on input"

Postby stone915 » Tue Jan 27, 2009 3:01 am UTC

Laguana wrote:I think you mean to add another argument to that, most likely "input".


Yes I did. Fixed. Thanks a lot!


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 14 guests