November 2009 - Haskell-Cafe

can there be (hash-table using) O(n) version of this (I think currently) n log n algo?
by Thomas Hartman 09 Dec '09

09 Dec '09

The code below is, I think, n log n, a few seconds on a million + element list. I wonder if it's possible to get this down to O(N) by using a hashtable implemementation, or other better data structure. Further, is there a hashtable implementation for haskell that doesn't live in IO? Maybe in ST or something? import Data.HashTable import qualified Data.Set as S import Data.List (foldl') testdata = [1,4,8,9,20,11,20,14,2,15] ++ [1..(10^6)] wantedsum = 29 -- set data structure -- findsums locates pairs of integers in a list that add up to a wanted sum. findsums :: [Int] -> Int -> S.Set (Int,Int) findsums xs wanted = snd . foldl' f (S.empty,S.empty) $ xs where f (candidates,successes) next = if S.member (wanted-next) candidates then (candidates, S.insert (next,wanted-next) successes) else (S.insert next candidates,successes) -- hashtable data structure -- result: t -- fromList [(15,14),(16,13),(17,12),(18,11),(19,10),(20,9),(21,8),(22,7),(23,6),(24,5),(25,4),(26,3),(27,2),(28,1)] -- probably O(n log n) complexity since using tree based Data.Set (a few seconds on million+ element list) t = findsums testdata wantedsum

9 10

ANNOUNCE: dbus-core 0.6 and dbus-client 0.2
by John Millikin 08 Dec '09

08 Dec '09

This is the second public release of my D-Bus implementation. dbus-core is an implementation of the D-Bus protocol, and dbus-client is a set of wrappers and utility computations to simplify writing basic clients. Interesting changes to dbus-core ================================ * Performance improvements: sending and receiving large structures should now be significantly faster. My thanks and appreciation go to Bryan O'Sullivan, whose excellent Criterion library made benchmarking the serialisation code much easier than it had any right to be. * Better support for byte arrays: byte strings (strict and lazy) are now directly supported types, with special cases to avoid most conversion overhead. * Implemented the TCP/IP transport, though it's untested because I can't figure out how to make the server listen on a socket. If anybody cares about remote D-Bus, and this doesn't work, drop me a mail with your configuration and I'll find out why. * Added module to represent "match rules", required for full signal support. * Added module for name reservations -- this is really just moving the bulk of the code from dbus-client into dbus-core, where it belongs. * Fixed possible concurrency issue when receiving messages from a connection in multiple threads. This is still a really bad idea, and it will never work correctly, but at least now it won't corrupt the connection state. Interesting changes to dbus-client ================================== * Fixed dumb signature to mkClient (thanks, Max). Its purpose should now be more obvious. * Shifted around some of the method call APIs -- it's now possible to send method calls without a proxy. * Uses the new MatchRule work to fully support receiving signals. Documentation ============= PDFs of the source; these are the most useful and complete documentation currently available: https://dl.dropbox.com/u/1947532/dbus-core_0.6.pdf https://dl.dropbox.com/u/1947532/dbus-client_0.2.pdf An API listing is also available, good for a quick overview: https://dl.dropbox.com/u/1947532/dbus-core_0.6/index.html https://dl.dropbox.com/u/1947532/dbus-client_0.2/index.html Hackage is currently experiencing some dependency conflicts with the "bytestring" library[1], so it's not generating its own documentation. I'll keep the dropbox pages up until Hackage is in a more usable state. Downloads ========= Available from the usual places: http://hackage.haskell.org/packages/archive/dbus-core/0.6/dbus-core-0.6.tar… http://hackage.haskell.org/packages/archive/dbus-client/0.2/dbus-client-0.2… [1] "binary" uses bytestring-0.9.1.4, "text" uses bytestring-0.9.1.5, kaboom

2 3

Re: [Haskell-cafe] Interactive chatbot
by Ben Millwood 08 Dec '09

08 Dec '09

Oops, I clicked "reply" instead of "reply to all". Duplicating the message below. I suppose this means someone is going to get two copies of this. Sorry someone! On Thu, Nov 5, 2009 at 12:56 AM, Ben Millwood <haskell(a)benmachine.co.uk> wrote: > On Wed, Nov 4, 2009 at 10:21 PM, Torsten Otto <t-otto-news(a)gmx.de> wrote: >> >> When we read the user's input through >>> t <- getLine >> it is not possible to delete typos before hitting enter and thereby sending >> the input off to the system (at least in OS X, bash). I didn't find that >> terribly problematic, but of course it is a bit of a show stopper from their >> point of view. >> > > As people have said it's worth checking what buffering settings you > are using (especially note that ghci changes some interesting settings > in relation to how input is handled, and compiled code may behave > differently), but it might also be worth checking the terminal > application's preferences to see if there are settings related to the > interpretation of the backspace key that you need to twiddle one way > or the other. In particular, if you are finding that pressing delete > makes ^H appear on the input line instead of deleting things, or if > pressing ctrl-H deletes stuff where the delete key fails to do so, it > might be a problem with your terminal rather than with your program. > This is only based on what I vaguely remember from faffing with the > Mac Terminal application some time ago when it wouldn't co-operate > with screen, but it may be worth a look. > > yours, > Ben Millwood >

2 1

Re: [Haskell-cafe] Re: [Haskell] ANNOUNCE: control-monad-exception 0.5 with monadic call traces
by klondike 07 Dec '09

07 Dec '09

Luke Palmer escribió: > On Fri, Nov 6, 2009 at 6:54 PM, klondike > <klondikehaskellcafe(a)xiscosoft.es> wrote: > >> Henning Thielemann escribió: >> >>> That's what I meant with my post: Programming errors (like "head []") >>> are not handled by control-monad-exception. As far as I understand, >>> control-monad-exception makes _exceptions_ explicit in the type >>> signatures, not programming errors. Why and how would you make >>> possible programming errors explicit in the type? But for exceptions >>> (e.g. "file could not be found") a detailed stack trace is not of much >>> use. >>> >> I think you have overlooked a few things. First, not every developer >> knows each one of the lines in the code well enough as to see where a >> exception comes from, specially when you are not the author of that code. >> >> Of course, that wouldn't mind so much unless you see another thing, if >> we don't know which exceptions can be launched by a operation then you >> will get it on the upper frame and rendered unable to solve it. Use >> typed exceptions (as this library intends to) you may say. Ok, now we >> have another problem, the strange habit of coders to keep the exceptions >> they don't know/can't treat going up and up and up, until then usually >> hit the top frame and you are screwed. You can check some Java code (to >> see an example on how this happens) as some of these exceptional >> conditions are put on the method's signature. >> > > You sound like you are expecting something that works exactly like the > imperative exception handling mechanisms you are used to, and are not > willing to accept anything else. > No, I sound like I am expecting programmers comming from the imperative world to do ugly things, maybe because I once was one. > This "strange habit" of programmers is simply bad practice, and leads > to just as brittle code as no exception handling, except that you get > inexplicable error message boxes with OK buttons instead of crashes. > You might as well just put the whole program in a catch block in IO > and bail with something noncomittal. > Now comes the time when I have to show you that not every exception could be handled, IE a file not found exception when looking for the config file can be fatal and force the program to stop. But what if this is on a library? How do you suggest that the programmer knows that the File Not Found exception is due to the lack of that config file, specially when the code is badly (or not) documented. > IMO, Haskell's typed exceptions (via eg. explicit-exception) *are* the > way to go. They keep the number of exceptional conditions that can > occur in a body of code small -- if some code has many exceptional > conditions, it forces you to *compose* them somehow, to come up with a > more precise idea of what your code is doing and how it can fail. > Yeah, the thing comes when you get the same kind of exceptions from different places, you need a way to tell them appart. > If you are just blindly passing exceptions up from the code below, the > interface to your code is getting more and more complex. With typed > exceptions, the types are reflecting the complexity of the interface > (which is precisely the purpose of types). > Well, it's not like blindly pass exceptions up but more like passing exceptions I don't know how to handle up.

3 3

Hoogle Down
by Elliot Wolk 07 Dec '09

07 Dec '09

hello! im not sure that this is the correct mailing list for saying so, and also whether or not today's down-ness is just scheduled maintenance, but hoogle appears to be down again. sorry if this is known/redundant/not the right place! thanks, elliot

2 1

ANNOUNCE: Blueprint 0.1 -- PREVIEW
by Gregory Crosswhite 06 Dec '09

06 Dec '09

I earlier posted to this list asking for help in getting Cabal to play with a Fortran compiler. When it turned out that there was no answer to this, I of course did the obvious thing --- I wrote my own build system. :-) It already boasts the following features: * Fully self-hosting --- can both build and install itself. * Implicitly detects and tracks module dependencies. * Builds in parallel as much as possible. * Can scan through a source directory to add all files, saving the trouble of adding them manually. * Supports compiling C and Fortran sources in addition to Haskell sources, and linking everything together. * Utilizes a “tool” system to make it easy to extend its functionality, such as by adding a new language. * Flexible configuration system: tool options (e.g., path to the Fortran compiler) can be detected automatically, set in a configuration file, or specified on the command line. * Provides help messages both to list the targets and to explain the configuration command-line options. * Does not terminate at the first error, but instead tries to do as much as possible and then report all errors. (This is a general philosophy that holds both for the build, the configuration, etc.) * Easily supports multiple targets that can depend on the results from other targets. * Automatically resolves package dependencies, as read from .cabal file. Detects when a module is not in any known dependency, and reports an error that also lists all packages that export this module. What separates this system apart from others is that it uses Haskell’s built-in laziness to handle dependency ordering and parallelism. That is, one expresses the desired build result as a function of the input sources; when the result is demanded, it causes Haskell to go through and execute on-demand all of the necessary build steps. To get parallelism, just tell GHC to use multiple threads with the “+RTS -N# -RTS” option, where # is the number of threads. (All that I had to do to get this to work was put parLists in a couple of places.) This is a big win for me because it means that I get the correct behavior without having to write and test my own complicated graph data structure for tracking the dependencies between build steps. The philosophy of building up a big calculation of which only parts need be lazily demanded can be extended further to the build phases, which I call “targets”. For example, the first line of the code defining the build target is: build = configure >>= \configuration -> ... This demands the configuration target, and then uses the result in the build. So when you run “./Setup configure”, you only demand that Setup compute the value of “configure”, but when you run “./Setup build” you demand both “build” and also “configure”. All of the errors that are reported are “composable” in the sense that they can be combined into a new error message that leaves nothing out and also has no duplicates. As much as possible the system tries not to stop until it has nothing else that it can do, allowing it to uncover as many errors as possible and then compose them into a single message. I have posted Blueprint to Hackage so that people can see what I have done and possibly play with it. I hope to eventually document it and add examples, but I figured it was better to release early and get it out there sooner rather than later so that people can see what I’ve done. Thus, at this point it should be considered a PREVIEW release, not even an alpha release. Having said that, within the domain of the functionality it implements it works well enough that I use it myself as the build system for a Physics simulation code that is a mixture of C, Haskell, and Fortran. To see what Blueprint looks like in action, take a look at Setup.hs. For example, Setup can either build a library (“build” target) or it can build itself (“bootstrap” target); it is smart enough to use different flags and directories in the two cases so that there ends up being in essence two parallel builds. Setup also has a lot of targets: configure, reconfigure (delete cached configuration and then configure), build, rebuild (clean then build), clean, distclean, install, bootstrap (build itself rather than a library), haddock (documentation generation that does not work particularly well yet). Anyway, take a look if any of this sounds interesting to you, and let me know if you have any questions! - Greg PS: You're best bet for browsing through the sources is to use Leo (leo.sourceforge.net) since this makes it easier for you to see how everything is organized.

