Simple Observers in Haskell

I’ve just uploaded version 0.0.1 of the simple-observer package to hackage, the Haskell package repository.

This is an implementation of the Observer design pattern in Haskell. I am not the originator or even main author of the code in this package; that is Dutch computer scientist Bastiaan Heeren, who wrote the original as part of an exercise for some students. But recently I was doing some GUI programming with wxHaskell (which I’ve found to be great, by the way) and found myself hankering for an observer or something MVC-ish, and my googling led me to his code. I used it, and then thought it might be worth releasing to the world at large — particular as it’s not wx-specific, or even GUI-specific, really. Bastiaan tells me he’s happy for me to do so, so here it is. I’ve changed names, separated it into two modules, and replaced IORef with MVars in order to better support multi-threaded use — but at heart it’s identical to Bastiaan’s code.

The basic idea is that an observable is a piece of mutable state, and when it’s changed, a list of observer functions are called in sequence, and passed the new value. For wx programming – which is anyway quite stateful and not very idiomatically functional – I’ve found it to be quite effective. Here’s a small example which illustrates basic use…

My GUI has a start/stop button, which toggles a running flag. When running is true, the button says “stop”, and certain things happen in the app’s idle handler (to run whatever is supposed to be running); when running is false, the button says “start”, and certain other things happen in the app’s idle handler. So here’s how we set it up:

In my app’s setup phase, I create running, which is initially false, using createSub :: a -> IO (Sub a):

    running <- createSub False

Later on (actually in a different function, which receives running as a parameter), I create the start/stop button and use running‘s current value to initialise its appearance:

     r <- getValue running
     btnRunStop <- button p [text := runStopBtnTxt r, on command := runStopClicked running]

Here, runStopBtnTxt :: Bool -> String just returns “start” or “stop” appropriately. We use it elsewhere, which is why it’s factored out. When the button is clicked, runStopClicked toggles the state of running (and does other stuff not shown here):

    runStopClicked :: Sub Bool -> -> IO ()
    runStopClicked running = do r <- getValue running
                                running `setValue` not r

(This would actually be neater using changeValue :: Sub a -> (a -> a) -> IO (), but in the real version I use r later on, so this I need the getValue anyway.)

So this setValue call will cause all of running‘s observers to be called with not r. The last thing we should do, then, is attach an observer:

    addObserver running (\x -> btnRunStop `set` [text := runStopBtnTxt x])

addObserver :: Sub a -> (a -> IO ()) -> IO () takes an observable subject and an observer function, and attaches that function to the subject’s list of observers. Here, the observer function just updates the text.

(It’s worth noting that the observer’s type is a -> IO () not Sub a -> IO () — i.e. observers receive values, not subjects. The subtext is that an observer shouldn’t modify the subject it’s observing, lest ye loop infinitely; you can get round this by passing the subject proper as an earlier argument, and provided it used setValue' not setValue you’d be fine — but I don’t know of any reason why you’d want to do this.)

The first win here is that the button’s on command function doesn’t need the button as a parameter, because it’s not directly updating the button text. The deeper win is relatively cheap and clean separation of concerns: the button only toggles the running value, and (separately) stuff happens when running changes. If some other mechanism (eg some network event) could also cause running to change, we’d already be dealing with it The Right Way: just add another observer. Without observers, if our reaction code was in the button’s on command handler, we’d need to call that, or factor the reaction code out, in order to deal with it then. This way’s clearly nicer. But hey, you’re reading a blog post containing type signatures, so I presumably don’t really need to explain separation of concerns, or the observer pattern, to you. :-)

I’m aware that there are more sophisticated approaches to this problem. I’m reliably informed that Functional Reactive Programming (FRP) subsumes observer quite naturally, but I don’t understand it enough to comment. Tom Lokhorst tells us that Erik Meijer & Co. at Microsoft have a good handle on this, as discussed in this entertaining video. Alternatively, if we like message-passing as our basic computational model, an implementation in CHP might be just the ticket — and that certainly looks like an impressively powerful approach. However, in my case, I wanted to keep things in a single thread as much as possible, because Haskell’s GUI frameworks (and indeed wx across all languages?) seem to interact with multi-threading in non-simple manners. This is also pretty much why I decided against implementing Neil Brown’s suggestion that the observers should be run in their own threads. Of course, if an observer wants to fork a thread, it absolutely can, and I may find myself doing this in my app soon — but I didn’t quite see the utility of baking it in. That’s probably my sequential imperative background showing through, and hopefully one day I’ll shake it off and welcome our new, multi-threaded masters. To conclude, everything mentioned in this paragraph is why I decided to release this as simple-observer.

Anyway, hopefully somebody will find this useful.

A Haskell shell for computing musical scales, in 58 lines of code.

On my way home from work I had an idea for something I thought I’d find handy. Two hours later, I’ve written it — in Haskell of course. :-)

