8 Replies - 1503 Views - Last Post: 31 July 2011 - 02:59 PM

#1 abhialmighty   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 04-August 09

haskell issue with expected and inferred type error

Posted 29 July 2011 - 04:38 PM

Hello,

I am implementing LL parsing in haskell. I am reading grammar and have functions to get the terminals and non-terminals. I got a code snippet as an example and I see the following error with the usage,


Couldn't match expected type `Data.Set.Set a'
against inferred type `[s]'
Expected type: [Data.Set.Set a]
Inferred type: [[s]]
In the second argument of `(.)', namely
`map (filter isT . snd) . snd'
In the expression: unions . map (filter isT . snd) . snd
Failed, modules loaded: none.


here's the code snippet,

 
import Data.Set (union,unions)
import Data.List (nub)
import qualified Data.Map (Map)

class Eq s => Symbol s where
  isT :: s -> Bool
  isN :: s -> Bool
  isT = not . isN

type Grm s = (s,[(s,[s])])

ourGrammar :: Grm Char
ourGrammar =
   ('S', [('S',"AaS"),('S',"B"),('S',"CB"),('A',"SC"),('A',"") ,('B',"A"),('B',"b"),('C',"D"),('D',"d")])

start :: Grm s -> s
start = fst

prods :: Grm s -> [(s,[s])]
prods = snd

terminals :: (Symbol s, Ord s) => Grm s -> [s]
terminals = unions . map (filter isT . snd) . snd


Is This A Good Question/Topic? 0
  • +

Replies To: haskell issue with expected and inferred type error

#2 sepp2k   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2757
  • View blog
  • Posts: 4,419
  • Joined: 21-June 11

Re: haskell issue with expected and inferred type error

Posted 29 July 2011 - 05:55 PM

map f xs returns a list of foos, where foo is the type returned by f.

Since filter isT xs returns a list of some sort (filter having the type (a -> Bool) -> [a] -> [a]), the type of map (filter isT . snd) is Eq a => [(b, [a])] -> [[a]], which means it returns a list of lists.

However Data.Set.unions wants a list of sets as its argument - not a list of lists. So you get the error you get.

To fix this, you should use map . fromList to convert your list of lists to a list of sets first (you need to import Data.Set.fromList first).
Was This Post Helpful? 0
  • +
  • -

#3 abhialmighty   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 04-August 09

Re: haskell issue with expected and inferred type error

Posted 29 July 2011 - 06:39 PM

sepp2k,

Thanks so much for the immediate response . I tried the change you suggested, but I see that it still complains with the type error,


Couldn't match expected type `[a]'
against inferred type `(a2, [a1]) -> [a1]'
In the first argument of `fromList', namely `(filter isT . snd)'
In the first argument of `(.)', namely
`fromList (filter isT . snd)'
In the second argument of `(.)', namely
`fromList (filter isT . snd) . snd'


I updated the code with these changes,

import Data.Set (union,unions,fromList)
.
.
.
terminals :: (Symbol s, Ord s) => Grm s -> [s]
terminals = unions . map.fromList(filter isT . snd). snd



Please forgive my lack of understanding, I am very very new to Haskell and hence lacking lot of understanding. Am I missing something here or doing something wrong ? Should I be using fromList even on the second argument i.e "snd" ? Thanks in advance

This post has been edited by abhialmighty: 29 July 2011 - 06:40 PM

Was This Post Helpful? 0
  • +
  • -

#4 sepp2k   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2757
  • View blog
  • Posts: 4,419
  • Joined: 21-June 11

Re: haskell issue with expected and inferred type error

Posted 29 July 2011 - 06:56 PM

That's just a precedence error. You need to add a dot after fromList or add another set of parentheses.

terminals = unions . map.fromList(filter isT . snd). snd

is parsed like
terminals xs = unions ( map (fromList (filter isT . snd)) snd) xs

, which makes very little sense. What you wanted was
terminal xs = unions (map (fromList (filter (isT . snd) (snd xs))))

