- Haskell-Cafe - Haskell.org

Fw: [Haskell-cafe] Re: do
by Thomas Hartman 04 Dec '07

04 Dec '07

It took me forever to get comfortable with monads. I think it helps if you've seen continuations, or done FP before, or a variety of things that build familiarity. But probably the only thing that I think will work for the masses of plodders (there are always a few stars to crash the curve) is a desire to learn and tons of practice. I wouldn't worry so much about the ideal way to introduce the material. Oh, one other thing. You learn monads when you need them. You need IO right away... well, after you tired of playing with pure functions in the ghci sandbox. my 2c. t. "Dan Piponi" <dpiponi(a)gmail.com> Sent by: haskell-cafe-bounces(a)haskell.org 12/03/2007 07:19 PM To haskell-cafe(a)haskell.org cc Subject Re: [Haskell-cafe] Re: do On Dec 3, 2007 3:54 PM, Ben Franksen <ben.franksen(a)online.de> wrote: > I don't buy this. As has been noted by others before, IO is a very special > case, in that it can't be defined in Haskell itself, and there is no > evaluation function runIO :: IO a -> a. I'm not sure what a function of type m a -> a has to do with the concept of a monad. And I don't really see what the problem is with the IO monad not being definable in (pure) Haskell. IO exposes the same interface as every other Monad, and you need to use that interface to get visible results. So people have to learn it whatever. And the whole point of the Monad is that it's an interface, not a specific implementation. > I'd rather use a simple example like Maybe (modeling failure as an effect). And I'd like to see more people getting off the ground doing interesting stuff with Haskell before their attention spans for pointless-seeming new stuff run out. I'm not talking about the smartest people in computer science courses here. I'm talking about the millions of people writing everyday Python and Ruby scripts, say, who might benefit from a more expressive, type-safe, well-thought out, fast and compiled language. -- Dan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

1 0

doing builds using cygwin on Windows
by Galchin Vasili 04 Dec '07

04 Dec '07

To Nanonthief ...... VasiliIGalchin wrote: > > > " .. 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. > Unless I misunderstood what you want, you can add a path to the PATH variable by adding the line: export PATH="$PATH:/path/to/folder" to the ~/.bashrc file (and also possibly the ~/.bash_profile file). I've also tried to build haskell with cygwin, but didn't have any luck. Could you describe how you managed to do it? -- nanothief ... here is what I decided to add to unix.cabal .. and I am getting farther ... build-depends: base, directory extensions: CPP, ForeignFunctionInterface include-dirs: include c:/cygwin/usr/include <<< added cygwin include path includes: HsUnix.h execvpe.h install-includes: HsUnix.h HsUnixConfig.h execvpe.h c-sources: cbits/HsUnix.c cbits/execvpe.c

1 0

Possible Improvements
by PR Stanley 03 Dec '07

03 Dec '07

Hi data Tree = Leaf Int | Node Tree Int Tree occurs :: Int -> Tree -> Bool occurs m (Leaf n) = m == n occurs m (Node l n r) = m == n || occurs m l || occurs m r It works but I'd like to know if it can be improved in any way. Thanks, Paul

13 17

Monads
by PR Stanley 03 Dec '07

03 Dec '07

Hi Does the list consider http://en.wikibooks.org/w/index.php?title=Haskell/Understanding_monads&oldi… a reliable tutorial on monads and, if not, could you recommend an onlien alternative please? Thanks, Paul

3 2

ANN: atom 2007.12
by Tom Hawkins 03 Dec '07

03 Dec '07

