December 2009 - Haskell-Cafe

Generating AST using Parsec
by CK Kashyap 27 Dec '09

27 Dec '09

Hi All, I recently came across the paper titled "Monadic Parser Combinators" - After going through it a few times, I think I am beginning to understand monads. However, the parser developed in the paper does not generate an AST - I feel, I'd grasp the whole thing a lot better if I could go over a sample that generates an AST from a simple expression (or even a standard language such as C or Java) ... Can someone please point me to a sample that generates AST - preferably with the simple parser combinator given in the paper. Regards, Kashyap

4 3

Continuable and serializable parsers.
by Serguey Zefirov 27 Dec '09

27 Dec '09

A pair of problems: 1) How to write a parser that could be restarted? Like, it will be represented by a function that returns something along the lines data ParseStepResult input result = Success (Maybe (input -> ParseStepResult input result)) (Maybe result) | Failure (ie, parsers using stream combinators like Fudgets have that property) ie, either a continuation of parsing process and result or failure flag. 2) How to write parser like one above that could be saved into database? data ParserCont input result = ... deriving (Show, Read) data ParseStepResult input result = Success (Maybe (ParserCont input result)) (Maybe result) | Failure I could imagine that it is possible using parser generator like Happy. Is it possible to get right using parsing combinators library?

5 13

Lazy evaluation/functions
by michael rice 27 Dec '09

27 Dec '09

I've seen the terms "lazy evaluation" and "lazy function." Is this just lazy language or are both these terms valid? Michael

3 2

Deconstruction
by haskell＠kudling.de 26 Dec '09

26 Dec '09

Hi, while this works: data Foo a = Foo a unwrapFoo :: Foo a -> a unwrapFoo (Foo x) = x this: {-# LANGUAGE ExistentialQuantification #-} class BarLike a where doSomething :: a -> Double data Bar = forall a. BarLike a => Bar a unwrapBar :: Bar -> a unwrapBar (Bar x) = x gives me: Couldn't match expected type `a' against inferred type `a1' `a' is a rigid type variable bound by the type signature for `unwrapBar' at test.hs:8:20 `a1' is a rigid type variable bound by the constructor `Bar' at test.hs:9:11 In the expression: x In the definition of `unwrapBar': unwrapBar (Bar x) = x How can i deconstruct the enclosed value of type a? Thanks, Lenny

3 5

Does the TMVar and TChan really obey STM rules?
by Andrey Sisoyev 26 Dec '09

26 Dec '09

Hi everyone, >isEmptyTMVar :: TMVar a -> STM Bool Source > >Check whether a given TMVar is empty. > >Notice that the boolean value returned is just a snapshot >of the state of the TMVar. By the time you get to react on its result, >the TMVar may have been filled (or emptied) - so be extremely careful >when using this operation. Use tryTakeTMVar instead if possible. When I read this in the haddock to Control.Concurrent.STM.TMVar, I started to suspect that the behavior of TMVar and TChan might be worse than I imagined. Few questions on TMVar and TChan: (1) If 2 threads are sleeping-waiting for the output of TChan, and it gets filled, do they both wakeup, or just one? (2) Similar question about reading/writing TMVar. (3) If a thread is sleeping-waiting for the output of TChan, but transaction wants to restart due to the change in any of touched TVar, then does the thread wakeup and restart the transaction? (4) Similar question about TMVar. Also, if there is some paper on this, please, give me a link on it. Please help, Andrey -- View this message in context: http://old.nabble.com/Does-the-TMVar-and-TChan-really-obey-STM-rules--tp269… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 3

Haskell type system and Barendregt's Lambda Cube classification
by Vladimir Ivanov 26 Dec '09

26 Dec '09

Dear All, Recently, I've been playing with self-application and fixed-point combinators definition in Haskell. It is possible to type them in Haskell using recursive types. I took Y & U combinators: > newtype Rec a = In { out :: Rec a -> a } > u :: Rec a -> a > u x = out x x > y :: (a -> a) -> a > y f = let uf = f . u in uf (In uf) Recursive types are part of System F-omega, which corresponds to lambda omega in Barendregt's Lambda Cube. For all type systems in Lambda Cube it is proven that they are strongly normalizing. But using "y" I can easily construct a term even without a normal form. So, I got a contradition and conclude that type system implementation in Haskell contains something, that is absent from System F-omega. My question is: what's particular feature in Haskell type system, that breaks strong normalization property? Or am I totally wrong classifying it in terms of Lambda Cube? Best regards, Vladimir Ivanov

2 2

Fwd: [Haskell-cafe] Deconstruction
by Alberto G. Corona 26 Dec '09

26 Dec '09

Cast uses unsafeCoerce. but well, it´s more elegant ;) 2009/12/26 Miguel Mitrofanov <miguelimo38(a)yandex.ru> > On 26 Dec 2009, at 12:45, Alberto G. Corona wrote: > > You can also make use of Typeable and unsafeCoerce (Data.Dynamic style) >> >> >> data Bar = forall a. (BarLike a, Typeable a) => Bar a >> >> unwrapBar :: Bar -> a >> unwrapBar (Bar x) = case typeof x== typeof a of >> True -> unsafeCoerce x >> False -> error $ "casting error for >> type: "++ typeOf a >> > > That's gross. Don't use unsafe functions unless you really need one. > > > data Bar = forall a. (BarLike a, Typeable a) => Bar a > unwrapBar :: Typeable a => Bar -> a > unwrapBar (Bar x) = fromMaybe (error $ "casting error for type: " ++ show > (typeOf x)) $ cast x > > > > > >> >> >> 2009/12/26 Miguel Mitrofanov <miguelimo38(a)yandex.ru> >> >> On 26 Dec 2009, at 11:58, haskell(a)kudling.de wrote: >> >> class BarLike a where >> doSomething :: a -> Double >> >> data Bar = forall a. BarLike a => Bar a >> >> unwrapBar :: Bar -> a >> unwrapBar (Bar x) = x >> >> How can i deconstruct the enclosed value of type a? >> >> You can't write a function with a type that mentions existentially >> quantified "a". Period. >> >> But you can deconstruct the enclosed value temporarily: >> >> getSomething :: Bar -> Double >> getSomething b = >> case b of >> Bar a -> doSomething a >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> >> >