, which could be expressed just like that or as:
terminals = unions . map . fromList . filter (isT . snd) . snd


Generally I'd suggest that as long as you're new to Haskell, you stick with "point-full" notation (i.e. use explicit parameter and parentheses everywhere) at the beginning and then perhaps try to refactor to point-free notation once you got your code working (or don't - it's not like it's essential).

This post has been edited by sepp2k: 29 July 2011 - 06:58 PM

Was This Post Helpful? 0
  • +
  • -

#5 abhialmighty   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 04-August 09

Re: haskell issue with expected and inferred type error

Posted 29 July 2011 - 07:27 PM

Thanks Sepp2k. Its really starting to get to me now. It seems it is looking for the second argument to be a list, no ?

I get this error now,

 
    Couldn't match expected type `a -> b'
           against inferred type `Data.Set.Set (s, [s])'
    In the second argument of `(.)', namely
        `fromList . filter (isT . snd) . snd'
    In the second argument of `(.)', namely
        `map . fromList . filter (isT . snd) . snd'
    In the expression:
          unions . map . fromList . filter (isT . snd) . snd
    


As a side-note, am I using wrong import ?

import Data.Set (union,unions,fromList)

Was This Post Helpful? 0
  • +
  • -

#6 sepp2k   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2757
  • View blog
  • Posts: 4,419
  • Joined: 21-June 11

Re: haskell issue with expected and inferred type error

Posted 30 July 2011 - 05:23 AM

Bah, my bad, I got confused about which result of what expression should be passed to which function. Also there's another problem with your code: Your call to filter will still result in a list of tuples of lists, where you want to have a list of lists (so you can turn it into a list of sets which you can then pass to unions). The easiest solution would be to just call map snd on the list of tuples first, and then pass it as a list of lists to filter and then map fromList. So the code becomes:

terminals xs = unions (map fromList (filter isT (map snd (snd xs))))


or
terminals = unions . map fromList . filter isT . map snd . snd


or if you want to go the readable route:
terminals (_, productions) = unions . setify . onlyTerminals $ productionTargets
  where
    setify = map fromList
    onlyTerminals = filter isT
    productionTargets = map snd productions



Note that this doesn't match your type signature as unions returns a set and not a list. This can be fixed by either accepting that and changing the signature or adding a call to toList to turn the set into a list again.

And your import is fine.
Was This Post Helpful? 2
  • +
  • -

#7 abhialmighty   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 04-August 09

Re: haskell issue with expected and inferred type error

Posted 31 July 2011 - 03:17 AM

Thanks Sepp2k so much for your help with all those info. It did help me understand the stuffs far better. I just had to tweak a little more in the code for it to work. Thanks for your help.

Since we are talking about this, I had a quick question as to can we actually retain the details of data that we read from a file outside the do block ?

While searching through when understanding Haskell, I saw about the "System.IO" usage of withFile function to read from a file. Though we use
main = do
              withFile "abc.txt" ReadMode (\handle -> do
                       contents <- hGetContents handle
                       putStr contents)


My question was can we access the data in "Contents" later in the program ? If yes, how do I achieve it ? Once I go out of the "main" block, I do not see this being retained anywhere.
Was This Post Helpful? 0
  • +
  • -

#8 sepp2k   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2757
  • View blog
  • Posts: 4,419
  • Joined: 21-June 11

Re: haskell issue with expected and inferred type error

Posted 31 July 2011 - 05:02 AM

Once you get out of main, your program is over. There is no later in your program. Any code that runs in your program runs because it has been called from main (directly or indirectly) - there is nothing that runs after main has finished.

So to answer your question, if other functions need to access contents, you should just call them with contents as their argument.
Was This Post Helpful? 2
  • +
  • -

#9 abhialmighty   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 04-August 09

Re: haskell issue with expected and inferred type error

Posted 31 July 2011 - 02:59 PM

Yup, that did get my doubts cleared. Thanks so much Sepp2k, I have a far better understanding than when I started off.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1