October 2008 - Haskell-Cafe

Re: Repair to floating point enumerations?
by Henning Thielemann 16 Oct '08

16 Oct '08

David Roundy schrieb: > Why not look for a heuristic that gets the common cases right, rather > than going with an elegant wrong solution? After all, these > enumerations are most often used by people who neither care nor know > how they're implemented, but who most likely would prefer if haskell > worked as well as matlab, python, etc. Although MatLab has a lot of bad heuristics, they fortunately didn't try to be too clever with respect to rounding errors. Floating point enumerations have the same problems in MatLab as in all other languages.

3 3

Rewrite rules
by George Pollard 16 Oct '08

16 Oct '08

Section 8.13.2 of the GHC manual[1] states: > GHC keeps trying to apply the rules as it optimises the program. For > example, consider: > > let s = map f > t = map g > in > s (t xs) > > The expression s (t xs) does not match the rule "map/map", but GHC > will substitute for s and t, giving an expression which does match. If > s or t was (a) used more than once, and (b) large or a redex, then it > would not be substituted, and the rule would not fire. > The part I'm interested in here is (a); if an expression is used more than one then it cannot be substituted for. Is there any way to work around this or force it? The reason I ask is that as a bit of fun (and inspired by Joachim Breitner's blog post [2]) I was going to try writing a rewrite rule for the first time. What I had in mind was this: {-# RULES "index cycled list" forall list n. cycle list !! n = list !! (n `mod` length list) #-} However, in the case he has written about this won't fire, since the LHS cannot be substituted as `cycle list` is used more than once: > let rlist = cycle list > print ( rlist !! (10^9), rlist !! 0 ) I can get it to fire again if I write it like this: > {-# RULES > "!!/cycle" forall list. (!!) (cycle list) = (\n -> list !! (n `mod` length list)) > #-} > > ... > > let rlist = (!!) (cycle list) > print (rlist (10^9), rlist 0) But this is non-obvious and I'd rather have it fire in the first case (i.e. when used naïvely). So, back to my question; is there a workaround or force for this... or does it break too many things if done? [1] http://www.haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html#… [2] http://www.joachim-breitner.de/blog/archives/308-guid.html

3 3

(OT) Humorous definition for fixed points?
by Corey O'Connor 16 Oct '08

16 Oct '08

I was just reminded of one of the joke definitions of recursion: "recursion: see recursion". Perhaps there is a similar one for fixed points? "To learn about fixed points find the fixed point of the process: Given somebody learn about fixed points from them." Course, my understanding of fixed points is poor and my jokes always have poor delivery. So I'm sure somebody else can do better. -Corey O'Connor

2 1

FFI Newbie: c functions that want pointers to objects
by Mauricio 16 Oct '08

16 Oct '08

Hi, Some functions in C changes data using pointers, like this example: void change_int (int *n) { *n ++; } What is the proper way to handle that? I guess I should wrap it like this: foreign ccall "change_int" change_int :: Ptr CInt -> IO () Can I use that on a CInt in Haskell code? Like this obviously wrong code, but that probably shows what I want: do let myN = 5 change_int myN Thanks, Maurício

2 1

What is this function?
by John Ky 16 Oct '08

16 Oct '08

Hi, I've written this function here: scramble [] = [] scramble [x] = [[z] | z <- scramble x] scramble (x:xs) = [(y:z)|y <- scramble x, z <- scramble xs] and (I think) it roughly does what I want it to: *Main> scramble ([]::[Int]) [] *Main> scramble ([1]::[Int]) [[1],[2]] *Main> scramble ([1,2]::[Int]) [[1,1],[1,2],[2,1],[2,2]] *Main> scramble ([1,2,3]::[Int]) [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]] Three questions: 1. What should I call this function? 2. Is there already one in the standard library that does the same thing? 3. Is it possible to rewrite it with only "scramble []" and "scramble (x:xs)" and not the "scramble[x]"? Thanks -John

3 2

What does laziness buy you?
by Ryan Ingram 16 Oct '08

16 Oct '08

One thing that is hard to communicate to people in industry is what value laziness has. You can point people at the WhyFP paper, and talk about infinite data structures and decoupling generation from search until you're blue in the face, but it's so far beyond the day-to-day work of regular programmers that they don't really comprehend. But I was talking to Simon Marlow yesterday and he pointed out something that strikes me as a great example to give of "what laziness buys you". Lets talk about atomic changes. In particular, I want to examine the function atomicModifyIORef :: IORef a -> (a -> (a,b)) -> IO b This takes an IORef, reads the value out of it, calls some code that gets a new value and may return some derived data, writes the new value into the IORef, and returns the derived data. It has the invariant that no other change to that IORef can happen in between. Now, there are all sorts of issues like "what if 'f' has a side effect" that get sidestepped entirely by purity, but I don't want to talk about those; I think the benefits of purity are easier to argue in many contexts. Lets just look at a simple Haskell implementation: > atomicModifyIORef p f = do > a <- readIORef p > let r = f a > writeIORef p (fst r) > return (snd r) This is a non-atomic implementation, but we can fix it assuming we have "compare-and-swap" available; any language with boxed types can do this: > -- low-level primitive that uses pointer equality behind the scenes > compareAndSwap# :: IORef a -> a -> a -> IO Bool > atomicModifyIORef p f = do > a <- readIORef p > let r = f a > let aNew = fst r > ok <- compareAndSwap# p a aNew > if ok > then return (snd r) > else atomicModifyIORef p f This loops until compareAndSwap# succeeds and is a simple lock-free implementation. But what if f takes a long time to run? In a strict language, if there was contention on p, it's likely that atomicModifyIORef never finishes executing due to starvation! But since Haskell is lazy, each attempt to modify p is a constant-time operation! We just allocate thunks for "r" and "aNew" and do the compare-and-swap. Now, the responsibility for executing f is shifted to anyone who reads from the IORef; they get a thunk. It's likely that this thread will do so, as the value returned by atomicModifyIORef depends on f executing, but if this thread gets suspended or there is contention, the next reader can pick up the slack! In fact, at the low level we can improve this further; we can build the thunks for "r" and "aNew" with a hole to put the value we read out of the IORef; the inner loop then looks like this: > a <- readIORef p > update thunk hole in "r" with "a" > ok <- compareAndSwap# p a aNew which compiles down to just a pointer read, assignment, and CAS instruction. This blew my mind; from the "imperative, strict" point of view, this sort of operation is impossible to do reasonably, and here in Haskell we can get a great "probability of success"; the "critical section" where we have to loop if someone else modified the value behind our back is just a few instructions long! -- ryan

1 0

[Haskell-cafe] Object-oriented programming, Haskell and existentials
by oleg＠okmij.org 16 Oct '08

16 Oct '08

Lennart Augustsson wrote: > I was just pointing out that the mechanism for doing the OO thing > exists in Haskell too, albeit looking a little different. Indeed there is a mechanism for doing OO in Haskell -- several of them. Most of them have nothing to do with Existentials. In the OHaskell paper, http://homepages.cwi.nl/~ralf/OOHaskell/ Ralf Laemmel has collected all known to us methods of doing OO in Haskell. Incidentally, three years ago Lennart Augustsson described a simple, Haskell98 method of emulating OO, without existentials. We give him credit in footnote 4. The OOHaskell paper then goes to demonstrate how to do *all* of the known OO in Haskell, with all its inherent complexity: depth and width subtyping, upcasting and safe downcasting, nominal and structural subtyping, and the whole issue about covariant methods. Derek Elkins wrote: > In general, to encode OO you need quite a bit more than existentials. > As you are probably aware, there was a cottage industry in the mid to > late '90s working on encodings of OO languages into System F + foo > calculi. They just about gave up on a complete encoding until someone > figured one out. 'turns out all you needed was recursive bounded > existential quantification. Not necessarily. Again, please see the OOHaskell paper. The full story is that there are several encodings of objects -- using closures and using existentials. The former are *far* simpler. ML-ART (which later evolved in the 'O' of OCaml) chose the more complex encoding -- and hence had to add equi-recursive types, existentials and universals to Caml -- only because of a potential safety issue with closures. A constructor of an object may invoke methods that may access fields that are not initialized yet. This problem is present in all OO languages, and the common `solution' is an admonition ``not to do that''. Clearly Didier Remy has higher standards, and he went into considerable pain to solve the problem. Incidentally, Haskell can solve this problem in a simpler way. We critically rely on the fact that all effects must be done in a monad. Therefore, in OOHaskell we can safely use the simpler encoding for objects. Regarding existentials, the web page http://okmij.org/ftp/Computation/Existentials.html demonstrates how to systematically eliminate existentials. In fact, the object encoding via existentials can be easily transformed into the encoding that uses only simple, first-order types. The web page begs a question if there is ever any real need for existentials.

5 6

Re: What I wish someone had told me...
by John Lato 16 Oct '08

16 Oct '08

I'd like to thank everyone who replied to my OP, and also perhaps clarify one point. I wasn't trying to be argumentative or negative about any work people have done to make Haskell approachable for OO programmers (or any other programmers, for that matter). I simply wanted to know what others thought about one item that was misleading to me in particular, and to see if others either agreed with me or had similar experiences. That being said, I know that it's a great deal of work to put together a useful tutorial, and I appreciate every one I read. Especially the monad tutorials, of which it took a half dozen before I got it. Best, John

7 6

Writing a function isPrime using recursion.
by Kalashnikov 16 Oct '08

16 Oct '08

I'm supposed to write a function isPrime that checks whether or not a given integer is a prime number or not. The function has to use recursion. The only advice I was given, was to use a helper function. I still have no clue how to do it :confused: I'm new to Haskell by the way..please help.. -- View this message in context: http://www.nabble.com/Writing-a-function-isPrime-using-recursion.-tp2000330… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

3 2

ANN: hledger 0.1, command-line accounting tool
by Simon Michael 15 Oct '08

15 Oct '08

I'm pleased to announce the first release of hledger, a command-line accounting tool similar to John Wiegley's c++ ledger. hledger generates simple ledger-compatible transaction & account balance reports from a plain text ledger file. It's simple to use, at least for techies. This has been my "learning Haskell" project, but I think it's also useful. It is much less featureful than ledger, and not quite as fast, but it has the virtue of being fun for haskellers to hack on. I am documenting the code, the app is simple, and I'm not too far up the haskell learning curve, so I think other people learning haskell might enjoy a look. It is currently ~1100 lines of haskell excluding tests. home: http://joyful.com/Ledger#hledger hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hledger-0.1 darcsweb: http://joyful.com/darcsweb/darcsweb.cgi?r=hledger darcs 2 repo: http://joyful.com/repos/hledger haddock: http://joyful.com/repos/hledger/api-doc/ ledger home: http://newartisans.com/software/ledger.html ledger manual (recommended): http://github.com/jwiegley/ledger/tree/master/doc/ledger.texi My thanks to John Wiegley for help with compatibility and for his very useful ledger tool. I use it (and now, both of them) daily to track time and money. This is of course a hot topic around our planet. I hope you find it useful or intriguing. Patches and feedback welcome! Best, -Simon

3 3