1 0

ANNOUNCE: graphviz-2999.8.0.0
by Ivan Lazar Miljenovic 26 Dec '09

26 Dec '09

I am pleased to announce the latest release of my graphviz [1] library, which provides bindings and helper functions for use with the Graphviz [2] suite of graph visualisation programs. [1] http://hackage.haskell.org/package/graphviz [2] http://www.graphviz.org/ For the most part, this release has a compatible API with the 2999.7.0.0 version; the only exceptions to this are the runGraphviz and runGraphvizCommand functions in Data.GraphViz.Commands; I released after the last release that it might be useful to have these return the filenames of the files created rather than just indicating success, especially when using addExtension (from the same module) to add the correct extension to a provided filename. The rest of the changes to this release are: * Added support for generalised DotGraphs; this optional representation removes the restriction of ordering of Dot statements. This allows for greater flexibility of how to specify Dot code. As an offshoot from this, most relevant functions now utilise a new DotRepr class that work with both DotGraphs and the new GDotGraphs; this shouldn't affect any code already in use. * With the prompting of Noam Lewis, the augmentation functions have been revamped in two ways: - Now contains support for multiple edges. - The ability to perform "manual" augmentation if greater control is desired. * Add a preview function to quickly render and visualise an FGL graph using the Xlib canvas. * Added a pseudo-inverse of the FGL -> Dot functions (a graph is created, but the original node and edge labels are unrecoverable). * The Printing and Parsing modules have been moved (from Data.GraphViz.Types to Data.GraphViz). In the near future, this library is also likely to contain support for record shapes for graph nodes thanks to Minh Thu. If you want/require any additional features in graphviz, you too can do what countless (well, OK, not actually countless per-se) people like Noam and Thu have done: bug me to do it or send me a patch! ;-) (I hope that I don't have to make yet another release soon fixing an obvious flaw as soon as I actually start using this release myself...) -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

1 0

Re: [Haskell-cafe] Performance of functional priority queues
by Louis Wasserman 25 Dec '09

25 Dec '09

>> One of the correspondents in that thread claims that it is >> provably impossible to have an efficient priority queue implementation >> without mutability. I think he's cuckoo. But I'd like to have some >> numbers to back me up. He is cuckoo, and here's proof: http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf <http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf>This demonstrates a functional priority queue that performs every desired operation in asymptotically optimal time. Granting that its constant factor could be significantly improved, realize that there are more complicated functional data structures with similar asymptotic guarantees. (Observation: I'm pretty sure that the Fibonacci heap is actually surprisingly functional.) Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

2 1

Why does HXT use Arrows?
by Gregory Crosswhite 25 Dec '09

25 Dec '09

Something I have been wondering for a while is: Why is HXT built on arrows, rather than monads? I understand that arrows are a generalization of monads, but they also add extra complexity that is often unnecessary. Furthermore, as I understand it they only give you additional power when your arrow cannot implement ArrowApply, since otherwise your arrow is equivalent to a monad anyway, and it looks like the result of parsing an XML document gets you an arrow which implements ArrowApply. Is there some circumstance I am missing where the fact that HXT uses arrows rather than monads lets one do something that one couldn't have done with monads? Cheers, Greg

4 3