Hello, Atom is a language embedded in Haskell for describing reactive software, primarily for realtime control applications. Based on conditional term rewriting, an atom description is composed of a set of state transition rules. The name "atom" comes from the atomic behavior of rules: if a rule is selected to fire, all its transitions occur or none at all. A hallmark of the language, rule atomicity greatly simplifies design reasoning. This release of atom is a major redirection. Atom is no longer a hardware description language (I changed jobs. I'm now in software.). Much of the frontend language and backend generators have changed, though rule scheduling remains nearly the same. On the frontend, atom's Signal datatypes have been replaced with Terms and Vars, which leverage Haskell's GADTs. The 4 supported Term and Var types include Bool, Int, Float, and Double. At the backend, atom generates C and Simulink models. The Verilog and VHDL generators have been dropped, but they may reappear in the future. Enjoy! http://funhdl.org/ darcs get http://funhdl.org/darcs/atom -Tom

2 1

A tale of three shootout entries
by Sterling Clover 03 Dec '07

03 Dec '07

In some spare time over the holidays I cooked up three shootout entries, for Fasta, the Meteor Contest, and Reverse Complement. I should probably have tossed them to haskell-cafe before submission, for review and ideas, but they're up now. In any case, all three were great learning experiences, but could use some other eyes and ideas to be the best that they can. First up is the meteor-contest entry. http://shootout.alioth.debian.org/gp4/benchmark.php? test=meteor&lang=ghc&id=5 This is the clear win of the bunch, with significantly improved time thanks to its translation of the better algorithm from Clean. However, it's still missing something. Nearly all its time is spent in a tight loop in the solveCell function near the end of the code. I tried unboxing this, but failed because it spends the bulk of its time applying a bitwise and between the recursively passed value and a piece of data retrieved from the masksAtCell data structure which is of type :: Array (Row,Col) (Array Color [Mask]). (Note that Mask, Color, Row and Col are all type synonyms for Int that I added for readability). As each Mask is stored in this list, the masks can't easily be unboxed -- some sort of custom data structure built using the FFI seems in order here. If anyone wants to tackle this, I think it could be a big win for performance. Next is reverse-complement. http://shootout.alioth.debian.org/gp4/benchmark.php? test=revcomp&lang=ghc&id=3 This *would* be a big win except I dimly doubled memory usage from the previous entry due to filtering newlines explicitly -- which does, one should note, provide a large performance gain. The solution here seems the most obvious -- roll the newline stripping into the destructive modifications performed in the revcomp function, as the winning C++ entry does. I'll probably get around to this eventually, but if someone else wants to try to implement this or any other performance improvements, please jump right in. Additionally, there might be some other tricks to reducing its memory usage that escape me at the moment (noting, of course, that using a strict bytestring, as we should, its unavoidable that we consume the entire contents of the input at once... I think?) Finally, there's fasta. http://shootout.alioth.debian.org/gp4/benchmark.php? test=fasta&lang=ghc&id=2 This one really depresses me. It outperforms the previous version by roughly 20% on my machine (PPC) but underperforms by roughly the same amount on the shootout box. If you compare it to dons previous version, the "optimizations" I attempted should be pretty obvious. First, I precompute the partial sums for the frequency tables and alter the choose function accordingly. This is a pretty basic measure that all the better entries seem to do. Next, I unboxed the random function, which yielded big speedups However, given that we use an unfoldN, as we should, I couldn't very well pass it a function that returned something of kind #, (especially as Maybe, which unfoldN uses, is of kind *->*). Thus, I hid the unrolled loop in a lazy list of floats that is passed instead of a random seed. I suspect that for some reason I don't understand relating to differences in processors, GHC's internal handling of floating point math, or who knows what, this somehow is the source of the slowdown. If someone with an Intel Pentium 4 machine comparable to that of the shootout box wants to take a look at this code and see why it underperforms, I'd be much obliged. It really seems to me that GHC's fasta performance is far below where it should be (4x slower than Java!) , and I'd like to get its numbers up somehow. Thanks, Sterl p.s. It looks like they've depreciated chameneos in favor of a new version, chameneos-redux. As this was one of the places Haskell really rocked the competition, it would probably be worth updating the Haskell entry for the new benchmark. Also, the n-bodies benchmark seems like another that could be much improved.

8 18

[Announce] FPSIG @ Southampton
by Paulo J. Matos 03 Dec '07

03 Dec '07

Hello all, Just to let you all know I'm leading a Special Interest Group in the University of Southampton, UK which is studying Haskell. I've put up a blog which I'll try to regularly update _at least_ with our meetings summary, exercises and code. We welcome any suggestions/comments/etc either via my email or as comments in the blog. I've added the group to the Haskell Wiki User Groups (I hope there's no problem). Cheers, -- Paulo Jorge Matos - pocm at soton.ac.uk http://www.personal.soton.ac.uk/pocm PhD Student @ ECS University of Southampton, UK

1 0

Re: [Haskell-cafe] Parsing unstructured data
by Olivier Boudry 03 Dec '07

03 Dec '07

On 12/2/07, Steven Fodstad <flarelocke(a)hotpop.com> wrote: > > Sorry for not responding earlier. The haskell-cafe list is hard to keep > up with. > > The process of finding geographic (lat/long) coordinates from a text > address is called geocoding. Obviously extracting the parts of an > address is part of that, so you might find better results looking for > geocoding, rather than the more general and more difficult topic of > extracting structure from unstructured data. Unfortunately, I don't > have any references at hand on that part of geocoding. > Hi Steven, The idea of using the geocoding approach seems appealing. I already thought of using geocoding for address validation (after the parsing) but not of looking at how geocoding tools parse addresses. But I'm not sure geocoding tools would be suitable to handle my addresses. I used a few geocoding tools and usually you have to provide the address in a very specific format if you want it to be recognized. Also most of the time it work quite well for US addresses but not for other countries addresses. I need to recognize very specific parts of an address. More than what a geocoding tools will require. Like dock #, doors, suite #, contact person, etc... I'm currently using the ZipFourCE web service from BCCSoftware for validating my addresses against the USPS address database. This tool is built for parsing and correcting addresses but I just use it for validation as it's not "smart enough" to parse them or maybe they are just too scrambled for the parsing to be automated using an out of the box tool. ;-) Thanks for your input, Olivier.

1 0

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