mux on #haskell pasted what is perhaps the most beautiful code I’ve ever seen in my life:
<mux> > nubBy(((>1) .) . gcd) [2..]
(Number two in an ongoing series of jaw-dropping Haskell one-liners which began with the fibonacci series.)
Here’s that well-known phrase “my hovercraft is full of eels” translated into more than sixty languages [reddit].
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:
Read the rest of this entry »
[gimbo@orb xmonad] runghc -v Setup configure
Could not find module `Distribution.Simple':
Use -v to see a list of the files searched for.
Wtf? Warrant issued for Richard Gere’s arrest in India following public kissing. Kissing on the cheek, mind you. An “obscene act”, apparently – it’s official!
Public displays of affection are still largely taboo in India, and protestors in Mumbai (Bombay) set fire to effigies of Gere following the incident.
Wtf? They burnt effigies of him? For a bit I wondered if the anger was directed solely at him. Apparently not.
… while protesters in other cities shouted “death to Shilpa Shetty”.
Here we have actual human beings, calling for the deaths of other actual human beings, because they kissed in public? Ye gods and little children, will the insanity of men never cease?
Wow, synchronicity. Yesterday I was browsing dons‘ space (because I spotted something like my string split in his h4sh stuff), and was very intruiged to spot xmonad. It’s another lightweight tiling window manager in the style of ion, wmii, dwm, and appears to be most like dwm in fact. It’s written in Haskell. Today, they announced the 0.1 release, so I just had to take a look.
It wasn’t too hard to install… A few dependencies, but all handled by Cabal, tvm. Since I already use wmii I didn’t find the keybindings too alien, and of course I can configure them at leisure should I wish to (and unlike dwm, it apparently doesn’t need a recompile when the config changes). Its (dwm-like) style of window management doesn’t sit completely easily with me, I have to say. I guess I’ve got used to the wmii way. I’m going to give it a go for a while, though, as I have an inkling I could grow to love it. It’s very snappy.
I miss three things.
First, a statusbar visible on every workspace. I just want to be able to see some things at a glance, always. Examples: time/date; battery life and charging/discharging status; xmms time remaining and shuffle status. Looking at the mailing list archives, it smells like there is or will be room for user-supplied extensions, and I guess this is an obvious candidate. If I don’t write it I’m sure someone else will. :-) Related to this is the ability to name workspaces, so they’re not just 1-9 – not critical but very handy. I don’t care about the whole tagging thing wmii does – I just want named workspaces as an aide memoir in the statusbar. “Ah yes, workspace 6 is hets.” That kind of thing.
Second, and routable-around: floating/unmanaged workspaces. Tiling/management is great 95% of the time, but sometimes it’s just a pain. The Gimp is the main culprit here, with its myriad windows of joy, but there are other cases. Xnest is probably the answer here. Here’s a little script to run an embedded icewm session:
Xnest :1 -name "Xnest" +kb -ac -geometry 1280x800 &
xsetroot -display :1 -solid black &
Third, I miss my window bars (the bits along the top where most wms put close buttons, etc.). Primarily I miss them in my terminals, where they report the full path of the current working directory. Another handy at-a-glance feature. I guess I can live without this though, for the sake of precious screen space. :-)
None of these are killers/blockers, though, so I’m definitely going to give xmonad a serious go.
(I realise it’s gone very “theory of programming languages” round here lately. Don’t worry, I’m sure I’ll have something else to talk about soon.)
Church’s Thesis and Functional Programming, a lovely little paper by David Turner (he of SASL & Miranda fame). Like the Google Tech Talk I mentioned a couple of days ago, it’s big on unifying historical perspective, which is a welcome change from most of the papers I see on these topics, which seem to assume you’ve either read all the papers they reference (recursively), or you’re about to. ;-)
It’s a veritable concucopial tour of TPL: Church’s thesis; the equivalence of lambda-calculus, Turing machines, and recursive functions; how the halting problem fits into that; the lambda calculus; Church-Rosser; strict vs. non-strict; combinatory logic; typed lambda-calculi; implementation of lazy FP (exemplars Miranda & Haskell); domain theory; FP without general recursion; Curry-Howard; Martin-Lof; and a hint of abstract Stone duality (which always makes me think of Father Stone). Seriously, if you’re at all interested in theoretical computer science, you should definitely take a look at this. I started losing the thread in the final section, but loved the rest and, I think, learnt quite a bit – mainly how various bits fit together; like joining the dots on a map.
(Ooh. Strachey coined the term “syntactic sugar”.)
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"
*StringSplit> split "an" "banana"
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
-- | 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.
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. ;-)
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]
Great stuff: Parametric Polymorphism and the Girard-Reynolds Isomorphism [reddit] – a 30 minute Google Tech Talk by Phil Gossett. A really clear presentation covering a number of interesting topics, with a very convincing historical sweep. Certainly cleared a few things up for me, at least. His response to the last question is really more Hindley-Milner than Girard-Reynolds, mind. ;-)
Phil Wadler comments.
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"
*Ew> endswith "banana" "moo"
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"
*Ew> (endswith "na") "a"
*Ew> (endswith "na") "na"
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"
*Ew> filter (endswith' "na") ["banana", "cat", "iguana", "mastodon"]
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"
*Ew> filter ((flip endswith) "na") ["banana", "cat", "iguana", "mastodon"]
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…
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"]
A name I’ve come across in my work on hets is Grothendieck. In a great example of Wikipedia cascade, someone on #haskell this morning mentioned the programming language Joy (which looks pretty cool), which led to the page on monoids, which led to the page on Grothendieck groups, which led to the page on Grothendieck himself, who a) also looks cool, and b) “gave lectures on category theory in the forests surrounding Hanoi while the city was being bombed, to protest against the Vietnam war”. Respect.
The Reason for Blogging, or rather Josef Svenningsson‘s reason for blogging – but I agree with what he says. In fact, I was only reading that post because he had commented on an earlier post of mine – a post which someone (ooh, dons)has submitted to programming.reddit.com and which was hence received some attention. As such, the following particularly resonated:
But then, why do I blog, as opposed to just writing on a piece of paper? The reason for me is that the possibility that someone might read what I write helps me write. Blogging means that I have an (at least potential) audience which I can target my writing towards. This (perhaps imaginary) audience is very important for me, I wouldn’t be able to write without it. I simply can’t motivate myself to write only for my own sake.
Absolutely. That post of mine about sections started with me just playing around for my own sake, investigating something interesting I’d just come across for the first time. I like to make notes (my memory is lamentably poor), and a blog is a nice way to do that; but as Josef says, once you commit to publishing, you think more carefully about what you write, how it’s structured, etc. Of course, I’m fairly used to writing (sometimes extensive) notes for semi-public consumption in my work, but a blog is nicer than a lecture in that anyone can leave comments and expand my understanding. That happens in lectures sometimes, but rarely, and almost never with random Haskell experts from all over the world. :-)
Another goodie of Josef’s: yak shaving. Yep, been there.
Boy falsely jailed for bomb threat for 12 days due to DST changeover. (URL in RISKS story doesn’t seem to work? Lots of google hits though, many of which have the same content and no attribution, sadly.)
Webb gave an insight into the school’s impressive investigative techniques, saying that he was ushered in to see the principal, Kathy Charlton. She asked him what his phone number was, and, according to Webb, when he replied ‘she started waving her hands in the air and saying â€œwe got him, we got him.â€’
‘They just started flipping out, saying I made a bomb threat to the school,’ he told local television station KDKA. After he protested his innocence, Webb says that the principal said: ‘Well, why should we believe you? You’re a criminal. Criminals lie all the time.’
Dorks. Dorks in positions of authority, more to the point.
Oh wow. According to the all-knowing Wikipedia Corey Feldman‘s second marriage was offociated by MC Hammer! I think that’s the best thing I’ve heard all year.
(Why am I Feldman-surfing? Last week, Bash & I watched The Goonies. I hadn’t seen this movie since its original release, when I went with my mum to see it at a cinema in Aylesybury. That must have been late 1985, and I’d have been 11 years old. Fun film, good to see it again, but made me wonder whatever happened to ol’ Corey. Well, now I know. :-) )
Here’s a super-cool (and very very large) image: All (known) bodies in the Solar System larger than 200 miles in diameter. Via the recently unveiled Long Now blog.
I received my Long Now charter membership card this morning. The envelope was beautiful – square, dun cardboard, a big Long Now logo, pretty American stamps, a San Francisco postmark, understated address labels… I was really impressed. Unfortunately, I was much less impressed by its contents, my “limited edition, individually numbered, stainless steel Charter Member card”. Flimsy (in fact, slightly bent), and fingerprinted, it really didn’t have the expected feel of, well, longevity. I was, at least, expecting something thicker and less bendable. :-)
I’ve spent most of today looking at Haskore, which appears to be the most well-developed kid on the block for doing Csound type things using Haskell (and indeed, doing music type things using Haskell). Here are my notes on finding/installing it, which experience wasn’t completely straightforward…
Read the rest of this entry »
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"
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"
('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'
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.
I have Firefox configured to not allow pages to specify their own fonts: instead, everything just gets rendered as sans-serif. I do this to make the web more legible.
This morning I realised an unintended consequence: my view of Gimboland differs from everyone else’s! While I was seeing it in beuatiful clean sans-serif, everyone else saw Georgia, or Lucida, or one of a list of several possibilities specified by the style sheet. Not what I wanted! So, for now, I’ve switched Gimboland’s style-sheet to specify sans-serif. To my mind this ought to be nice & clean (assuming your fonts are reasonably sensible); you may of course disagree – do let me know if you care to. And you can, of course, override the font in your own browser if you don’t like it. ;-)
This is, by the way, part of my ongoing effort to make Gimboland look OK across platforms & browsers. I think I’ve sorted out the alignment in the header, and now the only thing to do is work out why the sidebar overflows horizontally under Windows (even in Firefox, I think?).
Clive James on hoaxes & fraudsters. I’m with him on this one.
Some commentators regard fraudsters as romantic types, more interesting than poor old plodding us. These commentators say that few of these frauds would work without our greed. Perhaps not, but none of them would work without the propensity of the fraudster to lie.
How many software engineers does it take to change a lightbulb?
Just one. But the house falls down.
software engineering proverbs
Handy & cunning: netrenderer: how does such-and-such-a-URL look in IE7? Handy for those of us who avoid Windows like the plague as much as possible…
(And yes, I know Gimboland’s still a bit broken. Ah well.)
Oh, hey, the Shiko gig at the Monkey on Monday was fun. It was reeeeaaalllly quiet: probably a quarter of the people there were Shiko people, I’d say. Monday night in Swansea’s bound to be fairly quiet, I suppose, particularly outside term time, plus it was the first night of the new Wales-wide smoking-inside ban. The latter may or may not have been a factor, but it certainly made for strangely smoke-free Monkey experience.
We were there as part of an “African Rhythms” night – basically a couple of guys DJ’ing African music (not the usual Mondo boys, one of whom, Eddie, is also a Shiko’er), and us! As I said, it wasn’t massively well-attended, but that was kinda cool, because it ended up feeling less like a gig, and more like just going and playing together somewhere, but with people dancing. :-) Two people in particular: two girls who do African dancing (they were in the carnival, I remember). We’d prepared three pieces, but in the end only did two of them, and that seemed enough. Later, some random jamming occurred, which was sweet. So, all in all, very chilled, very cool, very much fun.
You can now get sushi in Swansea – at last!
A place called Wasabi opened in Uplands a few weeks ago (phone no/address here); we’ve eaten there twice: it did not disappoint on either occasion. Great food, nice decor/atmosphere, loads of cute asian waitresses, plum wine, sake, green tea ice cream (deep fried and not), etc. The first time, I had gyoza, california rolls, and shoyu ramen, which last dish would have sufficed perfectly well alone – huge and delicious, with a soup spoon more like a gently dimpled spatula. The second time, the irresistable gyoza again, and another ramen, this time with spicy beef. My only disappointment here was that it wasn’t spicy enough: I’d hoped for something reminiscent of a spicy beef soup I’d had for breakfast on my last day in Beijing, nearly two years ago. Life continues to attempt to teach me the lesson that things anticipated are rarely as sweet as the anticipation, and I continue to put my fingers in my ears and sing la-la-la.
Anyway, all in all, highly recommended, long overdue, and very welcome.
Weirdly, they seem to have done a really bad job of sorting out an internet presence. On Friday they didn’t even have a Yell listing, though they’ve sorted that out now. (It clearly did no harm to their sales – word of mouth, I assume, assured that the place was packed both times we went.) Furthermore, and quite curiously, the menu sports the address www.wasabi.com, which is (currently) just a placeholder page, and the domain is registered to a PO box in Hong Kong. I guess it could be the people behind the restaurant, but my first thought was that it was just a domain squatter, and that the restauranteurs had made a big blunder, somehow. :-) The email address firstname.lastname@example.org is also on the menu, though, so they really do seem to mean it. It all seems a bit weird, to me — can it really be that the (surely highly desirable) wasabi.com domain is owned by a restaurant in humble Swansea? I could understand it being owned by a chain, but then I’d expect the website to have more than a holding page.
Ah, in true geek fashion, I’ve spent as much of this post discussing domain issues as I did on the food (and the waitresses). Somebody save me, please.
Oooh! In related news, congratulations to Jo, who had her PhD viva on Friday and got through it without needing rescue or anybody getting poisoned. Hurrah for Jo! (And thanks for the spicy beef ramen.)
While going through Gimboland history, I came across this post from 2001, discussing the near-certainty of an imminent catastrophic hurricane/flood decimating New Orleans — less than four years later, along came Katrina. Interestingly, Wikipedia tells us that the population of the city has largely bounced back since Katrina — so expect more of the same in a few years, I guess.