2 3

Fwd: [Haskell-cafe] Haskell for Physicists
by Don Stewart 05 Dec '09

05 Dec '09

Hey all, Following up on this, I'm presenting a position paper tomorrow on the use of EDSLs to improve productivity and lower cost when developing code for new high performance architectures (like GPUs). http://www.galois.com/blog/2009/10/13/domain-specific-languages-for-domain-… It advocates for Haskell + EDSLs, much as we have been discussing in this thread. -- Don

6 6

I miss OO
by Michael Mossey 04 Dec '09

04 Dec '09

I'm fairly new to Haskell, and starting to write some big projects. Previously I used OO exclusively, mostly Python. I really miss the "namespace" capabilities... a class can have a lot of generic method names which may be identical for several different classes because there is no ambiguity. In my musical application, many "objects" (or in Haskell, data) have a time associated with them. In Python I would have an accessor function called "time" in every class. So if I have objects/data note1, cursor1, and staff1, Python: note1.time() cursor1.time() staff1.time() Haskell needs something like note_time note1 cursor_time cursor1 staff_time staff1 which is a lot more visually disorganized. What's worse, I have a moderate case of RSI (repetitive strain injury) so I type slowly and depend on abbreviations a lot. I use the souped-up abbreviation capabilities of Emacs. Let's say I have a field/member-variable called orientedPcSet that is used across many classes. In Python, I can create an abbreviation for that and it is useful many times. In Haskell, I might need someType_orientedPcSet someOtherType_orientedPcSet thirdType_orientedPcSet which prevents me from using abbreviations effectively (especially the dynamic-completion feature). (It would help to make the underscore not part of word syntax, but that's not ideal.) So I'm thinking of moving to a scheme in Haskell using modules, most types being defined in their own modules, and doing qualified imports. Generic names like 'time' can be defined in each module w/o clashing. Then I have Note.time note1 Cursor.time cursor1 Staff.time staff1 This is very useful because I can define abbreviations for the type name and for oft-used accessor function names and these abbrevs are more organized, easier to remember, and easier to combine. I would be interested in comments... is this a good way to do things? Am I trying too hard to impose OO on Haskell and is there a better way? Thanks, Mike