Context: I occasionally make what might kindly be called music, using computers and the like, and I don’t have any formal musical training. Consequently, I sometimes run into trouble regarding keys and scales. The idea I had was for something which would tell me, given a set of notes (ie the ones I’ve already used in a piece), what scales those notes are in — and consequently what other notes might also fit well with them. Long ago when I used Bars & Pipes on the Amiga, it had a tool for doing this. I could buy one for my Mac for about 8UKP (I may yet — it has a pretty GUI, which I might not be bothered to do), but it seemed I should be able to knock something up. The data types aren’t exactly complicated.

So I did it. I’ll put the code at the end of this post, or you can easily download it from here, in 133 lines of literate Haskell (58 lines of actual code). Here’s a screenshot showing typical use:

Haskell scale finder screenshot

Once again, I’ve been super impressed by how easy Haskell made this — and I’m particularly loving the Shellac library which gives me an interactive shell with history and graceful recovery from errors — all in 4 lines of code!

> react = mapM_ (uncurry printScale) . checkFit . parseNotes
>     where printScale :: String -> [Note] -> Sh () ()
>           printScale n ns = shellPutStrLn (n ++ ": " ++ ppNotes ns)
> main = runShell (mkShellDescription [] react) haskelineBackend ()

OK, I’m not using any of its juicier features like completion, state, automatic help, etc., but even so, it’s a great little library.

I could wrap it in a GUI, but to be honest, this’ll probably do the trick for me, assuming I haven’t made any big screw-ups, or got the scale definitions wrong. If anyone’s looking for a minimal Shellac example, maybe it’ll be useful.

(Update 2009-09-16 13:37: To get this up and running, if you’re not already a Haskeller, the following should suffice: 1. Download and install The Haskell Platform – nice ‘n’ easy. 2. Open a shell and issue cabal install Shellac-haskeline or possibly sudo cabal install --global Shellac-haskeline. 3. Download the code (from hpaste.org) and (still in a shell) issue ghci Scales, and when that’s loaded issue main. Or if you want to compile an executable, try ghc --make -main-is Scale.lhs Scale.lhs, just like in the screenshot. That should do it — I’d love to know if I’ve missed anything and/or if that works!)

Here’s the code (but, again, it’s prettier and easier to download from hpaste):

Read the rest of this entry »

A “Monte Hall” problem solved in Haskell

I’ve just written a solution to today’s Programming Praxis puzzle, which requires you, essentially, to write a Monte Carlo attack on the Monty Hall problem. Thus, the awful pun in this post’s title, in case you missed it. ;-)

Here’s my solution.

It was a lot of fun. I started out feeling like I should be able to do it, but not quite knowing what direction to take, so first of all I was writing some data types for things like Door = Car | Goat, etc. but pretty quickly realised it was just a matter of door numbers. My first working solution was actually a bit longer, because of some intermediate steps (for example the first thing I figured out, in its own function, was how to compute which goat door would get shown to the player given a (car, choice) pair). Then hlint gave me a couple of hints, like using replicateM, and I compacted it down to what we see here. I’m sure it has naive aspects, but I’m pretty happy with it — and I’m loving doing the Praxis problems.

Creating/consuming JSON in Haskell, with the help of pattern guards

I’m going to write about two Haskell things I’ve used today, both of which were new to me: first, creating/consuming JSON using Sigbjorn Finne‘s json library; second, using pattern guards to make the “consuming” part prettier than my first butt-ugly attempts.

Earlier today I googled a bit looking for examples of using the JSON library, but didn’t find any clear or immediately useful ones. There were a few examples of people rolling their own JSON stuff in Haskell, but obviously that wasn’t what I was after. (I’ve just noticed that Real World Haskell talks about JSON, but doesn’t appear to immediately answer my questions — though there is loads of good stuff there of course.) I just wanted something to get me going quickly with the problem at hand, really.

The context is this: I’m working on some code which represents models of devices’ user interfaces as finite automata and tries to do some analysis on that. I want to use JSON to pump FA models between implementations in at least two, and maybe more, languages. None of that is really relevant to the rest of this post, except perhaps in the next paragraph. :-)

I have an abstract data type representing what I call actions, which are essentially lists of transitions, which are just integers (the destination state). Actions may be deterministic (in which case each transition is just an integer) or nondeterministic (then each transition is a list of integers). Again, the meaning isn’t so important; what’s important is that my ADT looks like this:

data Action = DAction [Int] | NAction [[Int]]
  deriving (Eq, Ord, Show)

Now, having imported the appropriate JSON module…

import Text.JSON

… I need to make this type an instance of the JSON type class by defining showJSON and readJSON functions for creating and consuming JSON, respectively:

instance JSON Action where
    showJSON (DAction xs) = showJSON ("DAction", xs)
    showJSON (NAction xs) = showJSON ("NAction", xs)
    readJSON = Error "not yet implemented" -- See below!

