- Beginners - Haskell.org

Nullable attribute of a language grammar howto
by Larry Evans 02 Sep '08

02 Sep '08

The following is my first attempt at specifying a language grammar. The method of specification is to define an algebra for the grammar expression. This algebra is GramExpr with constants from enums ArithInp and ArithVar. The functions correspond to the choice and concatenation operators in compiler texts. Specification of grammar worked OK, as shows by the successful compile of all the prints for each expression as well as the successful print of the list of GramProd's. However, when I tried to calculate the Nullable attributes of the expressions, I ran into problems. What I wanted to do was execute a homomorphism from the grammar expressions to another algebra, the GramNull algebra. This GramNull algebra will eventually produce a set of recursive equations corresponding to the grammar productions. The solution of these equations will calculate whether a non-terminal (a member of the enum ArithVar) can derive the empty string. Would someone please let me know what I'm doing wrong or suggest a better way of calculating the Nullable attribute of the non-terminals. Eventually, I'd like to calculate the First and Follow attributes in a similar way. The source file is: <--- gram_alg.hs --- {- Purpose: Algebraic specification of language grammar. -} module Main where data ArithInp = Ident | Plus | Mult | ParenLeft | ParenRight deriving(Enum,Show) data ArithVar = Term | Factor | Expr deriving(Enum,Show) data GramExpr inp_type var_type --Grammar Expresson, i.e. the rhs of a production. = NullExpr --the empty string, i.e. the epsilon in Compiler texts. | InpExpr inp_type --a terminal, i.e. an inp_type, is a Grammar Expression | VarExpr var_type --a non-terminal, i.e. a var_type, is a Grammar Expression | (:|) (GramExpr inp_type var_type) (GramExpr inp_type var_type) {- :| is the choice grammar operator. E.g. input, i, matches x | y if i either matches x or y. -} | (:>>) (GramExpr inp_type var_type) (GramExpr inp_type var_type) {- :>> is the concatenation grammar operator. E.g. input, i, matches x :>> y if i matches x followed by y. -} deriving(Show) data GramProd inp_type var_type = (:==) var_type (GramExpr inp_type var_type) deriving(Show) data GramNull inp_type var_type = OneNull --can derive empty string, | ZeroNull --can't derive empty string. | VarNull var_type --unknow whether var_type can derive empty string | AltNull (GramNull inp_type var_type) (GramNull inp_type var_type) | CatNull (GramNull inp_type var_type) (GramNull inp_type var_type) deriving(Show) expr2null :: (GramExpr inp_type var_type) -> (GramNull inp_type var_type) {- expr2null GramExpr returns a GramNull expression which indicates whether the GramExpr can derive the empty string. -} expr2null NullExpr = OneNull expr2null (InpExpr inp_valu) = ZeroNull::(GramNull inp_type var_type) expr2null (VarExpr var_valu) = (VarNull var_valu)::(GramNull inp_type var_type) main = do { print Ident ; print Expr ; print (InpExpr Ident::GramExpr ArithInp ArithVar) ; print (VarExpr Expr::GramExpr ArithInp ArithVar) ; print ((InpExpr Ident :| VarExpr Factor)::GramExpr ArithInp ArithVar) ; print ((InpExpr Ident :>>VarExpr Factor)::GramExpr ArithInp ArithVar) ; print ((Factor :== InpExpr Ident)::GramProd ArithInp ArithVar) ; print ([ Factor :== ( InpExpr Ident :| ( InpExpr ParenLeft :>> VarExpr Expr :>> InpExpr ParenRight ) ) , Term :== ( VarExpr Factor :>> InpExpr Mult :>> VarExpr Factor ) , Expr :== ( VarExpr Term :>> InpExpr Plus :>> VarExpr Term ) ] ::[GramProd ArithInp ArithVar]) {- The above arg to print is the arithmetic expression grammar. -} ; print ((expr2null (InpExpr Mult))::(GramNull ArithInp ArithVar)) ; print ((expr2null (VarExpr Factor))::(GramNull ArithInp ArithVar)) ;} >--- gram_alg.hs --- The compile output is: <--- gram_alg.compile --- Compilation started at Mon Sep 1 11:02:19 make -k runghc -XMultiParamTypeClasses -XPatternSignatures gram_alg.hs gram_alg.hs:62:40: Couldn't match expected type `var_type1' against inferred type `var_type' `var_type1' is a rigid type variable bound by the polymorphic type `forall inp_type var_type1. GramNull inp_type var_type1' at gram_alg.hs:62:31 `var_type' is a rigid type variable bound by the type signature for `expr2null' at gram_alg.hs:53:32 In the first argument of `VarNull', namely `var_valu' In the expression: (VarNull var_valu) :: GramNull inp_type var_type In the definition of `expr2null': expr2null (VarExpr var_valu) = (VarNull var_valu) :: GramNull inp_type var_type make: *** [all] Error 1 >--- gram_alg.compile --- TIA. -regards, Larry

3 4

Help with Glade
by Daniel Fischer 02 Sep '08

02 Sep '08

