- Haskell-Cafe - Haskell.org

Trees
by Adrian Neumann 03 Dec '07

03 Dec '07

Good morning, as an exercise for my Algorithms and Programming course I have to program a couple of simple functions over trees. Until now everything we did in Java could be done in Haskell (usually much nicer too) using the naive > data Tree a = Leaf a | Node a [Tree a] But now the assignments require more than a simple top-down traversal. For example: given a tree t and two nodes u,v, find the first common ancestor. In Java this is really simple, because each node has a "parent" reference. That way I only need to follow those references until I find the first common ancestor. This should take something like O(log n) in the average case. In Haskell however the best way I've come up with so far is doing a BFS and looking for the last common node in the paths to u and v. This is neither fast, nor particularly elegant. So how would you smart guys do it? With a Zipper? It would be nice if there was an elegant solution without monads. --Adrian

8 8

Optimizing cellular automata evaluation (round 2)
by Justin Bailey 03 Dec '07

03 Dec '07

I posted awhile back asking for help improving my cellular automata program. I am competing with a C program which evolves CAs using a fairly simple genetic algorithm. The algorithm involves evaluating 100 rules on 100 CAs, 100 times. In C this takes about 1 second. In my Haskell version, it takes about 20 minutes. That's an improvement from my first attempts, which took 7 hours. All the time is spent in the function that evaluates one iteration of a given CA. It examines each cell and its neighbors and, based on the values found, updates the cell to be white or black. Here is the code, followed by an explanation of what it's doing. I'm looking for any suggestions on making this faster. Prettier helps too but not at the expense of speed. http://hpaste.org/4151#a0 I represent the automata as an array of integers, where each bit represents a cell. Automata 'wrap' around, so marching through the array and determing the value of all neighbors is tricky around the edges. My goal was to minimize conditionals as much as possible and to avoid any "modulo" arithmetic. I wanted to use straightforward array access. My implemention uses three functions: fill, fillS and fillE. Each evalutaion of fill will determine the new values for cells represented by the current array element. fill handles two conditions - when the array element being examined is the last element or when it is not. It calls fillS with appropriate arguments, the results of which become the value for the integer in the current array position. fillS then handles two conditions - when the "neighborhood" of the bit being examined crosses to the "next" array element and when it does not. When the "neighborhood" crosses to the next array element, fillE is called. fillE finishes determining the values for the remaining cells in the integer and returns, ending the current evaluation. There are some other details in the code (for example firstRule) which could be made faster and/or cleaner, but their contribution is far outweighed by the fill function. If there is one thing I'm happy about, its the memory performance of this code. It runs in a constant 7 - 10MB of memory, even when I'm doing 100 generations with 100 rules and 100 CAs. Each CA is evaluated for 250 steps, which means every generation does 2.5M steps. That kind of memory usage is pretty sweet. Thanks in advance to those willing to take the time to look at this code! Justin

7 8

Re: [Haskell-cafe] Possible Improvements
by PR Stanley 03 Dec '07

03 Dec '07

That's a very good point. Yes, let's have some detailed explanations accompanied by some good examples. Cheers, Paul At 08:43 03/12/2007, you wrote: > > I agree that (in this context, beginning learning Haskell) it is a > > somewhat minor issue. But I disagree that this is something you should > > ignore until it becomes a problem and I do think that it should be part > > of learning Haskell. Properly using strictness is an important part of > > using Haskell. It makes the difference between code that stack > > overflows and code that doesn't, code that takes 100 seconds and code > > that takes 10, code that uses 3MB of RAM and code that uses 600. At > > least the first of these is not, in my mind, the difference between > > "optimized" and "unoptimized", but rather the difference between correct > > and incorrect. Writing better code at the beginning is much easier than > > trying to figure out what the problem is later. Furthermore, writing > > better code is not more difficult. In this case it merely means adding > > two characters. Of late, the "rules of thumb" for this sort of thing > > are becoming more widely known. Such things need to be "instinctively" > > part of how you write code, much like writing code tail-recursively or > > not using (++) left associatively. It's not that you should immediately > > know that this is better, but (more strongly) that you should not even > > think of the worse ways to begin with in many cases. > >It would be great if someone could exemplify these "rules of thumb", >e.g. "Primitive types such as Int should be strict unless in the three >canonical examples X, Y and Z." My strictness radar is still quite >poor and I feel I can't make informed decisions on when I need to make >something more strict or lazy. > >-- Johan >_______________________________________________ >Haskell-Cafe mailing list >Haskell-Cafe(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

more info on building the Unix package on cygwin
by Galchin Vasili 03 Dec '07

03 Dec '07

Hello, I put an ugly kludge(on my laptop) in the unix.cabal file For the includes-dir "attribute" I explicited specified the path to the cygwin include directory. The Unix package build gets farther and then gets errors. At this point, it appears that the cygwin sys/types.h has a "bug" .. id_t is not defined but id_t is referenced by sys/resources.h/(getpriority/setpriority). Please see see http://www.opengroup.org/onlinepubs/000095399/functions/setpriority.html for getpriority function signature. In any case, I want compare the Linux sys/types.h include. To summarize: 1) I am just learning about the .cabal file format from the Cabal .pdf. In any case, it appears that for the case of cygwin that unix.cabal is deficient. 2) It also appears that the cygwin sys/types.h failed to defined id_t which is needed by sys/resources.h which in turn is needed by System/Posix/DynamicLinker/Module.hsc (error at line 57 where HsUnix.h is refd .. and in HsUnix.h at line # 38 sys/resource.h is referenced.) I can provide a stderr "log". Kind regards, Vasya

1 0

doing builds using cygwin on Windows ....help
by Galchin Vasili 03 Dec '07

03 Dec '07