Let’s start by thinking about showJSON. It’s important to note that showJSON doesn’t produce a serialised JSON string directly. Instead, there’s an intermediate representation: the JSValue ADT; you serialise values of that type using the JSON module’s encode or encodeStrict functions. This extra layer of abstraction is a big win, because when we’re consuming JSON, we don’t have to write any code to parse the serialised string: we just call decode (or decodeStrict) to turn the string (whose contents should never be very exotic: that’s the whole point) into a JSValue. Then, readJSON‘s job is to turn that JSValue back into our domain-specific representation, whatever that is. That was the bit I was having trouble with (which is why I haven’t shown it yet), but I recognise that doing it this way was a lot easier than parsing the serialised string representation would have been, so I’m thankful for the extra abstraction layer.

In my case (and, I suspect, in most), showJSON is rather straightforward, thanks to some already-existing JSON type class instances. I simply construct a pair whose first element is a string identifying the action type, and whose second element is the action’s transition list. The JSON module already defines instances of the JSON type class for pairs, Strings, lists, and Ints, so the corresponding showJSON functions (which I’ve never seen) do all the work for me. Win.

Time for an example; let’s define a simple Action value…

da :: Action
da = DAction [0,1,2]

and take a look at its JSValue and string representations in ghci:

*Data.FA.JSON> showJSON da
JSArray [JSString (JSONString {fromJSString = "DAction"}),JSArray [JSRational (0%1),JSRational (1%1),JSRational (2%1)]]
*Data.FA.JSON> putStrLn $ encode $ showJSON da
["DAction",[0,1,2]]

The JSValue is quite verbose, but if you compare it with the encoded string, you can comprehend its structure easily enough. JSON doesn’t have tuples, so the pair we fed showJSON has been turned into a two-element list (a JSArray). The string “DAction” is wrapped in a JSONString (a more efficient representation of String) inside a JSString constructor. The list of integers is a JSArray, but each Int is represented as a Rational: the JSON module doesn’t know how to serialise integers directly (AFAICS JSON can, in general?)

So far, so good: serialising my data structure to JSON is pretty easy. Lists of Actions, maps from Ints to Actions, etc. all “just work” too, out of the box: handy.

Extraction of an Action from a JSValue is trickier, and I am by no means confident that I’m doing it in the most sensible manner — though what I’m doing does work, at least! The type signature of readJSON is:

readJSON :: JSValue -> Result a

where Result is a bit like Maybe or Either: it’s either Ok a (it worked) or Error String (fail!). readJSON takes a JSValue, and depending on what the contents of our decoded JSON string were, this could be pretty much anything! So we have a pseudo-parsing situation: we need to match it against what we’re expecting, and if it doesn’t fit, we raise an error. In other words, we have to unpack it, layer by layer. Here’s what I came up with initially:

readJSONAction' :: JSValue -> Result Action
readJSONAction' value =
    case value of
      JSArray [a,b] ->
          case a of
            JSString jsTag -> 
                case (fromJSString jsTag) of
                  "DAction" ->
                    case (readJSONs b)::Result [Int] of
                      Ok xs -> Ok (DAction xs)
                      _ -> Error "can't decode deterministic actions"
                  "NAction" ->
                    case (readJSONs b)::Result [[Int]] of
                      Ok xs -> Ok (NAction xs)
                      _ -> Error "can't decode nondeterministic actions"
                  _ -> Error "Incorrect action tag"
            _ -> Error "can't decode action tag"
      _ -> Error "not an action" 

It sure does look ugly, as you’ll no doubt agree. It unpacks the JSValue bit by bit, using a case distinction to catch unexpected content, which is translated into an Error value. Note the explicit type-tagging in the deeply-nested calls to readJSONs: there are many instances of readJSONs and we need to be explicit about which one we want to call — and they’re different for the two different kinds of action.

This works…

*Data.FA.JSON> readJSON (showJSON da) :: Result Action
Ok (DAction [0,1,2])

… (again, we need to explicitl specify which readJSON we want), but it’s ugly as hell. My friend and colleage pwb suggested “pattern guards might make it prettier”. So I checked them out, and came up with this:

readJSONAction :: JSValue -> Result Action
readJSONAction value
  | JSArray [a,b] <- value
  , JSString jsTag <- a = checkContents jsTag b
  | otherwise = Error "not an action"
    where checkContents tag cargo
              | "DAction" <- (fromJSString tag)
              , Ok xs <- ((readJSONs cargo)::Result [Int])
                      = Ok (DAction xs)
              | "NAction" <- (fromJSString tag)
              , Ok xs <- ((readJSONs cargo)::Result [[Int]])
                      = Ok (NAction xs)
              | otherwise = Error "not an action"

The main disadvantage over the previous version is that we get less detailed error messages, but I think I can live with that for more readable code. It’s still fairly ugly though, and I’m not 100% sure why I need to break out the checkContents part (I did write it in a hurry).

I just can’t shake the nagging suspicion that I’m missing some clever and elegant way of doing this. So if anyone has any pointers, I’d love to hear them. Otherwise, I can at least testify that the above techniques work: maybe that’ll be useful for another JSON adventurer in a hurry, one day. :-)