Am Dienstag, 2. September 2008 00:21 schrieb Paul Johnston: > Sorry if it's a bit off topic but could anyone give me some pointers. > > Install Glade-3 (3.4.5) works great as a standalone > > However when trying to import Glade using the snippet below: > > module Main where > > import Graphics.UI.Gtk > import Graphics.UI.Gtk.Glade > > I get: > > > paulj@linux-yrwq:~/haskell> ghc --make hello3.hs -o hello3 > > hello3.hs:4:7: > Could not find module `Graphics.UI.Gtk.Glade': > Use -v to see a list of the files searched for. > > I'm fairly certain I'm missing an entry in package.conf as there are ones > for glib and cairo! > > Any thoughts gratefully accepted. > > Paul Did you build Gtk2Hs before you installed Glade? In that case the configure step determined that no glade is available and decided not to build that module. Then re-installing (complete: configure, build, install) Gtk2Hs should do the trick.

2 1

Help with Glade
by Paul Johnston 01 Sep '08

01 Sep '08

Sorry if it's a bit off topic but could anyone give me some pointers. I'm trying to get glade-3 to work with ghc. Installed ghc (works fine!) paulj@linux-yrwq:~/haskell> ghci GHCi, version 6.8.3: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Prelude> Installed Gtk2Hs The hello world program import Graphics.UI.Gtk main :: IO () main = do initGUI window <- windowNew button <- buttonNew set window [ containerBorderWidth := 10, containerChild := button ] set button [ buttonLabel := "Hello World" ] onClicked button (putStrLn "Hello World") onDestroy window mainQuit widgetShowAll window mainGUI (works fine!) Install Glade-3 (3.4.5) works great as a standalone However when trying to import Glade using the snippet below: module Main where import Graphics.UI.Gtk import Graphics.UI.Gtk.Glade I get: paulj@linux-yrwq:~/haskell> ghc --make hello3.hs -o hello3 hello3.hs:4:7: Could not find module `Graphics.UI.Gtk.Glade': Use -v to see a list of the files searched for. I'm fairly certain I'm missing an entry in package.conf as there are ones for glib and cairo! Any thoughts gratefully accepted. Paul

1 0

Monads and infinite types
by Greg Best 31 Aug '08

31 Aug '08

Hello-- I'm still trying to wade into Haskell after a fair amount of experience in other (mostly, but not exclusively, C-type) languages, and I'm finding this mind numbingly difficult. Usually the way I learn a new language is by finding an application for it and pounding my way through that application. In this case I've started by trying to parse apart a simple GPS NMEA sentence. I'm sure there are prefab libraries for parsing strings, but this seemed like a good way of getting aquatinted with the Monad. I've created a new data type similar to Maybe, but which can return no value, a single value, or a list of values. It seems to behave, but I haven't ruled it out as the cause of my frustration. The NMEAParser monad will eventually take a comma separated string and return a list of fields, lopping off the checksum at the end. Once I can do that, I can start adding other intelligence such as testing the checksum, bounds checking the fields, etc. At the bottom is the little bit of code I'm working with, and the error messages I'm getting out of ghci. Both errors confuse me-- infinite type message because I'm not sure where I've suggested that it build that type, and the "expected ZeroOrMore a but got ZeroOrMore b" message because I thought 'b' and 'a' were allowed to be different types but could also be the same. Any help wrapping my head around this would be appreciated, and will almost certainly be rewarded with more dumb questions in the near future. Thanks-- Greg --------------------------------- NMEATest.hs---------------------------------- module NMEATest where data ZeroOrMore a = NoVal | SingleVal a | MultiVal [a] deriving (Eq,Ord,Show) type Sentence = String newtype NMEAParser a = NMEAParser(Sentence -> (ZeroOrMore a, Sentence)) instance Monad NMEAParser where return a = NMEAParser(\s -> (SingleVal a,s)) NMEAParser k >>= f = NMEAParser(\s0 -> let (r1, s1) = k s0 k2 = f r1 (r2, s2) = k2 s1 in (r1,s2)) ------------------------------------------------------------------------------------ ------------------ghci output-------------------------------------------- Prelude> :l NMEATest.hs [1 of 1] Compiling NMEATest ( NMEATest.hs, interpreted ) NMEATest.hs:26:45: Occurs check: cannot construct the infinite type: a = ZeroOrMore a When generalising the type(s) for `k2' In the expression: let (r1, s1) = k s0 k2 = f r1 (r2, s2) = k2 s1 in (r1, s2) In the first argument of `NMEAParser', namely `(\ s0 -> let (r1, s1) = k s0 k2 = f r1 .... in (r1, s2))' NMEATest.hs:28:42: Couldn't match expected type `b' against inferred type `a' `b' is a rigid type variable bound by the type signature for `>>=' at <no location info> `a' is a rigid type variable bound by the type signature for `>>=' at <no location info> Expected type: ZeroOrMore b Inferred type: ZeroOrMore a In the expression: r1 In the expression: let (r1, s1) = k s0 k2 = f r1 (r2, s2) = k2 s1 in (r1, s2) Failed, modules loaded: none. Prelude> -------------------------------------------------------------------------------------------------

3 2

profiling in haskell
by Vlad Skvortsov 29 Aug '08

29 Aug '08

Hi! I'm trying to profile the code pasted below. Per the profiler output it takes about 30% of my program running time and I'd like to analyze it further. What I need is a breakdown on a finer level, so I inserted SCC annotations. However, they appear to have attributed zero cost. I use GHC 6.8.2 on FreeBSD, the code is compiled without -O options. What am I doing wrong? Note: I'm not trying to *optimize* this code (I intuitively know where the problems are). My intention is to learn the mechanics of profiling Haskell code. serialize :: Database -> [[String]] serialize (dmap, tmap) = [ {-# SCC "XXX1" #-} [dbFormatTag], {-# SCC "XXX2" #-} (dumpWith docToStr dmap), {-# SCC "XXX3" #-} (dumpWith termToStr tmap) ] where dumpWith f = Data.Map.foldWithKey f [] docToStr k (Doc { docName=n, docVectorLength=vl}) = (:) ("d " ++ show k ++ " " ++ n ++ " " ++ (show vl)) termToStr t il = (:) ("t " ++ t ++ " " ++ (foldl ilItemToStr "" il)) ilItemToStr acc (docid, weight) = show docid ++ ":" ++ show weight ++ " " ++ acc -- Vlad Skvortsov, vss(a)73rus.com, http://vss.73rus.com

2 1

Re: [Haskell-cafe] Is there GHC 6.8.3 on Ubuntu?
by Rafael Gustavo da Cunha Pereira Pinto 28 Aug '08

28 Aug '08

I'll take a look on how to build this package... Although I just want to use 6.8.3, I would really like to share my efforts. Now I just have to find a gap on my (and my wife's) agenda to do that! :-) Best regards On Thu, Aug 28, 2008 at 03:25, Ketil Malde <ketil(a)malde.org> wrote: > "Rafael Gustavo da Cunha Pereira Pinto" <RafaelGCPP.Linux(a)gmail.com> > writes: > > > Is there anyone packing GHC 6.8.3 for Ubuntu Hardy? > > The next Ubuntu release (8.10 Intrepid), seems to come with 6.8.2 as > well. > > If you want to pack 6.8.3, go for it! If you just wanted to use it, > I've had success using the binary snapshots on previous Ubuntus. > > -k > -- > If I haven't seen further, it is by standing in the footprints of giants > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

1 0

Functional programming concepts
by Rafael Gustavo da Cunha Pereira Pinto 28 Aug '08

28 Aug '08

Hi folks! Since I don't have a CS degree, there are some concepts I don't fully understand, and I'd like to propose a "begginers" thread to discuss some of those topics. For starters, what does a WHNF (weak-head normal form) mean? Cheers, -- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

4 7

ICFP 2007
by Rafael Gustavo da Cunha Pereira Pinto 28 Aug '08

28 Aug '08

First of all, sorry asking too many questions! I am using the ICFP 2007 (http://save-endo.cs.uu.nl/) problem as a case for learning Haskell. I started with the prototype, listed below =================Main.hs======================= module Main(main) where import qualified Data.ByteString.Lazy.Char8 as L import qualified Data.ByteString.Char8 as S import Data.ByteString.Search.BoyerMoore as BM import Debug.Trace data DNA=DNA {prefix :: L.ByteString, suffix :: L.ByteString} main::IO () main=do d<-L.readFile "endo.dna" let dna=DNA (L.pack "IIIIIIIIIIICCICCICCICFFIIIIIIIIIIIIIIIICFP") d let pat=S.pack "ICFP" print $ take 1 $ matchSL pat $ L.append (prefix dna) (suffix dna) =================EOF Main.hs=================== My question is: Knowing that the searched pattern is in DNA prefix, will "suffix dna" ever be called here? I mean, will the "append" suspension ever be fully evaluated? I am thinking on using a data type like data DNA=DNA {prefix::L.ByteString, worked::L.ByteString, suffix::ByteString} The invariant is that worked should be L.empty whenever prefix is L.empty. Thanks in advance -- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

2 1

Re: Beginners Digest, Vol 2, Issue 7
by Emmanuel 27 Aug '08

27 Aug '08

>> >> I am having troubles bulding the plugins package : >> >> manu:~/Desktop/tmp manu$ cabal install plugins >> Resolving dependencies... >> cabal: cannot configure plugins-1.2. It requires ghc >=6.8 > > That is the ghc-api package, of which it requires a version >= 6.8. > Could you verify that you have it installed (ghc-pkg list will tell > you what > you have)? it's not listed by ghc-pkg list, I have ... {ghc-6.8.1}, {ghc-6.8.2} ... where do I get it ? It's not listed on Hackage Thanks Emmanuel

2 1

findSubstring deprecated
by Rafael Gustavo da Cunha Pereira Pinto 27 Aug '08

27 Aug '08

Two quick questions: 1) Is there any replacement for the (now deprecated) findSubstring function on ByteString.Char8? 2) Does it work with ByteString.Lazy.Char8? Best Regards, Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

3 3