August 2007 - Haskell-Cafe

how to see operators precedence in GHCi
by Bulat Ziganshin 02 Aug '07

02 Aug '07

Hello , from http://community.livejournal.com/ru_declarative/54566.html Q: how to see operators precedence in GHCi? A: Prelude> let showParen = (undefined::[[[[()]]]]->()) Prelude> showParen $ 2+3*4 <interactive>:1:12: No instance for (Num [[[[()]]]]) arising from use of `+' at <interactive>:1:12 Probable fix: add an instance declaration for (Num [[[[()]]]]) In the second argument of `($)', namely `2 + (3 * 4)' In the definition of `it': it = showParen $ (2 + (3 * 4)) Prelude> -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

4 7

Exiting GLUT application
by Dave Tapley 02 Aug '07

02 Aug '07

Hi everyone, I have the following skeleton GLUT code: > import Graphics.UI.GLUT > main = do > getArgsAndInitialize > createWindow "" > mainLoop It loads into both hugs and ghci fine and when 'main' is evaluated an empty window opens as expected. However when closing the window (clicking the window manager's x button) both hugs and ghci exit with the window, as opposed to returning to the the 'Main>' prompt. I suspect I need some callback to exit the GUI cleanly? Cheers, Dave

3 4

Installing FreeGLUT
by Ronald Guida 02 Aug '07

02 Aug '07

Hi, I am trying to use freeglut with GHCi 6.6.1, and I'm stuck. I downloaded freeglut 2.4.0 and compiled it. I am on a Windows XP machine, and I found that freeglut compiled "out of the box" in MS Visual Studio.Net 2003. My difficulty is that GHCi is finding GLUT 2.2.1 and not freeglut. How do I get GHC and GHCi to recognize and use freeglut instead? Note: I'm using Windows XP; an upgrade to Linux is not an option. Thank you -- Ron

2 1

Some Haskell platformish questions
by David Pollak 02 Aug '07

02 Aug '07

Howdy, I'm considering building a desktop app using Haskell. The primary target for the app is Windows, but if it runs on Linux and Mac (Intel and PPC), that'd be a bonus. I've got a bunch of questions that hopefully folks can answer. Well, before I start, you might well be asking "Gee David, you're a Scala kind of guy... I mean, you're the primary contributor to lift... why not use Scala?" Well, I'm looking to build something that compiles down to native code and has a smaller download (and runtime) footprint than the JVM offers. I've come to love functional programming and am taking the current side project as an opportunity to learn Haskell. So... on to the questions: - Can GHC generate stand-alone executables with all the dependencies linked in such that I can distribute the single file without worrying about including a bunch of DLLs/SOs? The answer seems to be yes, but I wanted to confirm. - How much of a distribution footprint is the Haskell runtime? If I have a "Hello World" app, roughly how big will the EXE be (if one includes the JRE in the runtime, a Java/Scala program has a minimum footprint of 20M... that's big.) - Same goes for the runtime... I've looked at the stats on the Language Shootout home page and these look encouraging, but I wanted to see if the reasonable footprint is a reality. - How real/solid/stable is the wxHaskell widgets package? Is it being well maintained? Is there (okay... this is pie in the sky) an GUI Builder for it? - How are the Windows/COM bindings in Haskell... would it be possible to, for example, embed an IE Browser COM control in a a wxHaskell window? - I found a package to do HTTP requests in Haskell but it does not seem to support HTTPS. Is there an HTTPS client package for Haskell? - How are Strings internally represented? Are they single byte or multi-byte characters? How easy it is to translate to/from internal representation to UTF-8? - How's the XML support? Will the XML parser handle non-Latin characters and properly encode stuff? Does XML get parsed down into easily mappable/filterable collections? - Is there support for SHA256 (I saw an SSLeay package which had support for a lot of stuff, but not SHA256)? - I understand that Haskell has "a better approach" to parallelizing tasks, but I have not seen much about the actual manifestation of this... would someone be so kind as to give me a pointer? - On a related note, I have become a fan (via Scala) of Erlang-style Actors and asynchronous message passing. Are there any similar packages for Haskell? - I tend to do most of my coding in either Emacs or Eclipse... how's the Haskell support in either? Is there a preferred editor (I don't mean to start any wars here... :-) - Are there any production Haskell-based desktop apps of note? Anyway... sorry for the long list of questions. I look forward to hearing from you all and learning more about Haskell. Thanks, David -- lift, the fast, powerful, easy web framework http://liftweb.net