Neil Mitchell on F# from a Haskell perspective

Neil Mitchell on the F# language [dons].

Arrows in JavaScript

Arrows in JavaScript.

Arrows generalise computation schemes from the sequential version provided by monads, and are thus hard to bend one’s head around. It’s interesting to see them in JS.

SPJ/Haskell interview in Australian Computerworld

Simon Peyton Jones interview in Australian Computerworld [via galois].

A nice interview discussing various aspects of the history and philosophy of Haskell. SPJ sees purity, monads, and type classes as Haskell’s key aspects, and mentions a number of interesting other ideas along the way (along with uniqueness typing as seen in Clean, and functional reactive animation, which I first came across back when I was investigating music in Haskell).

More generally, this looks like a good series to keep an eye on: also contains interviews on Forth, JavaScript, Lua and other more boring languages such as C++. Shame there’s no obvious feed.

Why functional programming?

Because it will warp your mind [raganwald].

So I’m here to say that mindwarp #3 is discovering the function as the basic unit of abstraction. Jaw-droppingly beautiful abstractions and generalizations can be created out of just functions. You can rediscover the usefulness of partial functions and currying, which were techniques created in the 1800s. You can be in the direct lineage of Alan Turing, who used higher order functions in the 1930s to define his theoretical Turing Machine in his paper “On Computable Numbers, with an Application to the Entscheidungsproblem.” And you can finally understand recursion in a deep and intuitive way, and you’ll feel like you’ve looked into the abyss and somehow come back to tell everyone else about it. And maybe, just maybe, you can explain to me what a freakin’ monad is.

Word.

Slide40 – presentations with 8 bit style

Slide40 example slide

From the same good people who brought you the lambda calculcus in a can [ultimate].

On the relative positions of C and Haskell on the Mohs scale

C isn’t hard; programming in C is hard. On the other hand: Haskell is hard, but programming in Haskell is easy.

Seen on this thread.

More infinite list tomfoolery in Haskell

More infinite list tomfoolery in Haskell — the one for pi’s particularly “WTF?”.

Monads and the meaning of imperative language – also, some musing

Monads and the meaning of imperative language — the delicious alpheccar does a lovely job of introducing denotational semantics without saying enough to scare you off, and shows how exceptions (or even assert) in imperative languages are, at bottom, the Maybe monad. This point generalises (apparently – I know enough to believe it could be true, but not enough to assert that it isn’t untrue) to “any formal description of control flow in an imperative language will be monadic in nature.” Gorgeous.

The stuff about defining domains (and that being the hard part) is resonating with me just now; I’ve spent the day nailing down definitions of sets describing a particular aspect of my pet specification language, CspCASL, and it’s not trivial. And this is the easy part: not proper “domains”, just sets without much internal structure. Markus does that, for the model semantics. Anyway, yay language design.

Formally describing languages is hard. That’s why it doesn’t happen much yet, which is one reason our current languages situation is so messy. My hand-waving prediction: it’s hard but not intractable, and we’re getting better and better at it; in time it’ll be a sufficiently managable problem, with sufficiently good tool support, that languages which aren’t formally described will stagnate in comparison to the new languages then appearing. Naturally, from where I’m standing I see the increasing convergance of computer languages (sounds like a dumbing-down term but I’m really just trying to cover both programming and specification) with full-blown mathematical logic in all its various and colourful forms. Mathematics is the language for describing things formally; a computer program is by necessity a formal description of something, therefore this convergance seems like it will be a good thing – again, from where I’m standing. Whether or not it appears that way because where I’m standing is a good place to get a view of what’s going on, or just because that’s all you can see from here, remains to be seen. ;-)

Why Haskell is Good for Embedded Domain Specific Languages

Why Haskell is Good for Embedded Domain Specific Languages — nice summary, I’d say.

A pragmatic look at monads in Haskell

(Within an hour or two of publishing this, it was pointed out to me that this talk is really about the IO monad rather than monads in general, and that in particular the assertion that a monad represents a computation which performs a side-effect is not, in general true. A nice example is the Maybe monad. So a better title for this talk is “A pragmatic look at monadic I/O in Haskell”.)

A pragmatic look at monads in Haskell (PDF, 293KB) – slides from a talk I gave last Friday in Swansea University’s Computer Science department, as part of our “No Grownups” series of non-research talks given for and by postgraduate students.

The aim of the talk was to explain monads to a non-expert (and, largely, non-Haskell-programming) audience: why do we have them, what problems do they solve, and how are they used? The approach is pragmatic in that the talk explicitly does not go into technical details, instead focusing on a broad understanding, and on some specific useful “rules of thumb” for programming with monads in Haskell. I don’t claim to be an expert on monads or to have produced a talk which is authoritative or even necessarily completely correct. I do hope to have produced something reasonably comprehensible and useful, however. I would welcome any feedback, comments, corrections, clarifications, etc.

