- Haskell-Cafe - Haskell.org

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 16 Oct '08

16 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

Improving MTL instances (was: Overlapping/Incoherent instances)
by Ryan Ingram 16 Oct '08

16 Oct '08

On Mon, Oct 13, 2008 at 2:04 AM, J. Garrett Morris <jgmorris(a)cecs.pdx.edu> wrote: > Indeed - MTL seems to have been rewritten at some point in the past to > prefer exhaustive enumeration to overlap. Indeed, and I actually think this is a weakness of the current implementation. Anyone who comes up with a new transformer that provides different functionality than what is there needs to explicitly provide all the relevant instances, instead of letting MonadTrans do its thing. Consider MonadPrompt (shameless plug, it's on hackage!) In order to be fully interoperable with the MTL I'd need to write instances for MonadState, MonadReader, MonadWriter, MonadError, and MonadCont for PromptT. These are unavoidable, although for monads with a "simple enough" interface, such as State, everything can be accomplished with "lift". But I also need to provide the same boilerplate instances for every other monad transformer in the package to give them instances of MonadPrompt. And MonadPrompt *does* have a "simple enough" interface that it could be accomplished trivially with "lift". And this ignores interacting with any other transformer library! Anyone who uses MonadPrompt along with another transformer (like DatabaseT in the PostgreSQL library) needs to write any instances they care about themselves, which adds to the difficulty in using the libraries together. Of course, the point of this message isn't just to complain. The overlap implementation was abhorrent and it *is* better now than it was before. But perhaps there is an abstraction we are missing that would allow for better interoperability. For example, the type-compose library documentation at http://haskell.org/haskellwiki/TypeCompose mentions that (f :. g) is an applicative functor if both f and g are applicative functors, which means there is a generic "transformer" for all applicative functors! The presense of >>=/join for monads make this more difficult, although there is the "product" definition: > newtype Product m n a = Prod { runProd :: m (Either a (Product n m a)) } which handles nesting joins by just nesting the monads recursively. But in this case it is up to the user to figure out how to untangle the spaghetti created, so that's no good. So, does anyone have any good ideas for improving the interoperability of MTL? -- ryan

9 8

Flexible instances
by George Pollard 15 Oct '08

15 Oct '08

I'm a little confused. Why is this allowed: > data Blah = Blah > > instance Eq Blah where > x == y = True But not this: > class Stringable a where > toString :: a -> String > > instance Stringable [Char] where > toString = id (Resulting in:) > Illegal instance declaration for `Stringable [Char]' > (All instance types must be of the form (T a1 ... an) > where a1 ... an are distinct type *variables* > Use -XFlexibleInstances if you want to disable this.) > In the instance declaration for `Stringable [Char]' 'Blah' isn't a type variable, is it? Is my brain just not working right today?

9 9

Very silly
by Andrew Coppin 15 Oct '08

15 Oct '08

{-# LANGUAGE FlexibleInstances #-} module Overload where class Silly s where go :: s instance Silly ([x] -> [x]) where go = reverse instance Silly (Int -> Int) where go = (+1) Don't even ask. Suffice it to say, you *can* make Haskell support arbitrary overloading of function names like C++ has, _if_ you abuse the type system violently enough. Please, won't somebody think of the children?!?

9 13

Cairo and dialog oddities on Windows using glade.
by Jefferson Heard 15 Oct '08

15 Oct '08

Maybe I'm doing something wrong. I've created several dialog boxes in Glade, and I'm calling Gtk.runDialog on them when a user clicks the mouse in my main window. On Linux, they work mostly right, but the insertion point never shows in the Gtk.Entry areas and the dialog itself comes up without any decoration. In Windows, I cannot edit the Entry areas at all. I can click on the action buttons I added with Gtk.Dialog.addButton. Also, I'm getting an (Invalid matrix (matrix not invertible)) error from Cairo in WIndows that I'm not getting in Linux, and all I can think is that occasionally a rectangle width could be negative. Would that cause the error? -- I try to take things like a crow; war and chaos don't always ruin a picnic, they just mean you have to be careful what you swallow. -- Jessica Edwards

1 0

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

15 Oct '08

> Albet Lai wrote: > John Lato wrote: >> Are you advocating introducing existential types to beginning >> Haskellers? I think something with the scary name "existential >> quantification" would greatly increase the head'splodin' on the >> learnin' slope. > > OOP(*) advocates introducing existential types to beginning programmers. Yes, because they're required to get almost anything done in OOP languages. In general they are not required in Haskell. I got a bit carried away with rhetorical flourish, but my point wasn't so much that beginners couldn't understand something as that something with such specialized usage isn't necessary for new Haskellers, and is likely to encourage bad habits from OOP-converts. > > The broken analogy between OOP interfaces and Haskell/Isabell type > classes is there because some people insist that all languages should be > like mainstream languages. You have heard it, even from reputable > leaders and pioneers: "if you know one language, picking up others > should be easy, they just differ in syntax". > I have heard it, and I used to believe it. Now I think it's only true provided the one language you know is suitably advanced (and currently non-existent, I think). John

2 1