6 12

Cartesian product of a Set
by Andy Gimblett 02 Aug '07

02 Aug '07

Hi all, Is this a reasonable way to compute the cartesian product of a Set? > cartesian :: Ord a => S.Set a -> S.Set (a,a) > cartesian x = S.fromList [(i,j) | i <- xs, j <- xs] > where xs = S.toList x It's a fairly "obvious" way to do it, but I wondered if there were any hidden gotchas. I'm particularly concerned by toList (O(n)) fromList (O(n log n)) - but for other reasons I'd really like to be using Set rather than List for this (I think). Many thanks for any thoughts, -Andy -- Andy Gimblett Computer Science Department University of Wales Swansea http://www.cs.swan.ac.uk/~csandy/

5 7

monads and groups -- instead of loops
by Greg Meredith 02 Aug '07

02 Aug '07

Haskellians, Though the actual metaphor in the monads-via-loops doesn't seem to fly with this audience, i like the spirit of the communication and the implicit challenge: find a pithy slogan that -- for a particular audience, like imperative programmers -- serves to uncover the essence of the notion. i can't really address that audience as my first real exposure to programming was scheme and i moved into concurrency and reflection after that and only ever used imperative languages as means to an end. That said, i think i found another metaphor that summarizes the notion for me. In the same way that the group axioms organize notions of symmetry, including addition, multiplication, reflections, translations, rotations, ... the monad(ic axioms) organize(s) notions of snapshot (return) and update (bind), including state, i/o, control, .... In short group : symmetry :: monad : update Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

6 7

Re: monads and groups -- instead of loops
by Greg Meredith 02 Aug '07

02 Aug '07