The talk was filmed, but I don’t know if my delivery was good enough to warrant putting it online. :-) Let me know if you’re interested. The post-talk discussion was quite useful, so it might be worth it for that. In particular, there was a question about when exactly the “non-purity” happens – when does referential transparency go away? My answer was that it happens when it needs to (ie when the result is required) and that yes, obviously somewhere there is some code which isn’t pure Haskell and which is doing the impure operation – eg an operating system call. Markus opined that a big part of the point of monads is to give us a clear indication, in the type system, that an operation is impure and thus, in some sense, unsafe/not nice. I thought that was a good enough point that I’ve since added a bullet saying that to the talk – but that’s the only addition I’ve made before publishing.

Background/reference material: A History of Haskell: being lazy with class (historical context), monads @ wikibooks (the nuclear waste metaphor), IO inside: down the rabbit’s hole (probably the point where I started understanding monads), rules for Haskell I/O (not an influence, but something with a similar flavour which I saw when I’d nearly finished), do-notation considered harmful (desugaring), monads on the unix shell (just because the dirty string “dramatisation” is so great).

Primes one-liner in Haskell – oh my!

mux on #haskell pasted what is perhaps the most beautiful code I’ve ever seen in my life:

      <mux> > nubBy(((>1) .) . gcd) [2..]
