- Haskell-Cafe - Haskell.org

a monad for secret information
by Seth Gordon 11 Oct '06

11 Oct '06

I finally (think I) understand monads well enough to make one up: > module Secret (Secret, classify, declassify) > where > > data Secret a = Secret a > > classify :: a -> Secret a > classify x = Secret x > > declassify :: Secret a -> String -> Maybe a > declassify (Secret x) "xyzzy" = Just x > declassify (Secret x) _ = Nothing > > instance Monad Secret where > return = classify > (Secret x) >>= f = f x The nice thing about this is that (correct me if I'm wrong) clients of the module can't sneak information out of the monad without either using the right password or by using one of the unsafe*IO methods. (Or by running the program in a debugger. But you get the idea.) The not-so-nice thing is that the literal text of the password is baked into the data definition. I'd like to have a more general version of Secret that allows someone to pass the password in when constructing a secret, and preserves that password when "return" is used, but doesn't let the second argument of (>>=) see the password. Something like this:... > data Classification pw a = Classification pw a > declassify (Classification pw a) pw' = case pw' of > pw -> Just a > _ -> Nothing > > type Secret = Classification "xyzzy" ...but that doesn't parse. Is it even possible to have a type like this that still observes the monad rules? Is this the sort of thing that I need to understand arrows to pull off?

9 11

Haskell performance (again)!
by Yang 11 Oct '06

11 Oct '06

This email actually turned out much longer than I expected, but I hope it sparks interesting (and hopefully, thorough!) discussion on points that weren't touched on by previous threads on this topic. What follows describes my journey thus far exploring what I see (as a newcomer to Haskell) as a major problem with Haskell - the ease with which users can write inefficient code, and have no idea that they did. Some of this has to do with laziness, some of it with the functional programming in general. My goal is to achieve (as a link further down says) *good* performance, not blazing performance. I.e., I want to avoid what should really be no-brainers such as little-omega(1) space utilization for simple folds. The first version of a simple program I wrote was reasonably "clean." (Throughout this email, "clean" is supposed to mean some combination of: clear, compact, modular, elegant, etc.) It's a polynomial adder, which takes in lists of (coefficient, degree) tuples, combining terms of the same degree and maintaining a sorted order of least-to-greatest degree: type Poly = [(Int,Int)] addPoly1 :: Poly -> Poly -> Poly addPoly1 p1@(p1h@(p1c,p1d):p1t) p2@(p2h@(p2c,p2d):p2t) | p1d == p2d = (p1c + p2c, p1d) : addPoly1 p1t p2t | p1d < p2d = p1h : addPoly1 p1t p2 | p1d > p2d = p2h : addPoly1 p1 p2t addPoly1 p1 [] = p1 addPoly1 [] p2 = p2 addPoly1 [] [] = [] But this doesn't use tail recursion/accumulation (which seems to me like a complete hack that is a mandatory price to pay for using FP), so I rewrote it: addPoly :: Poly -> Poly -> Poly addPoly p1 p2 = let addPoly' p1@(p1h@(p1c,p1d):p1t) p2@(p2h@(p2c,p2d):p2t) result | p1d == p2d = addPoly' p1t p2t ((p1c + p2c, p1d):result) | p1d > p2d = addPoly' p1 p2t (p2h:result) | p1d < p2d = addPoly' p1t p2 (p1h:result) addPoly' (p1:p1s) [] result = addPoly' p1s [] (p1:result) addPoly' [] (p2:p2s) result = addPoly' [] p2s (p2:result) addPoly' [] [] result = reverse result in addPoly' p1 p2 [] But laziness will cause this to occupy Theta(n)-space of cons-ing thunks. (See appendix for a simpler example.) My third iteration will become even uglier because I will have to incorporate strictness and things like $! or seq. And there's probably a whole host of other issues that I haven't even thought of or don't know about (boxing, space leaks, etc.). >From #haskell, I got a general piece of advice: Oct 07 22:37:20 <Cale> Actually, a lot of the time, code gets messy when people optimise because they take the wrong road to optimisation Oct 07 22:37:31 <Cale> There are two ways to optimise a piece of Haskell code Oct 07 22:37:43 <Cale> You can make it stricter, forcing evaluation to occur sooner Oct 07 22:38:01 <Cale> Or you can make it lazier, ensuring that things are not demanded until actually needed Oct 07 22:38:09 <Korollary> @wiki performance Oct 07 22:38:09 <lambdabot> http://www.haskell.org/haskellwiki/performance Oct 07 22:38:13 <Cale> the latter route actually tends to result in cleaner code Of course, to want to learn route 2 was a no-brainer. I read through that wiki page on laziness and various other resources, but was disappointed in what I found: http://www.haskell.org/haskellwiki/Performance/Laziness only discusses the aspect of laziness where you only evaluate what you need, which by now has been repeatedly beaten into my head and sounds obvious. Aren't there other advantages to laziness? Or at least, am I not fully appreciating the "obvious" work-avoiding part of laziness? For instance, the example seems to allude to sharing (between the even and odd functions), which I think ties in strongly with laziness. I was hoping for more in-depth insights on how to take advantage of laziness to write cleaner AND more efficient code. (A loose analogy exists in computer architecture - the smaller the chip, the less power it can consume/the faster it can clock.) http://en.wikibooks.org/wiki/Haskell/Laziness_revisited does slightly better but still just scratches the surface - it gives an example of a clean (compact and modular) yet efficient piece of code (isSubstringOf), then completely neglects explaining it (e.g., exactly why/how does it run more efficiently?). http://users.aber.ac.uk/afc/stricthaskell.html seems to suggest that strictness is the way to go. Please say it ain't so! http://www.algorithm.com.au/mt/haskell/haskells_performance.html says that between code optimized for performance in Haskell and in another language (like O'Caml), "which is more declarative, high-level, and most importantly, which one doesn't require an expert in the language to write" is an unfortunate (for Haskell fans) no-brainer: "The problem then is you have to know why something is slow, and there's where Haskell can get complex. Is there a space leak? (Do you even know what a space leak is?) Is your array strict instead of lazy? If it's strict, is it boxed instead of unboxed? (Do you even know what unboxing is?) Can you use unsafeRead instead of readArray? (Did you know that unsafeRead exists? I sure didn't!)" So, how do I take advantage of laziness to write clean *and* performant code? I've been seeking resources with concrete examples, explanations, or guides on how to "systematically" do this. Is this even possible? Or am I deluding myself, and strictness is the way to go? If so, has there been any work/research to address the issues pointed out in the last blog entry? And do most (experienced) Haskell users sacrifice cleanliness for speed, or speed for cleanliness? I feel that an understanding of how Haskell compilers work would help immensely in writing more performant Haskell code (or just better Haskell code in general), as well as understand what optimizations are reasonable to expect from the compiler. (I have a university class of background on the design/implementation of simple lexers/parsers/compilers/interpreters/code block graph analyses for imperative OO languages. However, i'd love to learn more about these things for a language like Haskell, including details on lazy evaluation, pattern-matching, overloading (why it's slow), currying, PFA, type classes, monads, etc. Preferrably something "lighter weight" than a bunch of research papers. Any pointers?) BTW, please also feel free to give me feedback/refinements on my code snippets. :) Thanks a ton for any enlightenment! Yang Aside: http://www.matthewmorgan.net/blog/archives/2004/10/07/haskell-performance. This post brings up a most reasonable point (venturing off onto tangent now) - space leaks are a much more serious concern than performance, and they're a difficult problem even for experienced Haskell users (http://www.haskell.org/pipermail/haskell-cafe/2003-December/005587.html)

13 19

Profiling CAFs (re-post)
by Matthias Fischmann 11 Oct '06

11 Oct '06

Hi again, I posted a bunch of questions on profiling here a few days back, but couldn't tickle anybody to post a reply. Since I am not tired any more today, but still can't understand the documentation, or the output of the profiler, here it goes again: What qualifies as constant applicable form, and why is it not labelled in a more informative way? Why are there functions that inherit all of their (considerable) time and space consumption from elsewhere, but nothing in the list would allow for such a rich inheritage? As I said, I am happy to set up a wiki page if I learn anything that helps me improve the utility of profiling (the profiler and the rudimentary documentation are of great value as is). And i am happy to take pointers and go read articles if you tell me they help in the everyday work with ghc profiling. thanks / cheers, matthias

3 4

casting
by Thomas Conway 11 Oct '06

11 Oct '06

On 10/11/06, Bulat Ziganshin <bulat.ziganshin(a)gmail.com> wrote: > it's a sort of problem that bites me many times when i start to wrote > Streams library :) although you said that you discovered the > dictionaries mechanism, i propose you to read > http://haskell.org/haskellwiki/OOP_vs_type_classes page where you can > find something that you don't yet know Yes, I did actually know this stuff, it was just paged out, and I posted before thinking. :-) Something to do with having two small kids, one of whom gets up waaaaay too early in the morning (i.e. 5 - 5:30am). :-) In theory, however, there is no particular reason why a runtime type cast couldn't be implemented to allow downcasting, but it does require the runtime system to have a repository of instance declarations, or associate with static data for a type the classes of which it is an instance. It's been a few years, but if my recallection is correct, the Mercury runtime system does this. T.