Hello, I have suceeded in doing a build on top of cygwin. However, after editing some of the cygwin "bashrc" files, teh darcs path and haddock path still don't show up when I do a "echo $PATH". I am now reading http://cygwin.com/cygwin-ug-net/setup-env.html. "The PATH environment variable is used by Cygwin applications as a list of directories to search for executable files to run. This environment variable is converted from Windows format (e.g. C:\WinNT\system32;C:\WinNT) to UNIX format (e.g., /WinNT/system32:/WinNT) when a Cygwin process first starts. Set it so that it contains at least the x:\cygwin\bin directory where " x:\cygwin is the "root" of your cygwin installation if you wish to use cygwin tools outside of bash. " .. however, I don't see in which file PATH can be set. Any help? I really want to get my Haskell build environment set up and cranking away. Kind regards, Vasya

2 1

who develops and maintains the Unix package?
by Galchin Vasili 03 Dec '07

03 Dec '07

Hello, I am starting to get in the groove related to runhaskell -- config/builds on top of cygwin (I haven't had time to carve up hard drive and install Linux). In any case, I really want to get the Unix package to build on cgywin (as advertised at http://hackage.haskell.org/cgi-bin/hackage-scripts/package/unix-2.2.0.0) When i do "runhaskell Setup.lhs configure" things seem to go fine, .log fine is clean, and pertinent cygwin include files like times.h are found, but when i do a "runhaskell Setup.lhs build" then the include files that are allegedly found during the configure "probe" cannot be found. ???? 1) During the "runhaskell Setup.lhs build" step, what human readable file is used and contains paths to the cygwin Posix include file directories? 2) thatis foloowing is a better approach for me .. => 2) Somebody obviously put " (except under Cygwin)". Can you point at who made this claim and why? Kind regards, Vasya

2 2

Re: Haskell-Cafe Digest, Vol 51, Issue 180
by manu 03 Dec '07

03 Dec '07

>> >> I'm trying to build diverse packages from Hackage with ghc 6.8.1, >> they usually fail to build because of missing language extensions. >> >> Sometimes I am unable to determine the proper name of the extension >> missing in .cabal >> I tend to slap {- #OPTIONS -fglasgow-exts #-} at the top of the >> troublesome file. >> It works, but out of curiosity, what is the downside of such an >> approach ? (bigger executables ?) > > Can you list which packages failed to build out of the box? > > -- Don > Well I'd say none of the packages I've tried, build out of the box, that include : haskelldb haskelldb-hdbc haskelldb-hdbc-sqlite3 HDBC HDBC-sqlite3 Agreed some of these compile right after tweeking the build-depends: and extensions: lines in the .cabal file (apart from the pesky PatternSignatures which require a LANGUAGE pragma in the source file) haskelldb-hdbc-sqlite3 is the one that I couldn't get past... I didn't bother with hsql-mysql-1.7 since Duncan Coutts mentioned it required significant work (and I cannot do much) Manu

6 6

Peg solitaire in Haskell - anyone interested?
by Maurício 03 Dec '07

03 Dec '07

Hi, I've just finished a command line application that solves peg solitaire. It does that by building a database of (possible ^ solvable) boards, and you can walk through them from the beggining of the game to the end. It always shows all movements you can do where you are guaranteed to finish with just one peg. Today, it's messy. So I would like to know if people are interested on that. If at least five people say they would REALLY like to play with that program, I will make it into a nice gtk2hs application and release it on the net. If not, I'll keep it like it is and use for my pleasure only. Thanks, Maurício

1 0

fast Array operations: foldl, drop
by Henning Thielemann 02 Dec '07

02 Dec '07

I thought operations like "foldl'" and "drop" must be very fast on arrays (especially UArray) with appropriate pointer tricks, I mean pointer incrementing instead of indexing for "foldl'" and a pointer into the array for "drop". Is it planned to add such functions? Ok, if "foldl f x . elems" and "listArray (i,sufficientlyBig) . drop n . elems" are fused to high speed code, then these functions do not need to materialize in the API.

8 11

ANN: Teach Yourself Gtk2Hs in 21 Hours
by Hans van Thiel 02 Dec '07

02 Dec '07

Hello All, The Gtk2Hs basics tutorial, based on the Tony Gale and Ian Main GTK+2.0 tutorial, is now available for review and comment. The TOC: 1. Introduction 2. Getting Started 3. Packing 3.1 Packing Widgets 3.2 Packing Demonstration Program 3.3 Packing Using Tables 4. Miscellaneous Widgets 4.1 The Button Widget 4.2 Adjustments, Scale and Range 4.3 Labels 4.4 Arrows and Tooltips 4.5 Dialogs, Stock Items and Progress Bars 4.6 Text Entries and Status Bars 4.7 Spin Buttons 5. Aggregated Widgets 5.1 Calendar 5.2 File Selection 5.3 Font and Color Selection 5.4 Notebook 6 Supporting Widgets 6.1 Scrolled Windows 6.2 Event Boxes and Button Boxes 6.3 The Layout Container 6.4 Paned Windows and Aspect Frames 7. Action Based Widgets 7.1 Menus and Toolbars 7.2 Popup Menus, Radio Actions and Toggle Actions This covers about half of Gtk2Hs (guesstimate) but (hopefully) most of what's needed for the run of the mill GUI. It's available or will be on http://darcs.haskell.org/gtk2hs/docs/tutorial/Tutorial_Port/ http://j-van-thiel.speedlinq.nl/gtk2hs/index.html Thanks to Alex Tarkovsky it's in XHTML and well structured for easy maintenance and adaptation. I hope a Gtk2Hs basics tutorial will help to popularize this large, powerful and sophisticated gui library for Haskell. Needless to say, please don't hesitate to comment and report errors. Regards, Hans van Thiel

4 3