Arie, Thanks for your thoughtful reply. Comments in-lined. Best wishes, --greg Date: Thu, 2 Aug 2007 03:06:51 +0200 (CEST) > From: "Arie Peterson" <ariep(a)xs4all.nl> > Subject: Re: [Haskell-cafe] Re: monads and groups -- instead of loops > To: haskell-cafe(a)haskell.org > Message-ID: < 5043.213.84.177.94.1186016811.squirrel(a)webmail.xs4all.nl> > Content-Type: text/plain;charset=iso-8859-1 > > Math alert: mild category theory. > > Greg Meredith wrote: > > > But, along these lines i have been wondering for a while... the monad > laws > > present an alternative categorification of monoid. At least it's > > alternative to monoidoid. > > I wouldn't call monads categorifications of monoids, strictly speaking. > A monad is a monoid object in a category of endofunctors (which is a > monoidal category under composition). Sorry, i was being as fast and loose with the term as the rest of the communities concerned with 'categorification' seem to be. What do you mean by a 'monoidoid'? I only know it as a perverse synonym of > 'category' :-). Indeed. > In the spirit of this thought, does anyone know of an > > expansion of the monad axioms to include an inverse action? Here, i am > > following an analogy > > > > monoidoid : monad :: groupoid : ??? > > First of all, I don't actually know the answer. > > The canonical option would be a group object in the endofunctor category > (let's call the latter C). This does not make sense, however: in order to > formulate the axiom for the inverse, we would need the monoidal structure > of C (composition of functors) to behave more like a categorical product > (to wit, it should have diagonal morphisms diag :: m a -> m (m a) ). It seems to me that there are two basic possibilities, here. One is that the ambient categories over which one formulates computational monads are almost always some type of Linear-Cartesian situation. So, you can possibly exploit the additional structure there. That's certainly been the general flavor of the situation that motivates me. Otherwise, you can go the route of trying to excavate structure that might give meaningful interpretations. This has appeal in that it is more general and might actually uncover something, but as you observe it's not immediate. i haven't wrestled with the idea in anger, yet, because i thought it such an obvious thing to try that someone would have already done the work and was hoping just to get a reference. Your note suggests that it might be worth digging a little. i wonder... does a Hopf algebra-like structure do the job? Maybe there is a way to get it to work, though. After all, what we (in FP) > call a commutative monad, is not commutative in the usual mathematical > sense (again, C does not have enough structure to even talk about > commutativity). > > > > My intuition tells me this could be quite generally useful to computing > in > > situation where boxing and updating have natural (or yet to be > discovered) > > candidates for undo operations. i'm given to understand reversible > > computing > > might be a good thing to be thinking about if QC ever gets real... ;-) > > If this structure is to be grouplike, the inverse of an action should be > not only a post-inverse, but also a pre-inverse. Is that would you have in > mind? > > > (If I'm not making sense, please shout (or ignore ;-) ).) > > > Greetings, > > Arie > -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

1 0

Parser inversions [Was: CC-delcont-0.1...]
by oleg＠pobox.com 01 Aug '07

01 Aug '07

Dan Doel wrote about `inverting' a parser -- first, a pure parser consuming a string and later a parser written in a monadic style and consuming a monadic list: data MList' m a = MNil | MCons a (MList m a) type MList m a = m (MList' m a) The second attempt proved fully successful: > So, success! Tokens are printed out as soon as the lexer is able to recognize > them, properly interleaved with other IO side effects, and resuming from an > intermediate parse does not cause duplication of output. Indeed, one may say `inverting' a parser is differentiating it. That is, we wish parse incrementally, to observe semantic actions as they are being performed. If the parser is a pure function then the only possible observation is that of its result given a specific input. To differentiate such a parser we feed it progressively longer inputs and observe differences in the output, the stream of parsed tokens. The first attempt followed this `classical calculus' recipe and wasn't fully successful, even though the parser used in that attempt was a good, _continuous_ parser. The parser for conventional arithmetic expressions such as "1+2" can generate parsed token 1 after it saw the first two characters, no matter what follows further in the input stream. Giving longer input to the parser will _progressively_ cause longer output. Alas, there are _discontinuous_ parsers, such XML DOM parsers. Let's consider the input <root><a>text</a><b/></root> Until a pure parser sees </root> (that is, the entire input document) it produces nothing at all (except errors that the XML document is ill-formed). Indeed, ill-formed documents have no Infoset (no `meaning') and hence DOM parsers must not return any parsed data for incomplete documents. As in calculus, differentiating such discontinuous functions is not helpful. Now, if the parser is monadic then effects and their sequence become observable too. We can truly observe the sequence of executed semantic actions. These actions are executed incrementally, as the parser recognized a part of input to which a semantic action applies. Delimited continuations, as a `scriptable debugger', let us observe the execution of the parser step by step. One way to differentiate is to embed `breakpoints' in the input stream, in the get-char-like routine the parser uses to obtain next piece of input. Such routines are typically under user control, who can embed breakpoints, aka shift. The MList data structure is a clever way to `hide' get-char routines out of sight. Another way to observe the sequence of actions is to embed breakpoints into semantic actions themselves. In many parsers, the grammar with semantic actions is provided by users and thus again under their control. This approach can `invert' a DOM XML parser into a streaming, pull-like SAX XML parser, provided the DOM parser exports suitable callbacks: http://okmij.org/ftp/Scheme/xml.html#SSAX-pull > So, that wasn't really that hard to hack up. However, I should mention > that it wasn't trivial, either. When converting list functions to > MList functions, you have to be very careful not to perform side > effects twice. Indeed: the major complexity of LogicT was making sure effects are not done twice. > ... many recursive data structures can be expressed as the fixed-point > of shape functors. The kicker is, you can get the monadic version for > free. Indeed, open recursion at the term level lets us transparently interpose, for example, memoization. The benefits of coding recursive data types with explicit open recursion have been described in Two-Level Types and Parameterized Modules Time Sheard and Emir Pasalic JFP v14 (5):547-587, Sept. 2004 http://web.cecs.pdx.edu/~sheard/papers/JfpPearl.ps In particular, please see the Section 8, History, near the end of the paper. Thank you indeed for packaging CC monad and LogicT!

1 0

Backpatching
by Thomas Conway 01 Aug '07

01 Aug '07

Hi All, One of the things I've been working on lately is some ASN.1 stuff.One of the first things I wrote in Haskell was an ASN.1 parser. It only worked for a subset, and I'm revisiting it to make it handle a larger subset. One of the things that gets messy is that in lots of places you can put either a thing or a reference to a thing (i.e. the name of a thing defined elsewhere). For example, consider the production: NamedNumber ::= identifier "(" SignedNumber ")" | identifier "(" DefinedValue ")" If we ignore the second alternative, the natural translation into a Parsec parser would look like: namedNumber = do name <- identifier val <- parens signedNumber return (name, val) Now to handle the second alternative is easy enough: namedNumber = do name <- identifier val <- parens (fmap Left signedNumber <|> fmap Right definedValue) return (name, val) however because names can be used before they are defined the result typegoes from being type NamedNumber = (Name,Integer) to type NamedNumber = (Name,Either Integer Name) Nothing too terrible so far. The messiness comes in when you considerthe number of places that you have to replace a type 't' with (Either t Name). I'd really like to avoid having to do this. If I were using Prolog, I could finesse the problem by introducing afree variable and filling it in when I come across the definition[*]. Logic variable backpatching. :-) So one possibility would be to return a closure: ... return $ \bindings -> (name,resolve val bindings) resolve :: (Either t Name) -> Map Name t -> t or something like that. Then when you get to the end, you apply the bindings and voila, out pops the simple type. I'm not sure this will work quite as well as it sounds. This sounds like a common problem type. Is there a well known solution to this sort of problem? cheers, Tom [*] And then at the end use var/1 to look for undefined names. Urk. Actually, if I were using Prolog in the way most Prolog programmers use it, I wouldn't be thinking about the types. -- Dr Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

6 6

How can I optimize pattern matching on views?
by Ryan Ingram 01 Aug '07

01 Aug '07

Background: I participated in this year's ICFP programming contest<http://www.icfpcontest.org>and our team did quite well, coming in 37th. Our simulator (in somewhat naive C++ with a good algorithm) took about 45 seconds to run the original problem, and afterwards one of my coworkers took the same algorithm and optimized it to run in about 6-10 seconds. The rest of the email will have minor spoilers, so skip it if you want to work on the problem yourself. I'm using that problem as a good testcase for learning to write high-performance Haskell. I'm using the same data structure and basic algorithm as the C++ version, but I'm having problems getting the performance where I think it should be. The relevant parts of the code: > import qualified Data.ByteString.Base as B > import qualified Data.ByteString.Char8 as BC > > type DNABlock = B.ByteString > type DNA = [DNABlock] I represent the DNA string as a simplified rope<http://en.wikipedia.org/wiki/Rope_(computer_science)>that supports fast reading from the front & prepending. To access this in a reasonable fashion, I used a view to let me treat the data as a string. Here's a sample bit of code using that view: > matchConsts :: Int -> DNA -> (Int, DNA) > matchConsts len dna | len `seq` dna `seq` False = undefined -- force strictness > matchConsts len dna = case dnaView dna of > ('F':_) -> matchConsts (len+1) (dropDna 1 dna) > ('C':_) -> matchConsts (len+1) (dropDna 1 dna) > ('P':_) -> matchConsts (len+1) (dropDna 1 dna) > ('I':'C':_) -> matchConsts (len+2) (dropDna 2 dna) > _ -> (len, dna) > dropDna :: Int -> DNA -> DNA > dropDna n dna | n `seq` dna `seq` False = undefined -- force strictness > dropDna _ [] = [] > dropDna 0 dna = d > dropDna n (d:ds) > | n >= BC.length d = dropDna (n - BC.length d) ds > | otherwise = B.unsafeDrop n d : ds > {-# INLINE dropDna #-} Profiling showed that almost all of my time & allocations were spent in my view function: > dnaView :: DNA -> String > -- dnaView d = foldr (++) [] (map BC.unpack d) > -- This was ridiculously slow for some reason that I don't entirely understand > dnaView [] = [] > dnaView (d:ds) > | BC.null d = dnaView ds > | otherwise = (w2c $ B.unsafeHead d) : dnaView (B.unsafeTail d : ds) > {-# INLINE dnaView #-} The question I have for you, the haskell-cafe-reading-audience, is how can I get GHC to do smart code-gen for this? I want "case dnaView dna of ..." to not allocate and instead fuse the list generation with the pattern-match. -- ryan

1 0