19 26

Data.Binary and error handling
by Alexey Khudyakov 03 Dec '09

03 Dec '09

Hello Is there any plans to add error handling for binary? When it comes to binary parsing most awkward part is error handling I presume answer will be like "there are some vague plans but no one to implement them" so the second question how could it be done? Naive implementation of error handliing which converts Get monad into hybrid of state monad and error monad (Either like) gives about 5 times slowdown.

6 9

Card games
by Felipe Lessa 03 Dec '09

03 Dec '09

Hi! I would like to know if anybody has already thought of or tried to code an EDSL for card games. Ideally you should be able to write the rules the games and get "for free": - Game generator: given an input deck, construct the initial state of the game. - Random game generator: besides just creating a random deck and using the item above, it should be nice to be able to randomly construct the game from the final positions. This should guarantee that all random games are solvable. - "Hints" generator: IOW list possible moves given a game state. - Playable game: probably the EDSL should include at least some information to be able to properly place the cards on the screen. - Game solver: this is somewhat harder to do efficiently, but an inneficient one should be doable. - Demo mode: related to the above, an auto-play distract-me mode. - Tutorial mode: show a screen for each of the rules written? - ...anything more? Just curious, this looks like a perfect job for an EDSL. Also, I guess anybody trying to do something like this should read PySol's code to have some ideas. -- Felipe.

6 12