December 2010 - Haskell-Cafe

Hexpat: Lazy I/O problem with huge input files
by Aleksandar Dimitrov 11 Dec '11

11 Dec '11

Hello Haskell Cafe, I really hope this is the right list for this sort of question. I've bugged the folks in #haskell, they say go here, so I'm turning to you. I want to use Hexpat to read in some humongous XML files (linguistic corpora,) since it's the only Haskell XML library (I could find) that takes ByteStrings as input. I stumbled on a problem when using one of the examples from the docs of Text.XML.Expat.Tree. The "cookbook recipe" there suggests *first* processing the data, and only then looking into the parser error to see if there has been an error. I understand this should prevent the parse tree from being fully evaluated before use. Unfortunately, that is not what happens on my system (ghc 6.12.1, if that's of importance.) This is the code from the docs, that I modified to read files: > import Text.XML.Expat.Tree > import System.Environment (getArgs) > import Control.Monad (liftM) > import qualified Data.ByteString.Lazy as C >· > -- This is the recommended way to handle errors in lazy parses > main = do > f <- liftM head getArgs >>= C.readFile > let (tree, mError) = parse defaultParseOptions f > print (tree :: UNode String) >· > -- Note: We check the error _after_ we have finished our processing > -- on the tree. > case mError of > Just err -> putStrLn $ "It failed : "++show err > Nothing -> putStrLn "Success!" Given a 42M test file, an invocation like this: % ghc --make -O2 Hexpat.hs % ./Hexpat input.xml > dump.xml will gobble up some 2Gigs of RAM (at least. I usually kill it before it starts thrashing the swap space, since that almost crashes my entire machine.) If I remove the last 3 lines: > import Text.XML.Expat.Tree > import System.Environment (getArgs) > import Control.Monad (liftM) > import qualified Data.ByteString.Lazy as C > > main = do > f <- liftM head getArgs >>= C.readFile > let (tree, mError) = parse defaultParseOptions f > print (tree :: UNode String) the same invocation and input file barely uses a megabyte or two of RAM and finishes really quickly. Why is that? Is this a mistake in the Hexpat docs, or am I doing something wrong? Lazy IO has always been a little bit of a mystery to me, and just when I thought I had it... Thanks for any help on the matter! Aleks

3 3

Re: [Haskell-cafe] Re: Functional dependencies and Peano numbers (and hoogle-bug?)
by Oscar Finnsson 04 May '11

04 May '11

Thanks for the great feedback. The bijective example was especially interesting. While reading "Fun with Type Functions" I notices GNum as an interesting alternative to the Num type class but I couldn't find any such package on hackagedb. Do anyone know if there is anything like GNum on hackagedb? On an unrelated note: I hoogled "to" (i.e. http://haskell.org/hoogle/?hoogle=to) and just got a blank page. Nothing. Nil (not even <html>...</html>). Is this a bug or a "feature"? :) The reason I hoogled it was because I'm searching for something like explicit casting found in many other languages, something similar to > class To f t where > to :: f -> t > > instance To a a where > to x = x > > instance (Real a, Fractional b) => To a b where > to = realToFrac > > instance (Read a) => To String (Maybe a) where > to = maybeRead -- not from cgi :) so I can write something like > ("23.2" `to`) :: Maybe Double or > ((42 :: Integer) `to`) :: Float Anyone made a module/package that solves this problem already? I cannot be the first that needs generic type safe conversion... . -- Oscar

3 2

ANNOUNCE: Multiplate 0.0.1
by roconnor＠theorem.ca 25 Mar '11

25 Mar '11

