June 2009 - Haskell-Cafe

Weird and entirely random problem...
by Jeff Heard 10 Jun '09

10 Jun '09

The code that causes it is here: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5731#a5731 This is the strangest thing. Occasionally, using nothing but gets and puts and frees on a non-full Cache will result in this: Cache { store = fromList [("(\"icons/addBookmark.png\",False)",TextureObject {textureID = 4}) ,("(\"icons/addCircle.png\",False)",TextureObject {textureID = 1}) ,("(\"icons/addContent.png\",False)",TextureObject {textureID = 2}) ,("(\"icons/addElsewhereLink.png\",False)",TextureObject {textureID = 3})] , times = fromList [(61314,"(\"<span font_desc='sans 8'>294.0</span>\",AlignLeft,Nothing,WrapWholeWords,False,0.0,0.0)") ,(61316,"(\"icons/addBookmark.png\",False)"),(61318,"(\"icons/addCircle.png\",False)") ,(61320,"(\"icons/addContent.png\",False)"),(61322,"(\"icons/addElsewhereLink.png\",False)")] , now = 61323 , maxsize = 1024768000 , size = 4 , decimation = 0 } Sometimes the problem is self-correcting. Sometimes it is most certainly not. But I don't understand how my code can possibly allow for this.

2 2

Convert IO Int to Int
by ptrash 10 Jun '09

10 Jun '09

Hi, I am using the System.Random method randomRIO. How can I convert its output to an Int? Thanks... -- View this message in context: http://www.nabble.com/Convert-IO-Int-to-Int-tp23940249p23940249.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

16 23

How To Make It Faster?
by paravinicius＠yahoo.com.br 10 Jun '09

10 Jun '09

Hi, I come up with the following solution for this spoj problem (warning!): problem: https://www.spoj.pl/problems/ARITH2/ solution: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5720#a5720 I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. Thanks in advance, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E

2 1

How To Make It Faster?
by Diego Souza 10 Jun '09

10 Jun '09

Hi, I come up with the following solution for this easy spoj problem (warning!): problem: https://www.spoj.pl/problems/ARITH2/ solution: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5720#a5720 I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. Thanks in advance, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E

2 1

nubBy seems broken in recent GHCs
by Cale Gibbard 10 Jun '09

10 Jun '09

According to the Report: nubBy :: (a -> a -> Bool) -> [a] -> [a] nubBy eq [] = [] nubBy eq (x:xs) = x : nubBy eq (filter (\y -> not (eq x y)) xs) Hence, we should have that nubBy (<) (1:2:[]) = 1 : nubBy (<) (filter (\y -> not (1 < y)) (2:[])) = 1 : nubBy (<) [] = 1 : [] However in ghc-6.10.3: Prelude Data.List> nubBy (<) [1,2] [1,2] The order of the parameters to the function which is passed to nubBy is *important* since the function might not be an equivalence relation. nubBy is more generally useful for sieving even when the relation is not symmetric. groupBy, for a similar reason, has applications for grouping beyond those provided by equivalence relations, and I think we should be able to rely on its behaviour. Moreover, I contend that the Report's order is more sensible, since the parameters to the relation stay in the left-to-right order in which they occurred in the list. It would be good if this could get fixed for 6.10.4. - Cale PS: There is actually another implementation of groupBy which would *also* be useful to have, but which is exactly the same for equivalence relations as groupBy, and it compares adjacent elements rather than the first element of a group with successive ones. (groupByAdjacent or something would be a reasonable name.) An implementation of it can be found here: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5595

4 4

help with a question
by haonan21 10 Jun '09

10 Jun '09

I'm very new to haskell hugs and would appreciate it if someone could help me out here. I've been giving 2 questions. 1.) A and B are two sets of integers. Implement a function to obtain the integers that belong to both sets. Test your function fully. 2.) Define and test a function f, which, if A is a set of {x, y, z} then f(A) = {{},{x}, {y}, {z}, {x, y}, {x,z}, {y,z}, {x, y, z}} Manage to get the first one. interset::[Int]->[Int]->[Int] interset x [] = [] interset [] y = [] interset x@(xs:xt) y@(ys:yt) = if xs == ys then as:(interset at yt) else interset at y Totally have no clue for the 2nd question. could someone help me out ? Many thanks! -- View this message in context: http://www.nabble.com/help-with-a-question-tp23946402p23946402.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 1