<lambdabot>  [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,...

(Number two in an ongoing series of jaw-dropping Haskell one-liners which began with the fibonacci series.)

Haskell packages gotcha: global vs. per-user package databases

This morning, I was having a problem involving Haskell’s Cabal build system. Since it’s something which could conceivably affect others, and since googling on the error text didn’t help me, I’m going to report my experience for the benefit of future travellers/googlers.

I was trying to (re)build xmonad, and got the following error:

[gimbo@orb xmonad] runghc -v Setup configure 
   Could not find module `Distribution.Simple':
       Use -v to see a list of the files searched for.
Read the rest of this entry »

Python-style string split (and strip / trim) in Haskell

Haskell’s an incredible language but I’m repeatedly struck by (what I perceive as) gaps in its standard libraries (though as proven yesterday I could know them better). For example, there aren’t any cross-platform file path manipulation routines in the style of python’s os.path (though not for long, thanks to Neil Mitchell). Another lacking area seems to be string manipulation.

Today, I needed to split a string up according to some token, where that token is itself a string, not a single character. Thus, a split in the style of python’s strings’ built in split() method. That is, I wanted to be able to do this:

*StringSplit> split ", " "one, two, three, four"
["one","two","three","four"]
*StringSplit> split "an" "banana"
["b","","a"]

To my amazement, this isn’t a standard library function, and I couldn’t find hundreds of examples of how to do it via google. I couldn’t even find one! I could find a number of variants where the token is just a single Char, usually utilising takeWhile and the like. Gladly this led me to a reasonable (I hope) solution. This example splits on Chars but in the comments I was introduced to unfoldr, which looked tantalisingly close to what I wanted. All I needed to do now was write the function unfoldr calls. About half an hour and much hoogling later, hey pesto:

module StringSplit where

import List

-- | String split in style of python string.split()
split :: String -> String -> [String]
split tok splitme = unfoldr (sp1 tok) splitme
    where sp1 _ "" = Nothing
          sp1 t s = case find (t `isSuffixOf`) (inits s) of
                      Nothing -> Just (s, "")
                      Just p -> Just (take ((length p) - (length t)) p,
                                      drop (length p) s)

All of the complexity is in sp1 (short for “split once”), which performs a single split. sp1‘s type is String -> String -> Maybe (String, String); the section (sp1 tok) then has the right type for unfoldr (sections just seem to be cropping up everywhere lately, eh?). The point of sp1 is to split s at the first occurrence of t. It does this by using inits to build all prefices of s and finding the first one having t as a suffix. If found, it splits the string at the token, throws the token away, and return the (before, after) pair. If the token isn’t found, it just returns s paired with an empty string; that gets passed by unfoldr to sp1 on the next call, causing sp1 to return Nothing, causing unfoldr to finish – whew!

That last bit sounds a bit complicated, but it was necessary to fix a bug present in my first implementation of sp1:

sp1' t s = case find (t `isSuffixOf`) (inits s) of
               Nothing -> Nothing
               Just p -> Just (take ((length p) - (length t)) p,
                               drop (length p) s)

This misses the final substring, so split "n" "banana" would return ["ba", "a"] instead of ["ba", "a", "a"]. Hence the whole empty string/Nothing/stop machinery.

I could not have written this code two weeks ago, I think. Thus, I’m sure there are better ways to do this, and would love to hear them – and any criticism. I was a wee bit worried about using inits and find in this way for finding a substring (no standard substring function?). Haskell’s lazy nature ought to help me here though: inits will only build the entire list of prefices if t isn’t in s at all. For anything I’m planning to use this for, it ought to be fine; it’s probably not the best general way to do it though.

Postscript

For good measure, since I had to implement it later that evening, here’s a string.strip() (aka trim):

strip :: String -> String
strip s = dropWhile ws $ reverse $ dropWhile ws $ reverse s
    where ws = (`elem` [' ', '\n', '\t', '\r'])

I’m particularly proud of the ws part. :-) Look at me, all full of Haskell pride. ;-)

Postpostscript

I realised I can generalise split beyond strings, to work on lists of anything of class Eq:

-- | A function inspired by python's string.split().  A list is split
-- on a separator which is itself a list (not a single element).
split :: Eq a => [a] -> [a] -> [[a]]
split tok splitme = unfoldr (sp1 tok) splitme
    where sp1 _ [] = Nothing
          sp1 t s = case find (t `isSuffixOf`) $ (inits s) of
                      Nothing -> Just (s, [])
                      Just p -> Just (take (length p - length t) p,
                                      drop (length p) s)
*StringSplit> split [2,3] [1,2,3,4,3,2,1,2,3,4]
[[1],[4,3,2,1],[4]]

More playing with sections (and flip) in haskell

Last week I wrote about sections in Haskell, and discovered flip. Today I hit upon a problem which got me thinking about them again, leading to one of those wonderful moments when Stuff You Just Learnt turns out to be exactly what you need to solve the problem you’ve got right now. (Then you blog about it and find an Even Better Way, as it turns out.)

I’ve been writing some file-manipulation code, and along the way had written the following function:

-- | Check if a given string (subject) ends with another (target).
endswith :: String -> String -> Bool
endswith sub tgt = drop (length sub - length tgt) sub == tgt

(Actually I’ve forgotten now whether I wrote this myself or found it somewhere, but it’s clearly not a new problem. If anyone knows a source for the above code, please do tell so I can attribute it. Anyway…)

So then you can do:

*Ew> endswith "banana" "na"
True
*Ew> endswith "banana" "moo"
False

So far so good. Later, I had a list of filenames, and I wanted to filter it down to just those ending with a particular suffix. Initially, unthinkingly, I tried:

*Ew> filter (endswith "na") ["banana", "cat", "iguana", "mastodon"]
[]

Spot the cunning use of a section. Actually not so cunning, as it turns out – the empty list is not the result I was hoping for! The problem is that the first parameter of endswith is the subject (the string to be searched) not the target (the string to be searched for) so the section (endswith "na") is not the function which checks if a string ends with “na”. It’s the function which, given a string, checks if “na” ends in that string:

*Ew> (endswith "na") "banana"
False
*Ew> (endswith "na") "a"
True
*Ew> (endswith "na") "na"
True

My first reaction was to just swap the parameters around. Let’s call this version endswith'. It’s exactly the same as endswith except for the parameter order:

endswith' :: String -> String -> Bool
endswith' tgt sub = drop (length sub - length tgt) sub == tgt

Then (endswith' "na") is the section I’m looking for, and in particular works as I want under filter:

*Ew> (endswith' "na") "banana"
True
*Ew> filter (endswith' "na") ["banana", "cat", "iguana", "mastodon"]
["banana","iguana"]

I only use endswith in a couple of places, so this change was totally viable. Lesson learnt (or so I thought): you have to think carefully about parameter order when writing functions, because some sections will be more useful than others. Obviously with endswith, the section with bound target is more generally useful than the section with bound subject.

Later, I realised this lesson is bogus, or at least not very strong. I mean, there’s probably something in it, but I didn’t actually have to swap the parameters to make my filter work. That’s exactly what flip does:

*Ew> ((flip endswith) "na") "banana"
True
*Ew> filter ((flip endswith) "na") ["banana", "cat", "iguana", "mastodon"]
["banana","iguana"]

What’s going on here? (flip endswith) is endswith with the parameters flipped. Thus ((flip endswith) "na") is exactly the same function as (endswith' "na") which, as we saw above, does what I want. So in the end, I didn’t have to replace endswith with endswith' to get my filter to work – I could just flip it. Bearing in mind I didn’t even know flip existed a week ago, I felt pretty smug to realise this. :-)

The next question on my mind is what you might call “generalised sections for multi-parameter functions”… If I have a 4-parameter function and I want to build a section where 2 of the parameters are bound (say), and it’s not the first two, how do I do it? Stupid toy example:

f :: Int -> Int -> Int -> Int -> Int
f a b c d = a + b + c + d

Can I make a section representing f with b fixed at 3, and d fixed at 5, say? I know I can do this:

g :: Int -> Int -> Int
g a c = f a 3 c d

but can we do it inline, as it were, as with the section approach? Answers on a postcard to the comments page, please! :-) I suspect currying‘s going to wind up in there somewhere…

Postscript

That’s all I originally intended to blog about; when chasing links to support this post, however, I read this and learnt two more interesting things.

First, someone has, of course, solved this problem already, and I can just use isSuffixOf to get this job done (Strings in haskell are Lists of Chars). So now I get to throw endswith away – w00t, less code. A fundamental lesson: once the language starts making sense, learn what’s in the standard libraries!

Second, thanks to Haskell’s ability to deal with functions in infix form, the section (isSuffixOf "na") can also be written as ("na" `isSuffixOf`) which is, I suppose, more natural (provided you’re not scared off by the backticks, which I’m trying not to be). Then we have:

*Ew> filter ("na" `isSuffixOf`) ["banana", "cat", "iguana", "mastodon"]
["banana","iguana"]

Sweet.

Playing with sections in Haskell

Consider the function (:) in Haskell…

Hugs> :t (:)
(:) :: a -> [a] -> [a]

So, (:) is a polymorphic function which takes an element of some type, and a list of elements of that type, and returns a list of elements of that type. In particular, it prepends the singleton element onto the list. For example:

Hugs> 'c' : "ello"
"cello"

Now for the fun part.

Hugs> :t ('c':)
('c' :) :: [Char] -> [Char]

Here, we see that ('c':) is a function which takes a list of characters (ie a string) and returns another one. As you might expect, it prepends it with a 'c':

Hugs> ('c':) "ello"
"cello"

('c':) is an example of a section: we “partially evaluate” a function by providing only some of its parameters, which yields a new function. Obviously this is only possible if we have higher-order functions in our language.

We can take the section “on the other side” of the :, and define the function which takes a character and prepends it onto the string "ello"

Hugs> (:"ello") 'c'
"cello"

What’s its type?

Hugs> :t (:"ello")
flip (:) "ello" :: Char -> [Char]

Interesting. The type is as we would expect (Char -> [Char]), but what’s this flip thing?

Hugs> :t flip
flip :: (a -> b -> c) -> b -> a -> c

So flip takes a function with type signature (a -> b -> c) and returns an equivalent function with type signature (b -> a -> c) – OK, simple enough. But why did hugs introduce it here, I wonder, though, why didn’t hugs just do what ghci does, and say:

Prelude> :t (:"ello")
(:"ello") :: Char -> [Char]

? I say: shrug.

In other news, I’ve just discovered Neil Mitchell’s Haskell blog. I met Neil at BCTCS 05 in Nottingham, and again at BCTCS 06 in Swansea (though at that time I felt like I was moving away from TCS). He’s a thoroughly nice bloke, and clearly knows considerably more about Haskell than I do, thus, a good blog to find. I enjoyed:

I think I was quite a bit less successful at explaining this one. The only way you can show sequence is not necessary is by writing an OS, a compiler, a web server etc in Haskell – all of which have been done. Unfortunately I only had a small piece of paper so couldn’t write any of those.

Neil Mitchell, “Describing Haskell to an Ada programmer”.

(The section saga continues here.

Monad wrangling, and the joy of #haskell

Three days ago, I enthused about the Python community, and what a great help to me they were back in the day.

These days it’s Haskell that has my brain feeling too small, and I’ve just had my first experience of the Haskell community. I installed an IRC client for the first time in four years just so I could log on to the #haskell IRC channel. I’m happy to report that the experience was entirely positive.

For an imperative programmer, learning Haskell is initially hard because you have to stop thinking in terms of issuing instructions which will be performed in order, and start thinking in terms of composing pure functions (which have no side effects) together to Get Things Done. It’s weird at first, but ultimately very powerful, as it lends itself much more nicely to higher-order programming, lazy evaluation, actually composing programs out of reusable parts, etc. I’d say I’m starting to get a reasonable feel for that, although I’ve got a long way to go.

Unfortunately, a little later, you realise that there are cases where you need side-effects (eg input/output), which leads you into this whole sort-of-imperative side of Haskell, at the heart of which lie the hairy monad things. You totally can’t avoid this, because sooner or later you need to do I/O. Monadic I/O (and monads in general) look & feel imperative at first, but you soon hit barriers thinking like that, and ultimately really have to read stuff like The I/O Inside Tutorial, Tackling The Awkward Squad, etc. in order to understand what’s really going on, which is actually really clever, decidedly not imperative, and at some point turns into lambda calculus or category theory (take your pick).

It’s monads that I’ve been wrangling with lately. I’ve been trying to do a fairly simple I/O task: I have some directory containing some files; I want to operate on a subset of the files in that directory, for each of them reading the file and creating some data object representing its contents. The details aren’t important. Doing this in Python (say) is trivial. Doing it in Haskell has had me stuck for nearly a week. :-) I spent all day last Friday working through “I/O Inside”, and now understand monads much better than I did, and maybe half as well as I should (but maybe not even). That was all very informative and educational, but still didn’t answer my problem.

Anyway, long story short, tonight I installed an IRC client, went on #haskell, asked the question, and got an answer immediately and in a wonderfully friendly fashion. Full #haskell chat log for today is here if anyone’s interested, but in essence it turns out that mapM is what I need for this task. Sweet, and actually incredibly simple when you know it. I think a lot of Haskell is like that…

By the way, the #haskell channel has this neato lambdabot running, which among other handy functions, remembers and repeats amusing/apposite quotes when instructed to do so. Given the sad theory geek that I am becoming, this quote it kicked up tonight made me chortle:

Binkley: the sex is all in the operational semantics, denotational semantics only deals with love.

vincenz, 14:41:22

The Quest of the Algorithm of the Chimes of the Bells of the Clock of the Long Now

I’m on a bit of a quest at the moment, which is turning up all sorts of interesting bits and bobs (and distracting me nicely from the work I should be doing today).

Yesterday I listened for the first time to Danny Hillis‘ 2004 Long Now seminar on “Progress on the 10,000 Year Clock” (listen here). Like most of these seminars (which I really should write about in more detail some time) it’s well worth a listen, bristling with neato facts, insights, and mind-expanding ideas. (A less time-consuming but still usefully detailed introduction to the clock project can be found here.) One of the things which particularly caught my imagination was the discussion of the bells. Apparently His Enoship noticed that the number of days in 10,000 years is almost exactly equal to the number of permutations of ten things (365 x10000 = 3650000; 10! = 3628800) – so the idea is that once per day these ten bells will chime in a certain order, never heard before, never to be heard again. (Eno has released a CD of “bell studies”, which is on its way to me even as I type.) Hillis invented an algorithm for the ordering of the chimes, so we know what ordering will be played for any day in the next 10,000 years (Eno’s CD plays the sequences for January 7003) and as you’d expect, people have run with this idea. I have an itch to run with it too, probably (predictably) in Haskell.

So where’s the algorithm? I haven’t found it yet, to my great surprise. :) I would have expected it to be fairly easily available, but apparently not. It might be in Stewart Brand’s book about the clock (also on its way to me), but I sure don’t see it anywhere online. However, there are a couple of implementations floating around, so perhaps some reverse engineering is in order…

Sean Burke has created a web page for exploring the bell patterns, with visualisations and MIDI downloads – code in Perl (and a Postscript (!) version here). Not fancying reverse-engineering the Perl too much, I wrote and asked Sean if there was a better source for the algorithm. Apparently Danny’s original version is in Mathematica. I haven’t found it, but Sean says he’ll send me what he can find in a few days. Otherwise, I guess I’ll keep digging, ask around on the Long Now forums, etc.

Sean pointed out that, when reverse engineering, “there’s understanding, and there’s understanding”, and pointed me at this fantastic war story, which sounds like a Daily WTF candidate to me. I’ve been there in the past, and in my case it was spaghetti Perl I was banging my head against – not pleasant. Still, the whole process of reverse engineering, of picking apart the code slowly, gradually and gently teasing the tangled knot open, can be a wonderful thing in itself. Or it might just turn out that the Mathematica code is clean and easily Haskellised. I doubt it, though, from what I’ve seen of Mathematica. :-) I expect it’ll live in a much lower-level domain than I want to work in, which is, of course, more than half the fun. If I can take an esoteric algorithm in a difficult language and translate it into beautiful and readable higher-order code, that’d be something worth writing about. So, watch this space (but don’t, of course, hold your breath).

In the mean time, as I said, the search is turning up all sorts of cool stuff. We present:

Another version of the algorithm, by Joe McMahon, in OS X/AppleScript discussed here, here & here (code via that last link). Interesting mention of ChucK too, which looks quite shiny (though again, maybe a little low-level for my taste).

Prototype chime generator diagram – I would wear a t-shirt with that on it.

An interview with Alan Kay from two weeks ago, which also points at the Kay-says-it’s-a-must-read Doug Engelbart essays (and no, I must confess, I hadn’t heard of Engelbart).

Pop culture lives in the present; it doesn’t really live in the future or want to know about great ideas from the past. I’m saying there’s a lot of useful knowledge and wisdom out there for anybody who is curious, and who takes the time to do something other than just executing on some current plan. Cicero said, “Who knows only his own generation remains always a child.” People who live in the present often wind up exploiting the present to an extent that it starts removing the possibility of having a future.

Stewart Brand meets the Cybernetic Counterculture – whee, the 60s!

(These last two via this del.icio.us page on “admirable people”.)

Haskell study plan

Haskell study plan [smallcool].

Haskell and Category Theory

An introduction to Category Theory from a Haskell point of view. As always, monads are where your brain starts hurting.

hOp – a micro-kernel based on the Glasgow Haskell Compiler

Wow… Potential third year project supervision material for next year: hOp, a microkernel based on the Glasgow Haskell Compiler, in which “experimenting with writing drivers in Haskell should be reasonably easy“. Funky as. [lambda]

Where Python meets Haskell

Alex Martelli explaining how Python’s list comprehensions and (new and groovy) generator expressions relate to Haskell, and why Python doesn’t (in generally) do lazy evaluation. As someone with a foot in both camps, but no deep understanding (alas – yet) of what’s actually happening, this is pretty interesting stuff…