Multiplate is a lightweight generic library for mutually recursive data types that won't make Conor lose his lunch. Multiplate is an alternative extension of the Uniplate/Compos core design to support mutually recursive datatypes in a way that is as powerful as Compos, almost as easy to use as Uniplate, and more portable than both of them. Multiplate does not require you to rewrite your data type, does not require run-time reflection, does not require GADTs, and does not even require multi-parameter type classes. It only requires rank 3 polymorphism. <http://hackage.haskell.org/package/multiplate-0.0.1> A more detailed paper is forthcoming, but the library is available to try right now. -- Russell O'Connor <http://r6.ca/> ``All talk about `theft,''' the general counsel of the American Graphophone Company wrote, ``is the merest claptrap, for there exists no property in ideas musical, literary or artistic, except as defined by statute.''

2 1

Anyone recommend a VPS?
by Michael Snoyman 22 Mar '11

22 Mar '11

Hi all, I'm working with a client right now on deploying an app. I was wondering if anyone had some recommendations for a Haskell-friendly host. I'm inclined to go with a VPS for this setup, but if there's reliable shared hosting, that would do as well. This client is fairly price-sensitive, so I don't think anything past the $20/month range to start off with. The only other requirement for this project is PostgreSQL. As far as wants: * Linux is preferable * A server that isn't on everyone's spam list would be better. Of course, I can route through an outside e-mail provider, but local would be nicer. * Have room to grow. For now, this is a fairly small app, but the hope of course is for it to expand. Thanks in advance. Michael

12 15

Downloading Haskell repos from GitHub
by Gwern Branwen 21 Mar '11

21 Mar '11

Along the lines of http://blog.patch-tag.com/2010/03/13/mirroring-patch-tag/ for downloading all patch-tag.com repositories, I've begun to wonder how to download all Github repositories since more and more people seem to be using it. Nothing in http://develop.github.com/ seems especially useful for grabbing the git:// URLs of all repos by language - just by user. The only real list of repos by language seems to be gotten at via http://github.com/languages/Haskell/updated or http://github.com/languages/Haskell/created . (You might think http://github.com/languages/Haskell would be good, but no, it's just a few random repos by interest and not a full listing.) I looked at the HTML, and it looks possible to use tagsoup to get all 98 pages and then parse the entries to get the HTTP URLs of the repos, and then turn *that* into git:// URLs suitable for shelling out to 'git clone', but I can't help but wonder if maybe there's a better approach someone more familiar with Github would know. -- gwern

2 4

tplot and splot - analyst's swiss army knifes for visualizing log files
by Eugene Kirpichov 18 Mar '11

18 Mar '11

Hi cafe, I've published a large presentation about two Haskell-based tools of mine - tplot and splot. Their motto is "visualize system behavior from logs with a shell one-liner". Based on my experience, they usually seem to live up to this motto. http://www.slideshare.net/jkff/two-visualization-tools [attention attractor: the presentation has *really a lot* of pictures] hackage: http://hackage.haskell.org/package/timeplot http://hackage.haskell.org/package/splot other docs: http://www.haskell.org/haskellwiki/Timeplot http://www.haskell.org/haskellwiki/Splot -- Eugene Kirpichov Senior Software Engineer, Grid Dynamics http://www.griddynamics.com/

5 12

Infinite types should be optionally allowed
by Job Vranish 23 Feb '11

23 Feb '11

There are good reasons against allowing infinite types by default (mostly, that a lot of things type check that are normally not what we want). An old haskell cafe conversation on the topic is here: http://www.nabble.com/There%27s-nothing-wrong-with-infinite-types!-td771373… However, I think infinite types should be allowed, but only with an explicit type signature. In other words, don't allow infinite types to be inferred, but if they are specified, let them pass. I think it would be very hard to shoot yourself in the foot this way. Newtype is the standard solution to situations where you really need an infinite type, but in some cases this can be a big annoyance. Using newtype sacrifices data type abstraction and very useful type classes like Functor. You can use multiparameter type classes and functional dependencies to recover some of the lost abstraction, but then type checking becomes harder to reason about and the code gets way more ugly (If you doubt, let me know, I have some examples). Allowing infinite types would fix this. I'm imagining a syntax something like this: someFunctionThatCreatesInfiniteType :: a -> b | b = [(a, b)] Thoughts? Opinions? Am I missing anything obvious? - Job