I love purity, but it's killing me.
by Tom Hawkins 09 Jun '09

09 Jun '09

I've been programming with Haskell for a few years and love it. One of my favorite applications of Haskell is using for domain specific languages. However, after designing a handful of DSLs, I continue to hit what appears to be a fundamental hurdle -- or at least I have yet to find an adequate solution. My DSLs invariably define a datatype to capture expressions; something like this: data Expression = Add Expression Expression | Sub Expression Expression | Variable String | Constant Int deriving Eq Using the datatype Expression, it is easy to mass a collections of functions to help assemble complex expressions, which leads to very concise programs in the DSL. The problem comes when I want to generate efficient code from an Expression (ie. to C or some other target language). The method I use invovles converting the tree of subexpressions into an acyclic graphic to eliminate common subexpressions. The nodes are then topologically ordered and assigned an instruction, or statement for each node. For example: let a = Add (Constant 10) (Variable "i1") b = Sub (Variable "i2") (Constant 2) c = Add a b would compile to a C program that may look like this: a = 10 + i1; b = i2 - 2; c = a + b; The process of converting an expression tree to a graph uses either Eq or Ord (either derived or a custom instance) to search and build a set of unique nodes to be ordered for execution. In this case "a", then "b", then "c". The problem is expressions often have shared, equivalent subnodes, which dramatically grows the size of the tree. For example: let d = Add c c e = Add d d -- "e" now as 16 leaf nodes. As these trees grow in size, the equality comparison in graph construction quickly becomes the bottleneck for DSL compilation. What's worse, the phase transition from tractable to intractable is very sharp. In one of my DSL programs, I made a seemingly small change, and compilation time went from milliseconds to not-in-a-million-years. Prior to Haskell, I wrote a few DSLs in OCaml. I didn't have this problem in OCaml because each "let" expression was mutable, and I could use the physical equality operator to perform fast comparisons. Unfortunately, I have grown to love Haskell's type system and its lack of side effects, and could never go back. Is there anything that can be done to dramatically speed up comparisons, or is there a better approach I can take to extract common subexpressions? I should point out I have an opportunity to get Haskell on a real industrial application. But if I can't solve this problem, I may have to resort to far less eloquent languages. :-( Thanks for any and all help. -Tom

17 36

Re: [Haskell-cafe] please comment on my parser, can I do this cleaner?
by Thomas Hartman 09 Jun '09

09 Jun '09