1 0

Is Haskell a 5GL?
by Ch. A. Herrmann 10 Oct '06

10 Oct '06

Dear Haskellers, do you think that Haskell is a 3GL (third generation language) or a 5GL or that the hierarchy of programming language generations is useless? I see a problem if the potential of a language is evaluated according to the generation it belongs to. 1GLs: machine languages 2GLs: assembler languages 3GLs: programming based on algorithms (C, Java, ...) 4GSs: domain-specific languages (SQL,...) 5GLs: automatic problem solving (Mathematica, Prolog,...) and/or visual programming (Visual Basic,...) Haskell's laziness would in principle permit programming in a style akin to Prolog, e.g., for parser combinators. The question is: how strong is the influence of laziness in everyday Haskell programming? Cheers -- Christoph

16 29

casting
by Thomas Conway 10 Oct '06

10 Oct '06

Hi All I'm having some difficulty with typeclasses. What I'm trying to do should be obvious, but it's still giving me trouble. I want to take a packaged item, and strengthen the constraints on its type. Rather than being just any type that is an instance of A, I want to do a runtime check and do something different if it is a type that is also an instance of B (which implies that it is an instance of A also). I've attached some code that attempts this, but ghci (er, 6.4.2 with -fglasgow-exts) complains: Compiling Main ( Cast.hs, interpreted ) Cast.hs:15:22: Ambiguous type variable `b' in the constraint: `B b' arising from use of `qux' at Cast.hs:15:22-24 Probable fix: add a type signature that fixes these type variable(s) Failed, modules loaded: none. So, can anyone suggest how I can achieve my goal? thanks, Tom