3 10

Gedit Haskell mode plugin indentation
by yukkuri yu!yu!yu! 03 Feb '11

03 Feb '11

Here is my first try to write a Haskell mode layout indentation plugin for gedit - GNOME Text Editor: ftp://neverb.net/soft/mine/gedit_haskell_mode/haskell_indentation-latest.ta… Curent version: v0.4 To install the plugin 1) Create directory ~/.gnome2/gedit/plugins 2) Copy tarball/plugin/* contents to ~/.gnome2/gedit/plugins/ 3) In gedit go to Edit -> Preferences -> Plugins 4) Check the box left from "Haskell Indentation" plugin 5) (Possibly needed) Restart gedit.

1 4

Splittable random numbers
by Simon Peyton-Jones 01 Feb '11

01 Feb '11

Hi Cafe A while back there was a thread<http://www.mail-archive.com/haskell-cafe@haskell.org/msg79633.html> about a good implementation of a (pseudo) random number generator with a good "split" operation. There's lots of material on generators that generate a linear sequence of random numbers, but much less on how to generate a tree of random numbers, which is what Haskell's System.Random API requires. I happened to meet Burton Smith recently, who wrote some early papers about this stuff (eg "Pseudo random trees in Monte-Carlo<http://portal.acm.org/citation.cfm?id=1746034>"), so I asked him. His reply is below, along with some follow-up comments from his colleagues Tolga Acar and Gideon Yuval. The generator uses crypto functions, so it's probably more computationally expensive than common linear-sequence generators, but in exchange you get robust splitting. Does anyone feel like taking the idea and turning it into a Haskell library? (Or even a Haskell Wiki page?) I'm taking the liberty of cross-posting to the libraries list. Simon From: Burton Smith Sent: Tuesday, November 02, 2010 3:58 PM To: Simon Peyton-Jones Cc: Gideon Yuval (Gideon Yuval); Tolga Acar Subject: Random number generation With some help from Gideon and Tolga, I think the solution to the "arbitrary tree of random numbers problem" is as follows: The generator G is a pair comprising a crypto key G.k and an integer counter (the "message") G.c. The (next G) operation returns a pair: 1. a random integer r obtained by encrypting G.c with G.k, and 2. a new generator G' such that G'.k = G.k and G'.c = G.c + 1. The (split G) operation is similar, returning the same G', except that instead of returning a random integer r it returns a third generator G'' such that G''.k = r and G''.c = 0. A suitable block cipher system might be 128-bit AES (Rijndael). Unencumbered implementations exist in a variety of languages, and performance is pretty good and will improve dramatically as hardware support improves. I'd pick both crypto key size and the size of the result r to be 128 bits, and employ a 64 bit counter c. Other crypto options exist. From: Simon Peyton-Jones Sent: Wednesday, November 03, 2010 3:11 AM To: Burton Smith; Gideon Yuval (Gideon Yuval) Cc: Tolga Acar; Simon Peyton-Jones Subject: RE: Random number generation Burton, Gideon, Tolga Aha, that's interesting. I'd never seen a random number generator based on crypto, but it seems like an attractive idea. As I understand it, successive calls to 'next' will give you encrypt(0), encrypt(1), encrypt(2), encrypt(3),.... Is this standard? Does it have provably good randomness properties, (cycle length, what else?) like other RNGs? Or does it simply seem very plausible? Can I send it round to the Haskell mailing list, in the hope that someone will turn the idea into a library? (Ideally I'd like to make claims about the randomness properties in doing so, hence my qns above.) From: Gideon Yuval (Gideon Yuval) Sent: Wednesday, November 03, 2010 7:15 AM To: Simon Peyton-Jones; Burton Smith Cc: Tolga Acar Subject: RE: Random number generation As long as the key, and the non-counting part of the counter, are kept" secret", anyone who can distinguish these pseudorandoms from real random, in less than 2^128 steps, has a nice paper for crypto-2011 (this is known as "provable security") concerning a weakness in AES128. One exception: real randoms have a birthday paradox; the pseudorandoms suggested do not. If you care, you can: (1) Limit the counter to 2^32 steps (paradox has 2^-64 probability) or even 2^16 (2^-96), then rekey; or (2) XOR 2 such encrypted counters, with different keys; or (3) XOR 3 successive values for the same counter (just possibly cheaper; top-of-head idea). More hard-core: swap the position of key & message: encrypting a constant "secret" with 1,2,3,4.... Gives pseudorandoms with no birthday paradox. From: Tolga Acar Sent: 03 November 2010 15:50 To: Gideon Yuval (Gideon Yuval); Simon Peyton-Jones; Burton Smith Subject: RE: Random number generation Simon, The general idea is not really that new in the crypto area with constraints Gideon describes, of course. That is typically called a PRNG - Pseudo Random Number Generator, or in another parlance, Deterministic Random Bit Generators (DRBG). The DRBG constructions based on hash functions and block ciphers are even standardized in NIST publication SP800-90 (even though I may not recommend every one of them). As for the construction below, that is based on the AES block cipher, that essentially takes advantage of the PRP (Pseudo Random Permutation) property of the AES block cipher, as each block cipher ought to be. So, as Gideon outlines below, if you fix the key, the PRP gives you a random-looking (or, in other terms, indistinguishable from random) output that no one without the secret key and the "state" can generate or easily predict. Assuming an ideal cipher (and AES is a close approximation to it), the probability is believed to be the birthday paradox - no counterexample or a proof exists without assumptions; so we stick to the birthday bound. There ought to be papers on this somewhere. If not, that condensed information is spread across many papers and is part of the crypto folklore, I'd say. From: Burton Smith Sent: 03 November 2010 19:03 To: Simon Peyton-Jones Cc: Gideon Yuval (Gideon Yuval); Tolga Acar Subject: RE: Random number generation Just two points of further clarification: 1. All PRNGs used in the technical computing space fail the birthday paradox criterion (i.e. have full period), so we really need not worry about this. Also, there are other mitigating factors, e.g. suppose we are using the PRNG to generate pseudorandom residues mod n << 2^128; the paradox is happily present there. 2. The big innovation in this scheme is that the rekeying operation done by split creates a new generator with independence guaranteed by "provable security" in the sense Gideon mentioned - if someone can find something nonrandom in the correlation between G' and G'', say, then it amounts to a weakness in AES128 and is publishable. So it's yet another example of reducibility, common in our field: "if you can easily transform a known/famous hard problem P into this other problem Q, Q must be hard".