Thanks. It seems my original parser also works against FOO,BAR,BAZ if you only modify atom = string "," <|> ( many1 $ noneOf "()<>," ) -- add , Indeed, what to call the "thingies" in a parser is a source of some personal consternation. What is a token, what is an atom, what is an expr? It all seems to be somewhat ad hoc. > 2009/6/9 Daniel Fischer <daniel.is.fischer(a)web.de>: >> Am Dienstag 09 Juni 2009 20:29:09 schrieb Thomas Hartman: >>> All I want to do is split on commas, but not the commas inside () or <> >>> tags. >>> >>> I have been wanting to master parsec for a long time and this simple >>> exercise looked like a good place to start. >>> >>> The code below does the right thing. Am I missing any tricks to make >>> this simpler/neater? >>> >>> Thanks, thomas. >>> >>> thartman@ubuntu:~/perlArena>cat splitEm. >>> splitEm.hs splitEm.hs~ splitEm.pl splitEm.pl~ >>> thartman@ubuntu:~/perlArena>cat splitEm.hs >>> {-# LANGUAGE ScopedTypeVariables #-} >>> import Text.ParserCombinators.Parsec >>> import Text.ParserCombinators.Parsec.Char >>> import Text.PrettyPrint (vcat, render, text) >>> import Data.List.Split hiding (sepBy, chunk) >>> import Text.ParserCombinators.Parsec.Token >>> >>> import Debug.Trace >>> import Debug.Trace.Helpers >>> >>> -- this works, but is there a neater/cleaner way? >>> main = ripInputsXs (toEof splitter) "splitter" [ goodS, badS ] >>> >>> -- I need a way to split on commas, but not the commas inside '<>' or >>> '()' characters >>> goodS = "<*2>FOO<2,1>,<*3>(SigB<8:0:2>,BAR),<*2>Siga<2:0>,Sigb<8,7,6,5,0>" >>> badS = "<*2)FOO<2,1>,<*3>(SigB<8:0:2>,BAR),<*2>Siga<2:0>,Sigb<8,7,6,5,0>" >>> -- the first < matches a ), so reject this >>> >>> >>> splitter = do >>> chunks :: [String] <- toEof (many chunk) >>> let pieces = map concat $ splitOn [","] chunks >>> return pieces -- chunks >>> where >>> atom = string "," >>> <|> ( many1 $ noneOf "()<>" ) >>> chunk = parenExpr <|> atom >> >> I think that does not do what you want. >> >> For input "FOO,BAR,BAZ", chunks is ["FOO,BAR,BAZ"], that won't be split; as far as I can >> see, it splits only on commas directly following a parenExpr (or at the beginning of the >> input or directly following another splitting comma). >> >>> parenExpr :: GenParser Char st [Char] >>> parenExpr = let paren p = betweenInc (char '(' ) (char ')' ) p >>> <|> betweenInc (char '<' ) (char '>' ) >>> p >>> in paren $ option "" $ do ps <- many1 $ parenExpr <|> atom >>> return . concat $ ps >>> >>> betweenInc o' c' p' = do >>> o <- o' >>> p <- p' >>> c <- c' >>> return $ [o] ++ p ++ [c] >>> >>> toEof p' = do >>> r <- p' >>> eof >>> return r >>> >>> >>> >>> >>> >>> >>> ripInputs prs prsName xs = mapM_ (putStrLn . show . parse prs prsName ) xs >>> ripInputsXs prs prsName xs = mapM_ (putStrLn . showXs . parse prs prsName ) >>> xs where showXs v = case v of >>> Left e -> show e >>> Right xs -> render . vcat . map text $ xs >> >> I can offer (sorry for the names, and I don't know if what that does is really what you >> want): >> >> >> keepSepBy :: Parser a -> Parser a -> Parser [a] >> keepSepBy p sep = (do >> r <- p >> (do s <- sep >> xs <- keepSepBy p sep >> return (r:s:xs)) <|> return [r]) >> <|> return [] >> >> twain :: Parser a -> Parser a -> Parser [a] -> Parser [a] >> twain open close list = do >> o <- open >> l <- list >> c <- close >> return (o:l++[c]) >> >> comma :: Parser String >> comma = string "," >> >> simpleChar :: Parser Char >> simpleChar = noneOf "<>()," >> >> suite :: Parser String >> suite = many1 simpleChar >> >> atom :: Parser String >> atom = fmap concat $ many1 (parenExp <|> suite) >> >> parenGroup :: Parser String >> parenGroup = fmap concat $ keepSepBy atom comma >> >> parenExp :: Parser String >> parenExp = twain (char '<') (char '>') parenGroup >> <|> twain (char '(') (char ')') parenGroup >> >> chunks :: Parser [String] >> chunks = sepBy atom comma >> >> splitter = do >> cs <- chunks >> eof >> return cs >> >> goodS = "<*2>FOO<2,1>,<*3>(SigB<8:0:2>,BAR),<*2>Siga<2:0>,Sigb<8,7,6,5,0>" >> badS = "<*2)FOO<2,1>,<*3>(SigB<8:0:2>,BAR),<*2>Siga<2:0>,Sigb<8,7,6,5,0>" >> >> goodRes = parse splitter "splitter" goodS >> badRes = parse splitter "splitter" badS >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> >

1 0

Incremental XML parsing with namespaces?
by John Millikin 09 Jun '09

09 Jun '09

I'm trying to convert an XML document, incrementally, into a sequence of XML events. A simple example XML document: <doc xmlns="org:myproject:mainns" xmlns:x="org:myproject:otherns"> <title>Doc title</title> <x:ref>abc1234</x:ref> <html xmlns="http://www.w3.org/1999/xhtml"><body>Hello world!</body></html> </doc> The document can be very large, and arrives in chunks over a socket, so I need to be able to "feed" the text data into a parser and receive a list of XML events per chunk. Chunks can be separated in time by intervals of several minutes to an hour, so pausing processing for the arrival of the entire document is not an option. The type signatures would be something like: type Namespace = String type LocalName = String data Attribute = Attribute Namespace LocalName String data XMLEvent = EventElementBegin Namespace LocalName [Attribute] | EventElementEnd Namespace LocalName | EventContent String | EventError String parse :: Parser -> String -> (Parser, [XMLEvent]) I've looked at HaXml, HXT, and hexpat, and unless I'm missing something, none of them can achieve this: + HaXml and hexpat seem to disregard namespaces entirely -- that is, the root element is parsed to "doc" instead of ("org:myproject:mainns", "doc"), and the second child is "x:ref" instead of ("org:myproject:otherns", "ref"). Obviously, this makes parsing mixed-namespace documents effectively impossible. I found an email from 2004[1] that mentions a "filter" for namespace support in HaXml, but no further information and no working code. + HXT looks promising, because I see explicit mention in the documentation of recording and propagating namespaces. However, I can't figure out if there's an incremental mode. A page on the wiki[2] suggests that SAX is supported in the "html tag soup" parser, but I want incremental parsing of *valid* documents. If incremental parsing is supported by the standard "arrow" interface, I don't see any obvious way to pull events out into a list -- I'm a Haskell newbie, and still haven't quite figured out monads yet, let alone Arrows. Are there any libraries that support namespace-aware incremental parsing? [1] http://www.haskell.org/pipermail/haskell-cafe/2004-June/006252.html [2] http://www.haskell.org/haskellwiki/HXT/Conversion_of_Haskell_data_from/to_X…

5 8

FlexibleContexts and FlexibleInstances
by Niklas Broberg 09 Jun '09

09 Jun '09

Dear all, This post is partly a gripe about how poor the formal documentation for various GHC extensions is, partly a gripe about how GHC blurs the lines between syntactic and type-level issues as well as between various extensions, and partly a gripe about how the Haskell 98 report is sometimes similarly blurred where syntax is concerned (or not). All these things make the life of a poor parser implementor quite miserable at times. All in good jest of course, but with an edge of truth, especially regarding (lack of) formal documentation. The issue at hand which has caused my frustration is the FlexibleContexts [1] and FlexibleInstances [2] extensions, which lift restrictions imposed by Haskell 98 on the forms of contexts and instances that may be defined. Great extensions both of them - but what do they do, really really? The following toy program requires MultiParamTypeClasses OR FlexibleContexts in order to be accepted by GHC(i): > f :: (T a b) => a -> Int > f _ = 0 This of course assumes that we import the definition of T, we *must* have MultiParamTypeClasses enabled if we want to declare T. Both extensions thus enable classes with more than one argument to appear in contexts. Changing the program to > f :: (T a ()) => a -> Int > f _ = 0 i.e. changing the second argument to T to () instead, means we now *must* have FlexibleInstances, in order to allow the non-tyvar argument. This is nothing surprising, this is what FlexibleInstances are supposed to do. But the question is, is this a syntactic issue or a typing issue? In GHC proper this doesn't really matter much, as long as it is caught *somewhere* then all is dandy. GHC's parser lets everything pass, and it's the type checker that balks at this program. But for someone like me with *only* a parser, this is a question that needs a clear answer. Looking at the online report, the productions regarding contexts are context -> class | ( class1 , ... , classn ) (n>=0) class -> qtycls tyvar | qtycls ( tyvar atype1 ... atypen ) (n>=1) qtycls -> [ modid . ] tycls tycls -> conid tyvar -> varid Ok, so clearly the () is a syntactic extension enabled by FlexibleContexts, as it is not a tyvar nor a tyvar applied to a sequence of types. So this is something that a parser should handle. FlexibleContexts also enables similar parses of contexts in other places, for instance in class declarations, for which the Haskell 98 report says topdecl -> class [scontext =>] tycls tyvar [where cdecls] scontext -> simpleclass | ( simpleclass1 , ... , simpleclassn ) (n>=0) simpleclass -> qtycls tyvar The difference here is that the simpleclass doesn't allow the tyvar applied to a sequence of types bit. FlexibleContexts lifts that restriction too, so there should be no difference between the two kinds of contexts. So the new formal productions for flexible contexts should be something like fcontext -> fclass | ( fclass1 , ... , fclassn ) (n>=0) fclass -> qtycls type1 ... typen (n>=1) topdecl -> data [fcontext =>] simpletype = constrs [deriving] | newtype [fcontext =>] simpletype = newconstr [deriving] | class [fcontext =>] tycls tyvar [where cdecls] | instance [fcontext =>] qtycls inst [where idecls] gendecl -> vars :: [fcontext =>] type Does this seem correct? Now let's turn to FlexibleInstances, which similarly lifts restrictions, only to instance declarations instead of contexts. The Haskell 98 report says on instance declarations: topdecl -> instance [scontext =>] qtycls inst [where idecls] inst -> gtycon | ( gtycon tyvar1 ... tyvark ) (k>=0, tyvars distinct) | ( tyvar1 , ... , tyvark ) (k>=2, tyvars distinct) | [ tyvar ] | ( tyvar1 -> tyvar2 ) (tyvar1 and tyvar2 distinct) Note the re-appearance of scontext, which is the same as above. The instance head must be a type constructor, possibly applied to a number of type variables, or one of three built-in syntactic cases. This is where I consider the Haskell 98 report blurry - the fact that the tyvars must be distinct, is that truly a syntactic issue? It might be, it's certainly something that could be checked syntactically. But when you take into account that with the proper extensions, they no longer need to be distinct, at what level would we expect such a check to happen? My gut feeling is that this check for distinctness is something that a type checker might do better than a parser, though it's not clear cut by any means. But since I don't do any other kind of name resolution or checking in my parser even if it would be possible (e.g. multiple declarations of the same symbol), I would find it a bit anomalous to check this too. Turning on FlexibleInstances, we shouldn't need to follow any of the above restrictions on inst. In other words, the flexible production should simply be something like finst -> type Right? Now, FlexibleInstances *also* lifts the restriction on contexts, just like FlexibleContexts - but *only* for the contexts of instance declarations. This may seem like a reasonable thing, but it certainly gives me some headaches. It means I could not treat the contexts uniformly, but would need to have separate syntactic categories (or rather post-parse checks) that look different between instance contexts and other contexts (including class). So with FlexibleInstances on, there are *three* different kinds of contexts allowed: scontext for class declaration, fcontext for instance declarations, and context for all other uses of contexts (type signatures, data/newtype declarations). Just a small headache, since I already apparently needed two categories from Haskell 98, but still. I'm not sure I find it reasonable, that flexible instances are enabled just for instance declarations but not elsewhere, but I'm sure a lot of thought was given to that. If it was up to *me* though, I would leave the flexible contexts with FlexibleContexts entirely, which means you would have to use both flags if you wanted both in your instance declarations. Would that be a bad thing? Separation of concern seems desirable to me (and no, I'm not saying that just because it would be easier to implement in the parser)... At any rate, to make a long rant short: * Are my interpretations of the lifted restrictions by FlexibleContexts and FlexibleInstances correct? * Is it reasonable that the issue of checking that tyvars are distinct should not be considered syntactic? * Would it also be reasonable to make the separation of concern between FlexibleContexts and FlexibleInstances more clean? Thanks for reading, and please give me input! Cheers, /Niklas [1] http://www.haskell.org/ghc/docs/latest/html/users_guide/other-type-extensio… [2] http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensio…

1 0