- Haskell-Cafe - Haskell.org

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 02 Aug '07

02 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 02 Aug '07

02 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 02 Aug '07

02 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

Indentation woes
by anon 01 Aug '07

01 Aug '07

Greetings, I wish to be able to indent my code like so: > longFunctionName various and sundry arguments > | guard1 = body1 > | guard2 = body2 > | ... > where declarations That is, with guards and where clauses indented to the same level as the function name. This seems like a perfectly reasonable indentation style to me. It also happens to be the preferred style in Clean, another layout-sensitive functional language. I believe it is not uncommon in ML dialects as well. So why is it that I'm not allowed to use it in Haskell?

16 25

Re: [Haskell] View patterns in GHC: Request for feedback
by Simon Marlow 01 Aug '07

01 Aug '07

Dan Licata wrote: > Simon PJ and I are implementing view patterns, a way of pattern matching > against abstract datatypes, in GHC. Our design is described here: > > http://hackage.haskell.org/trac/ghc/wiki/ViewPatterns > > If you have any comments or suggestions about this design, we'd love to > hear them. You can respond to this list (and we can take it to > haskell-cafe if the thread gets long) or, if you prefer, directly to me. At the risk of being a spoil-sport, I have a somewhat negative take on view patterns. Not because I think they're particularly bad, but because I don't think they're significantly useful enough to warrant adding to the language, at least if we also have pattern guards. All of the examples on the wiki page can be written in the same number of lines, sometimes with fewer characters, using pattern guards or some other existing Haskell idiom (e.g. the bit parsing example is much more nicely expressed using a bit-parsing monad). I believe adding yet another idiom will be detrimental: too much choice is bad. To my eyes, mixing bound and binding occurrences of variables in patterns in an arbitrarily nested way is sure to lead to confusion. The existing idioms all have a one-level deep notion of bound/binding scope, and in order to get more nesting you have to start naming things: this is good, IMO. Not that I think we should omit a language feature because it *could* be used to write obfuscated code; no, in this case I think nesting more than one level deep will *always* lead to obfuscated code. The use of the right-arrow is confusing, especially on the left of a case alternative or in a lambda expression. The main argument in favour of view patterns is: > it's possible that people would start routinely hiding the data > representation and exporting view functions instead, which would be an > excellent thing. My impression is that most of the time a data structure has a clever internal representation that you don't want to expose anyway. This is supported by the data structures we have in the base package, all these are abstract: Data.Set, Data.IntSet, Data.Map, Data.IntMap Data.Graph, Data.Sequence, Data.Bytestring, Data.Array, Data.HashTable, Data.Ratio(Rational) and most export view-like things (e.g. Data.Set.toList). The modules I found that export non-abstract types that should really be abstract: Data.Complex, Data.Tree So I don't think there's an overwhelming amount of stuff that would change if we had view patterns. In GHC itself most of our data structures are already abstract too. The View class is nice, even with just pattern guards. I'd be in favour of making it standard and actively encouraging its use. Cheers, Simon

17 43

Re[6]: [Haskell-cafe] i need wxHaskell compiled for ghc 6.6.1 on Windows
by Bulat Ziganshin 01 Aug '07

01 Aug '07

Hello shelarcy, Wednesday, August 1, 2007, 4:03:52 AM, you wrote: >> problems. the only question that remains - does this version supports >> unicode? > Yes. Current darcs repository version support only unicode > enabled version. great, it's all what i need. but i'm still curious about other features enabled when building this package. can i see config.gcc or build.cfg or setup.h or any other file that shows feature list? also it will be useful to include such file with the next builds of wxHaskell -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0