3 3

How would you replace a field in a CSV file?
by Pete Kazmier 10 Oct '06

10 Oct '06

The other day at work an opportunity arose where I was hoping to sneak some Haskell into the pipeline of tools used to process call detail records (CDRs). In the telecommunications industry, CDRs are used for billing. Each CDR is a single line record of 30 comma-separated values. Each line is approximately 240 characters in length. The task at hand is to replace field number 10 if a new value can be found in a hashmap which is keyed using the contents of the field. My colleague was going to write a C program (that's all he knows), but I whipped up a trivial python program instead. I was curious if a haskell version could be faster and more elegant , but I have not been able to beat my python version in either case. So, I'm curious as to how you would go about this task in Haskell. The input files are generally 300-400MB, and the hashmap will contain perhaps 20-30 items. For those that know python, here is a very simple implementation that happens to be very fast compared to my Haskell version and very short: for line in sys.stdin: fields = line.split(',') fields[9] = tgmap.get(fields[9], fields[9]) print ",".join(fields), For each line in standard input: - Splits the string on the comma: "field0,field1,...,field29" => ["field0", "field1", ..., "field29"] to obtain a list of strings. - Gets the value associated with the key of field9 from tgmap, if it does not exist, it returns a default value which is the original value. I.e., if it's not in the map, then don't replace the field. - Joins the list of fields with a comma to yield a string again which is printed out to standard output. The join method on the string is a bit odd: ",".join([1,2,3]) => "1,2,3" Here is my first Haskell attempt: import Data.ByteString.Lazy.Char8 as B hiding (map,foldr) import Data.List (map) import Data.Map as M hiding (map) -- This is just a placeholder until I actually populate the map tgmap = M.singleton (B.pack "Pete") (B.pack "Kazmier") main = B.interact $ B.unlines . map doline . B.lines where doline = B.join comma . mapIndex fixup . B.split ',' fixup i s = if i==9 then M.findWithDefault s s tgmap else s comma = B.pack "," -- f is supplied the index of the current element being processed mapIndex f xs = m f 0 xs where m f i [] = [] m f i (x:xs') = f i x : m f (i+1) xs' After talking with dons on #haskell, he cleaned my version up and produced this version which gets rid of 'if' statement and makes mapIndex stricter: import Data.ByteString.Lazy.Char8 as B hiding (map,foldr) import Data.List (map) import Data.Map as M hiding (map) -- This will be populated from a file dict = M.singleton (B.pack "Pete") (B.pack "Kazmier") main = B.interact $ B.unlines . map doline . B.lines where doline = B.join comma . mapIndex fixup . B.split ',' comma = B.singleton ',' fixup 3 s = M.findWithDefault s s dict fixup n s = s -- f is supplied the index of the current element being processed mapIndex :: (Int -> ByteString -> ByteString) -> [ByteString] -> [ByteString] mapIndex f xs = m xs 0 where m [] _ = [] m (x:xs') i = f i x : (m xs' $! i+1) That helped things a bit, but I must confess I don't understand how the strictness improved things as I had assumed things were going to be evaluated in a reasonable amount of time due to the printing of output. I thought IO was interlaced with the execution and thus I wasn't going to have to concern myself over laziness. In addition, the function is able to generate new elements of the list on demand so I thought it was a good citizen in the lazy world. Could anyone help explain? And then he came up with another version to avoid the 'unlines', but that did not that really speed things up significantly. So, with all that said, is there a better approach to this problem? Perhaps a more elegant Haskell solution? Thanks, Pete

3 2

Re: [Haskell-cafe] casting
by Thomas Conway 09 Oct '06

09 Oct '06

Thanks Misha & Matthias. I now get what's going on. The mention of the word "dictionary" revealed it all. I've spent the last 7 years programming in C++, and had dynamic_cast<> firmly fixed in my head. I totally forgot that Fergus Henderson and I independently reinvented dictionary passing for the implementation of Mercury circa 1995. :-) I also realized that the concrete signatures from my actual application don't quite satisfy the requirements anyway, and that the problem evaporates when I get the signatures right.:-) T.

1 0

Announce: Monad Transformer Tutorial
by Martin Grabmueller 09 Oct '06

09 Oct '06

Hallo all, I hereby announce a small tutorial on using monad transformers. In contrast to others found on the web, it concentrates on using them, not on their implementation. I'd like to hear comments, suggestions, etc. about it! Both PDF and Literate Haskell source available here: http://uebb.cs.tu-berlin.de/~magr/pub/Transformers.en.html Have fun, Martin

3 3

Bizarre garbage collection behaviour
by Guillaume Theoret 09 Oct '06

09 Oct '06

I'm using Hugs98 for .NET and I'm running into some bizarre garbage collection issues. I hope I'm posting at the right spot. I didn't want to post this in Hugs bugs since I'm pretty new to Haskell and it's entirely possible I'm doing something a way I shouldn't. Back to the problem at hand. My script (link available at the bottom of this email) fetches a webpage through the .NET Net library and processes it. If I output the result of this processing (a list with the player's name, goals, assists and points) to the screen with putStrLn I can process about two dozen before I hit a .NET runtime exception (which is a different issue entirely). If I don't ouput the result to the screen (I delete 2 lines that only do putStrLn, Ln 148 & Ln 161) I get "ERROR - Garbage collection fails to reclaim sufficient space" after 2 players processed which seems completely counter-intuitive to me. Does someone have an idea as to what's going on here? The script (and its dependencies) are available here: http://smokinn.tengun.net/comp348/week6/ Thanks, Guillaume Theoret

1 0