11 19

Re: [Haskell-cafe] ANNOUNCE: genprog-0.1
by Jan Snajder 31 Jan '11

31 Jan '11

(Moved from haskell(a)haskell.org) Hi Kenneth, I'm sorry for the very late reply. On Wed, 2010-12-08 at 10:01 +0100, Kenneth Hoste wrote: > Hi Jan, > > On 11/29/2010 12:55 PM, Jan Snajder wrote: > > Dear Haskellers, > > > > I am pleased to announce the release of genprog-0.1, a genetic > > programming library. > > > > (snip) > > Very interesting, and nice job on the code (elegant, well-structured, > well-documented, ...)! Thank you. This was my first shot at building a Haskell library and I'm flattered to receive such positive comments :-) > Genetic programming recently got my attention because one of the bots in > the Google AI contest was built using this technique (see > http://ai-contest.com/forums/viewtopic.php?f=17&t=1136) and it > performed really well (way better than my hand-crafted bot). Interesting, thanks for the link. > I have a bit of experience with genetic algorithms, on a practical and > pragmatic level. The field of genetic programming is something I hope to > look at and play with in the upcoming months (just for fun). > > I was kind of planning to implement my own genetic programming library > in Haskell as I became familiar with the field, but after diving into > your code it quickly became clear to me you've done a way better job > than I would have. > > I really like the example you provided for evolving an expression that > computes a specified integer value. I kept this example deliberatly simple so to make it clear how you can use the library. The example is actually a degenerated case of symbolic regression, in which you are given only a single instance to train at, rather than a set of instances. You can find much more interesting examples in Koza's book. > I plan to start playing with that > and improve the example (faster convergence to a perfect solution, and > also tweaking the current GP config to obtain smaller solutions). > > > A couple of questions (some fairly unrelated to Haskell): > > How hard would it be to extend the current version to support the > evolution of actual Haskell programs? As far as I can tell, the current > version has support for (simple?) self-defined expressions, but this > seems like a long way from supporting Haskell programs with > multi-argument functions that operate on lists, etc., even if you just > limit it to non-monadic Haskell98 code. Actually, I have no idea. :-) I don't know if there is a data structure that can represent an AST of a Haskell program. I guess there is, because I guess at some point a compiler like GHC has to maintain such a structure internally, but I never looked into this. At present, I am more than satisfied to be able to evolve custom-made data structures. Another issue with evolving arbitrary Haskell (or whatever) programs is the "closure property". When doing crossover, you have to ensure that what you get by exchanging two subtrees still is a valid program. In other words, if F is a set of (arbitrary arity) functional nodes and T is a set of terminal nodes, then, given a functional node F(x1,...,xi,...xn), you should be able to substitute for argument xi each element of F `union` T. Obviouslly, this will not work for programms in general and you would have to either introduce specialized crossover operations or treat the nodes differently depending on their types. In genprog, I have kept things simple and closure propery is ensured by allowing crossover to take place only at nodes that are of the same type as the root node. This is certainly a limitation, but still I think one can do interesting stuff with it. > > Have you considered playing with dynamic values for the various > parameters that steer the evolution, i.e. population size, > crossover/mutation probabilities, etc.? > One thing I've always wanted to try (but never really got to it) is e.g. > increasing the mutation probability as the evolution seems to be getting > stuck in a (local?) optimum. Also, shrinking the population size if > enough progress is being made could be interesting, to speed up the > evolutionary process. Are you aware of studies that do such a thing? Yes, definitely! Variable mutation probability is often used in genetic algorithms to improve the results. The idea is to have higher mutation probability in the beginning, so to encourage exploration, and then decrease the mutation probability as the evolution progresses, so to encourage exploitation. This increases the chances of not getting stuck in a local optima. But I didn't include this into genprog because I don't need variable mutation right now. I will probably do it in the next release. The most straightforward to do it, I guess, would be make the mutation prob. (and pop. size) a function of the evolution state. There are also other things that I plan to include in the next release. I hope I will find time to do it. Btw., mutation is actually rarely used in GP (unlike in GA). Koza, for example, used mutation in one example only. The thing is that, if you think of mutation as a replacement of a subexpression with a randomly generated subexpression, then you already can do this with crossover. Now, this only true for this default type of mutation. If you have a custom-defined mutation operator, one that changes a node depending on its value and/or type, than this cannot be accomplished by crossover anymore. Whether or not you need custom-defined mutations depends on the task at hand. E.g., if the expressions you're evolving feature values from a very large domain set, than a crossover operation alone will not get you enough genetic diversity. For this reason I've defined in genprog the mutation operation as a function of an expression that is being mutated. > Are you planning to actively maintain and extend this library? Are you > using it for research purposes, or did you hack this together just for > fun (if so, nice job!). What do you plan to use it for? Yes, I will maintain the library actively. I did this for fun, of course :-), and also for research, which I also do for fun :-) I am using the library for solving specific problems related to natural language processing. > Anyway, great job, I hope I'll find the time to play around with this. So do I. Please let me know if you have any suggestions on how to improve the library. If you do interesting stuff with it, please let us know what it is. Cheers, Jan

2 1