therning.org/magnus
Checked: 2 hours 27 min ago
Updated: 3 days 15 hours ago
Update every: 2 hours
Incoherent mumblings
This morning on Swedish telly…
Today I started the day by watching some Swedish telly, Gomorron Sverige I think the show was called. Three guests got to comment on the news year that just passed. They were asked for their nominations in categories such as Most Over-Reported News Story, Most Important Public Figure and the like. One of them nominated climate change for the category Most Under-Reported News Story. Immediately one of the others blurted out that he thinks that climate change is exaggerated and has received too much attention in media. He was told that there now is proof that large portions of the polar ice has melted (25% was mentioned, though I didn’t catch whether it was an increase of 25% or if 25% was gone, anyway, it doesn’t really matter here) and that therefore this is a very real problem. In answer to this the climate-change doubter mentioned that he has been keeping an eye on the water level at the pier near his summer place and there has been no change over the years. So, if climate change is real and the polar ice is melting, where does the water go? My initial reaction against this line of ressoning seems to have been shared by the person who initially brought up the subject, “How could he argue against climate change? And with such a simplistic argument as well?” Then I was disappointed to hear that the only counter argument basically boiled down to “But, it doesn’t work that way” and “How can you argue against all the scientists?” First I was disappointed in her for not providing any answers, then I grew more disappointed in myself as I realised that had I been sitting next to this climate-change doubter myself at a dinner I wouldn’t hve been able to provide a stronger argument myself.
How should a counter-argument be constructed? What scientific ideas and proofs should be used to point out the fallacy of the “pier argument”?
I can think of these:
- There is evidence of climate change on a macro level, his argument doesn’t explain those away. All he’s really saying is that on a micro level, and in a very specific geographical location, measuring only the water level, he can’t find any evidence for climate change.
- It’s probably also simple to point out the lack of scientific rigor in his methods. Somehow though, I feel this is a bad way to try to convince anyone.
![[Digg]](http://therning.org/magnus/wp-content/plugins/bookmarkify/digg.png)
![[Reddit]](http://therning.org/magnus/wp-content/plugins/bookmarkify/reddit.png)
More » Book: Lighttpd
As I mentioned in the previous post I received an email pointing me towards a newly released book on lighttpd. Only one chapter is available free of charge so that and the table of contents is all I can comment on at this point.
Let’s start with the table of contents. To be honest I found it very disappointing, there were so many other chapters that I would have found much more interesting than chapter 10. Given that I’ve never really gotten into Apache to begin with I would much rather have read about advanced configuration (chapters 2 and 3), or CGI (chapters 3 and 11), or maybe most about securing lighttpd, both securing what it serves (through SSL, chapter 6) and by reducing privileges (chapter 8). Yes, for me personally they’ve chosen the least interesting chapter to make available free of charge 
So, what do I think about chapter 10 then? Overall I’m happy with it. In a book like this, one that covers usage of a specific piece of software, I’m happy to find text that is clear and simple to understand. It isn’t very deep in concepts and details, but there are links to places where I can find out more if I need it. I’m not familiar enough with lighttpd to judge whether the details are correct, but I assume they are, and as I already mentioned it isn’t a complete reference, but offers links to where the reader can find more details. One thing that did upset me a little is the presence of rather lengthy pieces of Python scripts to aid in the converting some of the Apache configuration to lighttpd. Though I suppose they fit in I’d rather have seen them made available only online, with just the descriptions and usage in the book. I couldn’t help but feel they were there only to increase the page count.
Anyway, what I’ve seen so far makes me want to read the rest of the book. As I’ve made clear I’m not a serious user of lighttpd, but it is the web server I reach for first when I find myself needing one. I think this book will make me a more efficient user of lighttpd.
More » A first for me…
I’ve read quite a few articles about the changing landscape of marketing, how regular ads and old-style marketing is no longer trusted. I suppose companies have over-promised and under-delivered for too long. Instead PR firms are adding blogging into the mix, which probably means blogs will be ruined in the long run For now though blogs are still trusted, especially when it’s regular people who write about products.
So, why this post? Well, it seems the few posts I’ve made here on lighttpd seems to have attracted some minimal attention and I received an email regarding a new book on lighttpd, published by Packt publishing. This despite the fact that I am what can only be called a cursory user of lighttpd. It contained a link to a gratuitous chapter so I decided to play along and pubically comment on the chapter. If you don’t like this kind of thing then you should skip the next post.
More » Re: Redesigning GHC’s build system
The blog GHC Mutterings doesn’t allow posting of comments without logging in. Since I have absolutely no interest at all in creating yet another online account I hope they allow pingbacks 
In this post they discuss the planned redesign of GHC’s build system, and here’s my comment:
The goal of moving away from make is probably a good one, but when failing to get Cabal to fit your needs you revert back to redesigning it using make again? There are numerous other build tools out there, many of them remarkably better than make. What other tools were considered and why were they discarded? I simply refuse to believe that the only build tool to make the shortlist was make.
More » Keysafe and screenshots.debian.net
After reading about screenshots.debian.net I’ve now uploaded a screenshot for the only package I have in Debian, keysafe. It will be visible to the public as soon at it has been approved.
More » Another item for the GMail whishlist
Why can’t I change the ordering of mail in GMail?
I’ve never quite understood why anyone would want to have their most recently received mail at the top. Personally I always want to read mail in the order they arrive.
More » Adventures with a certain Xen vulnerability (in the PVFB backend)
Here’s another post about a paper I’ve read recently. This time it’s not entirely for fun, but I still thought I’d write about this one, Adventures with a certain Xen vulnerability (in the PVFB backend). I’ve read a few security-related papers and articles. In general I’ve found that there’s a huge gap in quality (and sometimes rigor) between the practitioners and academia. This however is a paper that I found to be of good quality, while still being produced by a member of the former camp. Hopefully it will start a trend
More » Evaluating High-Level Distributed Language Constructs
I thought I’d start posting little notes about papers I read, especially if I find them interesting and worth reading. So here we go!
I read this paper on the bus this morning. I suspect I got it off Lambda the Ultimate a while back, printed it and then kept it in my bag for several months.
Evaluating High-Level Distributed Language Constructs
More » What money is
A friend pointed me to this film about what money is. I’ve known since high school how banks create money, but I’ve never thought it through to its logical, and somewhat worrying, conclusion. Well worth watching I thought.
More » Haskell and Time
I’ve found myself getting confused over the Data.Time modules a few times now. Today I wanted to do something that I ought to be simple both to do (it was) and find out how to do (it wasn’t, at least not for me). I thought I’d write it down, because I’m bound to forget about it otherwise, and it might be helpful for some other poor soul out there.
I wanted to store a date in a database (SQLite) using Haskell (HDBC). Since I’m only interested in the date and not the time I chose to represent it in Haskell as a Date.Time.Calendar.Day. For Day 0 means 1858-11-17. HDBC on the other hand needs the date in seconds since epoch (1970-01-01 00:00 UTC), which conveniently can be represented with a single Integer. Time.Data.Clock.POSIX contains a few handy functions to convert between POSIXTime (NominalDiffTime) and UTCTime. However, there are no special functions for converting between an Integer and NominalDiffTime. The way I found was to do it via the class types that NominalDiffTime implements.
First I thought that Enum might offer the solution, but my experiments with that was a bit confusing:
> pt <- getPOSIXTime 1221603766.526661s > fromEnum pt 4118657661830593344 > toEnum 4118657661830593344 :: POSIXTime 4118657.661830593344s
Not really the result I had hoped for. No, instead the function to use to get the Integer is floor, and the only way I found to convert a NominalDiffTime from an Integer is to go via a Ratio:
> fromRational (1221603766 % 1) :: POSIXTime 1221603766s
Have I missed something or is this the best way to achieve this?
More » GPG and Gmail?
I’d love to see the Gmail S/MIME plugin for Firefox gain support for PGP/MIME. I can’t imagine it’d be too hard to add for someone who’s familiar with JavaScript and Firefox plugins. Or maybe there’s some other plugin out there that offers PGP/MIME support in Gmail?
Oh, and no, FireGPG isn’t good enough, it doesn’t do PGP/MIME, it doesn’t automatically verify/decrypt received emails, and it requires too much mouse interaction!
More » Confusion with HaskellDB
Dear LazyWeb,
I’ve recently made some comparisons between HaskellDB and HDBC. My gut feeling is that I’d like to use HaskellDB due to its typesafety and that it allows me to abstract away from SQL—something in me twitches everytime I see strings containing SQL mixed in with other code, no matter what language it is. However there are some things that confuse me with HaskellDB. After overcoming the initial puzzlement that I seem to hit whenever I look at a Haskell API I stumbled on the apparent lack of support for primary keys. This surprised me and to check if I overlooked something I wrote the following code:
module Main where
import System.Environment
import System.IO
import Database.HaskellDB.HSQL.SQLite3
import Database.HaskellDB.DBSpec
testDBOpts = DBOptions { useBString=False }
sqliteOptions= SQLiteOptions { filepath="replace me", mode=ReadMode }
main :: IO ()
main = do
dbfn <- fmap (!! 0) getArgs
let options = sqliteOptions { filepath=dbfn }
sqliteConnect options (dbToDBSpec False "extracted.db") >>= print
This is the surprising output when I point this to two different databases. The first database has no primary key:
% sqlite3 test1.db .dump
BEGIN TRANSACTION;
CREATE TABLE person (name text not null,
age int);
COMMIT;
and the DBInfo looks the way I expected:
% ./extract test1.db
DBInfo {dbname = "extracted.db", opts = DBOptions {useBString = False},
tbls = [TInfo {tname = "person", cols = [CInfo {cname = "name",
descr = (StringT,False)},CInfo {cname = "age", descr = (StringT,True)}]}]}
The second database does have a primary key:
% sqlite3 test2.db .dump BEGIN TRANSACTION; CREATE TABLE person (name text primary key not null, age int); COMMIT;
but not only does the DBInfo lack any mention of it, it also contains the table info twice:
% ./extract test2.db
DBInfo {dbname = "extracted.db", opts = DBOptions {useBString = False},
tbls = [TInfo {tname = "person", cols = [CInfo {cname = "name",
descr = (StringT,False)},CInfo {cname = "age", descr = (StringT,True)}]},
TInfo {tname = "person", cols = [CInfo {cname = "name",
descr = (StringT,False)},CInfo {cname = "age", descr = (StringT,True)}]}]}
Am I doing something fundamentally wrong or does HaskellDB not support the notion of a primary key?
Is it a bug in HaskellDB that the second extracted DBInfo contains two instances of TInfo when the database clearly only has one table?
More » TagSoup, meet Parsec!
Recently I began writing a tool to scrape some information off a web site for some off-line processing. After writing up the basics using TagSoup I showed what I had to a colleague. His first comment was “Can’t you use Parsec for that?” It took me a second to realise that he didn’t mean that I should write my own XML parser but rather that Parsec allows writing parsers of a list of anything. So I thought I’d see just what it’d take to create a parser for [Tag].
A look at the string parser shipped with Parsec offered a lot of inspiration.
First the basic type, TagParser:
type TagParser = GenParser Tag
The basic function of Parsec is tokenPrim, basically that’s what other basic parsers use. Taking a cue from the string parser implementation I defined a function called satisfy:
satisfy f = tokenPrim
show
(\ pos t _ -> updatePosTag pos t)
(\ t -> if (f t) then Just t else Nothing)
The positioning in a list of tags simply an increase of column, irrespective of what tag is processed:
updatePosTag s _ = incSourceColumn s 1
Now I have enough to create the first Tag parser—one that accepts a single instance of the specified kind:
tag t = satisfy (~== t) <?> show t
It’s important to stick the supplied tag on the right of (~==). See its documentation for why that is. The second parser is one that accepts any kind of tag:
anyTag = satisfy (const True)
So far so good. The next parser to implement is one that accepts any kind of tag out of a list of tags. Here I want to make use of the convenient behaviour of (~==) so I’ll need to implement a custom version of elem:
l `elemTag` r = or $ l `elemT` r
where
l `elemT` [] = [False]
l `elemT` (r:rs) = (l ~== r) : l `elemT` rs
With that in place it’s easy to implement oneOf and noneOf:
oneOf ts = satisfy (`elemTag` ts) noneOf ts = satisfy (\ t -> not (t `elemTag` ts))
So, as an example of what this can be used for here is a re-implementation of TagSoup’s partitions:
partitions t = liftM2 (:)
(many $ noneOf [t])
(many $ liftM2 (:) (tag t) (many $ noneOf [t]))
Of course the big question is whether I’ll rewrite my original code using Parsec. Hmm, probably not in this case, but the next time I need to do some web page scraping it offers yet another option for doing it.
Burning audio CDs on Linux
I just had a blast from the past!
Being somewhat spoiled by the current state of Linux-on-the-desktop (Gnome in my case) I have become used to inserting a blank CD, point Nautilus to burn:///, dragging and dropping a few files into it, and finally clicking the “Burn to CD” button. Works beautifully. Of course I thought that Nautilus’ CD-burning would know about audio CDs. So I dragged a few WAV files into Nautilus and clicked the button. Voilà, a data CD containing a few Wav files! Not really what I wanted.
So, to avoid this in the future here is the command line to use:
wodim -v dev=0,0,0 speed=40 -audio -pad *.wav
More prefixes
As Edward pointed out the code in the previous post expressions such as a .+. b .+. c are problematic. By expanding the expression and introducing a few parentheses it becomes apparent what the problem is:
fromIB $ (toIB (fromIB $ (toIB a) `addIB` (toIB b))) `addIB` (toIB c)
The problem is that inner fromIB. Unfortunately GHC doesn’t realise that the left-most sum could take on any type that is a CIB, the exact type doesn’t really matter since the result is passed to toIB anyway. It would be sort of cool if I could tell the compiler to prefer a specific CIB, basically a directive along the lines of “if in doubt, use Bytes”. I don’t think that’s possible in GHC. As it stands one would have to specify the type of the inner sum:
(a .+. b :: Bytes) .+. c :: KBytes
One possible solution would be to remove the call to fromIB from the definition of .+. and instead require the user to call it explicitly:
fromIB $ a .+. b .+. c :: KBytes
I suppose it’s all right, but not quite as elegant as I had hoped.
Now on to the more interesting part of Edward’s comment. I needed quite a bit of clarification, but I now know what he is proposing, I even think I understand it
The general idea is to have the compiler choose the largest prefix that can represent the sum of two values without losing precision. The represention I used didn’t have the problem of ever losing precision, so I’ll change the representation to better show what Edward meant.
First off I need some extensions to GHC:
{-# OPTIONS_GHC -XGeneralizedNewtypeDeriving
-XMultiParamTypeClasses
-XFunctionalDependencies #-}
Now the prefixes are represented with a single integer (or rather a single instance of Num). This is easily done thanks to GeneralizedNewtypeDeriving.
newtype Bytes a = Bytes a
deriving (Eq, Show, Num)
newtype KBytes a = KBytes a
deriving (Eq, Show, Num)
newtype KiBytes a = KiBytes a
deriving (Eq, Show, Num)
Now I need a typeclass to bind together two types in a ‘lesser-than-or-equal’ relationship and provide a conversion function:
class LEq s u where
lower :: Num a => s a -> u a
Now the relation has to be implemented for the prefixes. In short the following says that Bytes is the less than both KBytes and KiBytes and that each prefix is less than or equal to itself:
instance LEq Bytes Bytes where
lower = id
instance LEq KBytes KBytes where
lower = id
instance LEq KiBytes KiBytes where
lower = id
instance LEq KBytes Bytes where
lower (KBytes k) = Bytes $ k * 10^3
instance LEq KiBytes Bytes where
lower (KiBytes ki) = Bytes $ ki * 2 ^ 10
Now there’s a second relationship that is designed to relate two prefixes to a third one. Basically the third is the largest prefix that can be used to represent the sum of the other two without a loss of precision. One could say that the third is where the other two meet.
class (LEq s u, LEq t u) => Meet s t u | s t -> u
I have to manually define where the different prefixes meet:
instance Meet Bytes Bytes Bytes instance Meet KBytes Bytes Bytes instance Meet Bytes KBytes Bytes instance Meet KiBytes Bytes Bytes instance Meet Bytes KiBytes Bytes instance Meet KBytes KBytes KBytes instance Meet KBytes KiBytes Bytes instance Meet KiBytes KBytes Bytes instance Meet KiBytes KiBytes KiBytes
Now I can define addition and subtraction in terms of Meet instances:
(.+.) :: (Meet s t u, Num a, Num (u a)) => s a -> t a -> u a (.+.) a b = (lower a) + (lower b) (.-.) :: (Meet s t u, Num a, Num (u a)) => s a -> t a -> u a (.-.) a b = (lower a) - (lower b)
Finally I’ve arrived at the destination, but as so often I have to admit that the journey was at least half the fun.
*Prefixes> let i = KiBytes 4 *Prefixes> let j = KBytes 3 *Prefixes> let k = Bytes 900 *Prefixes> i .+. j Bytes 7096 *Prefixes> i .+. i KiBytes 8 *Prefixes> i .+. j .+. k Bytes 7996
Playing with prefixes
I just realised that it’s been over a month since I posted something. All I can do is blame life With a daughter of 8 months and a recent switch of positions I just haven’t found time to play around really. Hopefully that’ll change now that the situation at work is “calming down” a bit.
Anyway, here’s a bit of code I played with today. A friend described a problem inside a tool related to reporting of free and used memory. Apparently, depending on the location in the code, memory could be stored in integers in bytes or in kilobytes (kB) or in kibibytes (Ki) or in mebibytes (Mi) etc. In every place the prefix would be ‘recorded’ in the variable name, resulting in a situation where a change of prefix used in one place would force a change of variable names in callers/callees. A bit of a mess. I thought I’d try to explore what Haskell’s type system could produce
My first thought was to create a data type for the prefixes:
data Size = Bytes Int
| KB Int Int
| KiBi Int Int
deriving (Show, Eq)
Both for KB and KiBi I record the number of full KBs (Kis) and the remaining bytes. Then I thought that it’d be easiest to do all the calculations in bytes, which required a conversion function:
toBytes (KB i r) = Bytes (10^3 * i + r) toBytes (KiBi i r) = Bytes $ 2^10 * i + r toBytes b = b
After that it’s possible to make Size an instance of Num (incomplete, but the rest of the functions in Num are straight forward):
instance Num Size where
(Bytes b1) + (Bytes b2) = Bytes $ b1 + b2
s1 + s2 = (toBytes s1) + (toBytes s2)
(Bytes b1) - (Bytes b2) = Bytes $ b1 - b2
s1 - s2 = (toBytes s1) - (toBytes s2)
Unfortunately the result will always be in Bytes so a few other conversion functions are necessary:
toKB (Bytes i) = uncurry KB $ divMod i (10^3) toKB s = toKB $ toBytes s toKiBi (Bytes i) = uncurry KiBi $ divMod i (2^10) toKiBi s = toKiBi $ toBytes s
Now it’s easy to create a type for bookeeping of memory and making it an instance of Num as well:
data MemUsage = Free Size | Used Size
deriving (Eq, Show)
instance Num MemUsage where
(Free i) + (Free j) = Free $ i + j
(Used i) + (Used j) = Used $ i + j
(Free i) + (Used j) = Free $ i - j
(Used i) + (Free j) = Used $ i - j
(Free i) - (Free j) = Free $ i - j
(Used i) - (Used j) = Used $ i - j
(Free i) - (Used j) = Free $ i + j
(Used i) - (Free j) = Used $ i + j
On some level this ‘algebra’ for memory usage makes sense, though refinements are certainly possible e.g. . I suspect there are some interesting choices to be made regarding the remaining functions in Num, e.g. should negate turn free memory into used memory?
I find this solution somewhat lacking in the extensibility department—as the commonly available amount of memory grows (the code above is stuck in the 80’s it seems) changes have to be made to Size. The same goes for changes to support non-standard prefixes, probably not a common problem but It would be nice to have a solution that is “independently extensible”.
Second approachHere my idea was to create one type per prefix, use a separate type for the calculations and use a type class for the conversions. Quite straightforward when put like that, though it took me a while to come up with it
Here is the internal representation used during calculations:
data IB = IB Int
deriving (Eq, Show)
Simple enough. Then the class for conversions to and from IB:
class CIB a where
toIB :: a -> IB
fromIB :: IB -> a
No surprises there either. Now I want to add and subtract, but due to the definition of Num (it requires all arguments to be of the same type, e.g. the type of addition is (+) :: a -> a -> a) I’ll need two new functions for that (at least I don’t know a way around this):
(.+.) :: (CIB a, CIB b, CIB c) => a -> b -> c
i .+. j = fromIB $ (toIB i) `addIB` (toIB j)
where
addIB (IB i1) (IB i2) = IB (i1 + i2)
(.-.) :: (CIB a, CIB b, CIB c) => a -> b -> c
i .-. j = fromIB $ (toIB i) `subIB` (toIB j)
where
subIB (IB i1) (IB i2) = IB (i1 - i2)
One interesting observation is that due to the type of .+. and .-. it is possible, and often required, to specify the type of the result, somewhat similar to HSH. Now the stage is set for the prefix types to be defined, starting with plain bytes:
data Bytes = Bytes Int
deriving (Eq, Show)
instance CIB Bytes where
toIB (Bytes i) = IB i
fromIB (IB i) = Bytes i
Similarly for kilobytes and kibibytes:
data KBytes = KBytes Int Int
deriving (Eq, Show)
instance CIB KBytes where
toIB (KBytes i j) = IB $ i * 10^3 + j
fromIB (IB i) = uncurry KBytes $ divMod i (10^3)
data KiBytes = KiBytes Int Int
deriving (Eq, Show)
instance CIB KiBytes where
toIB (KiBytes i j) = IB $ i * 2^10 + j
fromIB (IB i) = uncurry KiBytes $ divMod i (2^10)
The data type for memory usage wrap the memory usage:
data MemUsage a = Free a | Used a
deriving (Eq, Show)
Again I can’t make MemUsage a an instance of Num, instead there are two new operators:
(~+~) :: (CIB a, CIB b, CIB c) => MemUsage a -> MemUsage b -> MemUsage c (Free i) ~+~ (Free j) = Free $ i .+. j (Used i) ~+~ (Used j) = Used $ i .+. j (Free i) ~+~ (Used j) = Free $ i .-. j (Used i) ~+~ (Free j) = Used $ i .-. j (~-~) :: (CIB a, CIB b, CIB c) => MemUsage a -> MemUsage b -> MemUsage c (Free i) ~-~ (Free j) = Free $ i .-. j (Used i) ~-~ (Used j) = Used $ i .-. j (Free i) ~-~ (Used j) = Free $ i .+. j (Used i) ~-~ (Free j) = Used $ i .+. jEnd thoughts
There is one thing I like about the first approach and one thing I don’t like. That both the types are instances of Num is something I like since I am interested in adding and subtracting memory, though arguably there are functions in Num that don’t make much sense for memory (e.g. multiplication and negation). The thing I don’t like is the need for explicit conversion functions (toKB and friends).
There are also one thing that I like about the second approach and one I don’t like. I would have liked to use the standard functions in Num, introducing new (type-specific) operators is something that I’m never particularly keen on. Though I suppose that implementing separate operators does emphasize that memory isn’t quite like regular integers. I really do like using Haskell’s own syntax to do the conversion, it’s more readable than having to call conversion functions.
That’s it! Comments and suggestions for improvements are always welcome of course.
Google Treasure Hunt primes question
In the comments to my post on the Google treasure hunt Andre asked me to put up my solution for the fourth problem. The problems were personalised and here is mine:
Find the smallest number that can be expressed as
the sum of 3 consecutive prime numbers,
the sum of 29 consecutive prime numbers,
the sum of 373 consecutive prime numbers,
the sum of 665 consecutive prime numbers,
and is itself a prime number.
The idea behind my solution is that if I have four lists of the sums, and a list of primes, then the solution to the problem is the smallest member of the intersection of all five lists.
I saved the problem of finding primes to the last and instead concentrated on summing up lists of integers in a convenient way. I ended up with the following solution to that:
sumN :: Int -> [Integer]
sumN n = map fst sumi
where
sumi = tail $ iterate (sumn) (0, primes)
sumn (r, xs) = (sum $ take n xs, tail xs)
The real work happens in the inner functions. sumn picks out as many numbers as I want and sums them up, the reason for taking and returning a tuple is that sumi can use iterate to calculate the sequence of sums. The first item in the result of iterate a is a, so sumi drops the first one. This lets me create the needed lists of sums:
sum3 = sumN 3 sum29 = sumN 29 sum373 = sumN 373 sum665 = sumN 665
After having a quick look at the implementation of Data.List.intersect I realised it probably would be a bit too slow. Instead I wrote one that exploits that all the involved lists are ordered:
intersection a@(x:xs) b@(y:ys)
| x == y = x : intersection xs ys
| x < y = intersection (dropWhile (< y) xs) b
| x > y = intersection a (dropWhile (x >) ys)
After convincing myself that this code did what I wanted (basically through playing in GHCi using an incorrect definition of primes, primes = [1..]) I turned to the problem of finding the primes. Of course someone else had already written the Haskell code to find primes. That code fitted perfectly with mine since it produces an infinate list of Integers. Brilliant!
Finally here’s the main that allows me to compile the code and get the answer quickly (it’s slightly modified for the medium, basically I wrote it all on one, long line):
main :: IO ()
main = let
i1 = (primes `intersection` sum665)
i2 = (sum3 `intersection` sum373)
s = i1 `intersection` i2 `intersection` sum29
in
print $ head s
Compiled, it runs in about 5.5 seconds on my desktop machine.
Google Treasure Hunt, check!
I personally found the first one to be the trickiest, quite a bit of thinking with a colleague before we saw Pascal’s triangle in the problem. I was a bit worried that things would get trickier from there on. It surely didn’t.
The second, summing certain lines taken from files matching certain glob patterns, was easily solved with a short Haskell program.
The third, a routing problem was probably the easiest and I think most easily solved on paper. I did make a mistake though, which I caught before typing my answer into the webform.
The fourth one, adding sequences of primes, was fairly straight forward. I think it would have presented a bit more trouble if I didn’t make use of Haskell’s laziness and support for infinate lists though.
Silly realisation
I bet a lot of people would consider this to be fairly obvious, but today, while solving the fourth of Google’s Treasure Hunt problems I realised just how similar in essence laziness+infinate lists in Haskell is to generators in Python. It’s just much easier to work with the former
Linux 2.6.25 + nvidia module
I hope this will be out of date really soon, but here’s what I did to solve the problems I had with the nVidia driver after upgrading to the latest kernel in Sid (2.6.25). First download the file NVIDIA_kernel-169.12-2286310.diff.txt from this forum article. Then, as root do:
# cd /usr/src # m-a clean nvidia-kernel # tar -x -j -f nvidia-kernel.tar.bz2 # pushd modules/nvidia-kernel/nv # patch -p3 < NVIDIA_kernel-169.12-2286310.diff.txt # popd # m-a -O build nvidia-kernel
Now there’s a package ready for installation
Dealing with life in Haskell
I bet you have at least one silly little thing at work that, whenever it happens, you let out a sigh, maybe roll your eyes and whish that everyone would use a proper operating system. A few days I finally decided to do something about one of my things like that. At work, Windows users will at times for some strange reason, manually create directories inside their work area, even though the directories actually are under version control. Invariably they get the case wrong and due to an onfortunate combination of case insensitive filesystem on the client (Windows) and a version control system the cares about case (Perforce). This results in files ending up all over the place even though they belong in the same directory. The Windows users are none the wiser, they simply don’t see the problem. Since I use a sane system (Linux) I do notice, and when I see it I sigh and roll my eyes.
Here’s my take on solving the problem:
module Main where
import Control.Monad
import Data.Char
import System.Directory
import System.Environment
import System.FilePath
import System.IO.HVFS.Utils
import System.Posix.Files
data IFile = IFile
{ iFileIPath :: FilePath
, iFileIName :: FilePath
, iFileFull :: FilePath
} deriving (Show)
toIFile :: FilePath -> IFile
toIFile fp = IFile path file fp
where
path = map toLower $ takeDirectory fp
file = map toLower $ takeFileName fp
listFilesR :: FilePath -> IO [IFile]
listFilesR path =
recurseDir SystemFS path >>=
filterM doesFileExist >>=
mapM (return . toIFile)
linkFile :: FilePath -> IFile -> IO ()
linkFile dest ifile = do
createDirectoryIfMissing True newDir
createLink (iFileFull ifile) newFile
where
newDir = normalise $ dest </> (iFileIPath ifile)
newFile = newDir </> (iFileIName ifile)
main :: IO ()
main = do
args <- getArgs
listFilesR (args !! 0) >>= mapM_ (linkFile $ args !! 1)
Yes, this is the code I wrote in Literate Haskell, but I think I’d better not disclose my rant against clueless Windows users publically
Rubber and lhs?
Another dear lazyweb post.
Yesterday night I hacked up a silly little tool for use at work. Nothing spectaculari but I thought I’d try this Literate Haskell thing. I decided to go the LaTeX route and created a .lhs file. To my amazement rubber has a module for handling Literate Haskell, unfortunately it passes everything ending in .lhs through lhs2Tex. I didn’t really want to use lhs2Texii but I haven’t been able to find any way of changing rubber’s behaviour through its command line arguments. What I’d like is a way to disable a module for a single invocation. So, dear lazyweb, is there a way to do this from the command line?
So far I’ve worked around this by creating a symbolic link named MyTool.tex that points to the Haskell source, then I run rubber on the link. Not to much of a hazzle, but it’d be nicer to pass an argument to rubber.
- I’ll post the source here shortly.
- I’ll probably have a closer look at it later but for now I wanted to keep things as easy as possible.
Debian, lighttpd and MediaWiki
I just went through the exercise of setting up MediaWiki on a Debian Etch box, but instead of serving it using the common choice of Apache I wanted to use lighttpd. It seems the combination MediaWiki and Apache is well supported on Debian. There was even an install-time question whether I wanted the configuration files set up for me. Well, it’s boring to follow the common path, right?
It seems the combination MediaWiki and Apache is well supported on Debian. Luckily that doesn’t mean it’s difficult to serve it with lighttpd. Here’s how I configured things, and luckily it all seems to work just fine
First off, I installed mediawiki1.7, lighttpd, php5-cgi, and mysql-server. I made sure that aptitude only pulled in required packages and then I started un-choosing all Apache-related packages. By the time you get to installing MySQL you’ll be asked for a root password, that is if your debconf is set to ask medium-level questions.
Setting up MediaWikiThe Debian package for MediaWiki creates a site in /var/lib/mediawiki1.7 consisting mostly of symbolic links to the actual location of its files. I kept lighttpd’s default document root of /var/www and linked the two by creating a symbolic link /var/www/mw pointing to the MediaWiki site (/var/lib/mediawiki1.7).
Configuration of lighttpdFirst enable FastCGI by linking /etc/lighttpd/conf-available/10-fastgi.conf into /etc/lighttpd/conf-enabled/. Then go in and change the bin-path to point to /usr/bin/php5-cgi. To prepare for the MediaWiki configuration, enable mod_rewrite in /etc/lighttpd/lighttpd.conf and finally create the file /etc/lighttpd/conf-enabled/20-mediawiki.conf with the following contents:
url.rewrite-once = (
"^/$" => "/mw/index.php",
"^/wiki/([^?]*)(?:\?(.*))?" => "/mw/index.php?title=$1&$2"
)
Now it’s time to restart lighttpd.
Configuration of MediaWikiPoint a browser to http://your.server/mw/config/index.php to configure the site settings. When that’s done copy the file /var/lib/mediawiki1.7/config/LocalSettings.php one layer up.
That should be it! Enjoy!
Debian: pbuilder tip
I’m writing this mostly so that I’ll remember myself
If pbuilder --create fails when building a base image for Sid then it’s worth trying to build a base image for the stable release and then upgrade to Sid afterwards. The very manual way is pbuild --login --save-after-login.
Packages for omnicodec and dataenc
As promised I’ve now created Debian packages for omnicodec. Since dataenc is a pre-requisite for building from source there are packages for it as well.
I’ve uploaded the source to Debian Mentors here and here. As usual pre-built binaries are available from my own APT repo.
ctypes and flexible (zero-length) arrays
Dear lazyweb, I’ve been racking my brain trying to get information out of the following C struct in a nice way when using ctypes:
struct Foo
{
unsigned int length;
char name[];
};
I wrote a little C function to get instance of the struct easily into python:
struct Foo *
put_name(char *name)
{
struct Foo *foo = malloc(sizeof(struct Foo) + strlen(name));
foo->length = strlen(name);
memcpy(foo->name, name, foo->length);
return(foo);
}
Now, how do I actually get the full contents of Foo.name in python? The only way I could think of that actually works is to create a dummy-struct type in order to get the length out and then use it to dynamically create a new sub-class of ctypes.Structure, then create an instance based on the address of what was returned. I think the following shows it pretty clearly:
class FOO(Structure):
_fields_ = [('length', c_uint), ('name', c_char * 0)]
liblib = cdll.LoadLibrary('./_build/liblib.so')
c_put_name = liblib.put_name
c_put_name.argtypes = [c_char_p]
c_put_name.restype = POINTER(FOO)
def put_name(str):
f = c_put_name(str)
K = type('FOO%s' % f.contents.length, (Structure,),
{'_fields_' : [('length', c_uint), ('name', c_char * f.contents.length)]})
return K.from_address(addressof(f.contents))
I still think there ought to be some other way that ‘feels’ nicer. I mean the use of “short arrays” (declared as here with [], or zero size as supported by GCC, or the more portable array of size one) seems to be common enough to warrant some support from ctypes, right?
Any suggestions for improvements?
Kid’s play with HTML in Haskell
In my ever-continuing attempts to replace Python by Haskell as my language of first choice I’ve finally managed to dip a toe in the XML/HTML sea. I decided to use the Haskell XML Toolkit (HXT) even though it’s not packaged for Debian (something I might look into doing one day). HXT depends on tagsoup which also isn’t packaged for Debian. Both packages install painlessly thanks to Cabal.
As the title suggests my itch wouldn’t require anything complicated, but when I’ve previously have looked at any Haskell XML library I’ve always shied away. It all just looks so complicated. It turns out it looks worse than it is, and of course the documentation is poor when it comes to simple, concrete examples with adequate explanations. HXT would surely benefit from documentation at a level similar to what’s available for Parsec. I whish I were equipped to write it.
Anyway, this was my problem. I’ve found an interesting audio webcast. The team behind it has published around 90 episodes already and I’d like to listen to all of them. Unfortunately their RSS feed doesn’t include all episodes so I can’t simply use the trusted hpodder to get all episodes. After manually downloading about 20 of them I thought I’d better write some code to make it less labour-intensive. Here’s the complete script:
module Main where
import System.Environment
import Text.XML.HXT.Arrow
isMp3Link = (==) "3pm." . take 4 . reverse
myReadDoc = readDocument [(a_parse_html, "1"), (a_encoding, isoLatin1),
(a_issue_warnings, "0"), (a_issue_errors, "0")]
myProc src = (runX $ myReadDoc src >>> deep selectMp3Links >>> getAttrValue "href")
>>= mapM_ putStrLn
selectMp3Links = hasName "a" >>> hasAttrValue "href" isMp3Link
main = do
[src] <- getArgs
myProc src
The thing that took by far the most time was finding out that hasAttrValue exists. I’m currently downloading episodes using the following command line:
curl -L $(for h in $(runhaskell get_mp3links.hs 'http://url.of.page/'); do \
echo '-O' $h; done)
Yet another set of itches where Haskell has displaced Python as the utensil used for scratching.
Saddle, two SDDL related tools
I’ve just uploaded two small tools that makes it a little easier to deal with SDDL (Security Descriptor Description Language, this is a good resource for SDDL):
- saddle-ex - “extract” the security descriptor for a number of different kinds of objects
- saddle-pp - a pretty printer for an SDDL string
Full build instructions are included. Download the archive here.
The tools are written (mostly) in Haskell and I’ll probably upload it all to hackage at some point in the future. I’m holding out for a fix to ticket 2097 since a fix for it will allow me to add a third tool which I feel belong in the package.
Suggestions for improvements are always welcome, patches even more so
Omnicodec released
Four days ago I uploaded omnicodec to Hackage. It’s a collection of two simple command-line utilities for encoding and decoding data built on the dataenc. I’m planning on building a Debian package for it as soon as I find the time.
Haskell on Windows
Recently I’ve had reason to write a few tools for Windows. Nothing complicated, and since there was nothing “mission critical” (there hardly ever is for me ) I decided to try to write them in Haskell rather than Python or C/C++. This post contains some sort of recollection of my experience so far.
First off I should probably disclose that I don’t particularly like Windows. Besides feeling more at home on a Unix (Linux) system I find that Windows also upsets me on a very basic level. If I spend a whole day at work in Windows I tend to go home more stressed and irritated than after a day in Linux. Part of this is probably due to my familiarity with Linux. My hope was that the combination of the immense joy of programming Haskell and my loath of the Windows platform I would end up with something that at least was bearable. It turns out I did.
My setupBesides installing the pre-built GHC I also installed Visual Studio Express more later to explain the need for it. I don’t like the Visual Studio environment so I installed CMake and jEditi. Last but not least I installed Console, it addresses the fact that Windows’ “DOS-box” is an amazing piece of crap.
FFI on WindowsFirst, GHC comes with a number of Windows-specific modules and they cover an impressive number of the Win32 API functions. The Win32 API is simply huge and one will sooner or later come find the need to add to what those modules offer. Second, GHC is able to compile C code by delegation to MinGW, however MinGW doesn’t completely cover the Win32 API either and if one is unlucky MinGW isn’t enough for the task at hand. Of course that’s exactly what happened to me. So, I installed Visual Studio Express, but since I don’t like VS that much and I didn’t want VS solutions in my darcs repository I decided to use CMake to build a library that I then instruct GHC, through a Cabal file, to link with my Haskell code. The end result is that building requires a few extra steps before the familiar configure/build sequence. It works remarkably well really, and I’ll definately use that strategy again if I need to.
There is a benign warning thrown when linking the final executable though:
Warning: .drectve `/manifestdependency:"type='win32' name='Microsoft.VC90.CRT' version='9.0.21022.8' processorArchitecture='x86' publicKeyToken='1fc8b3b9a1e18e3b'" /DEFAULTLIB:"uuid.lib" /DEFAULTLIB:"uuid.lib" /DEFAULTLIB:"MSVCRT" /DEFAULTLIB:"OLDNAMES" ' unrecognized
It seems that it might be possible to skip the extra steps in the future if Cabal ticket #229 is addressed.
Windows System modulesAdmittedly I haven’t been using much of the functionality in these modules, but it happens that the only function I needed had a bug that results in a segmentation fault, sometimes. See GHC ticket #2097 for some details. I guess this confirms my impression of most Haskell hackers being Linux/BSD/Unix users.
ConclusionsI won’t drop Haskell on Linux anytime soon, but I’ve found Haskell on Windows to be possible. As I suspected when I started out, Haskell does make Windows somewhat easier to bear.
- ordinarily I would install Vim but I thought I’d try out another editor. Vim on Windows is somewhat “leaky”, i.e. it sometimes shows behaviour that betrays its Unix roots.
Rotonyms in Haskell
I have to say rotonyms seem kind of pointless, but since there is a post with a Python solution I thought I’d make an attempt at a solution in Haskell. Of course I didn’t manage on my own, I received some much needed help from Cale and dmwit on #haskell.
First some rotation functions, as far as I know there’s no built-in rot13 encoding in Haskell:
rot13Char c = chr ( (ord c - ord 'a' + 13) `mod` (ord 'z' - ord 'a' + 1) + ord 'a') rot13 = map rot13Char
In order to ease working with rotonyms I introduced a type to represent one. This turned out to pay off later on.
data Rotonym = R String
It would be easy to let the compiler derive Show, but I wanted to mimick the output produced by Will’s solution in Python:
instance Show Rotonym where
show (R w) =
let r = rot13 w
in (min w r) ++ "\t" ++ (max w r)
Now I’m ready for the meat of the matter, reading the word list, pick out the rotonyms and finally print them. Following Will’s cue I represent the word list as a set of strings (importing Data.Set as S), this also eliminates duplicates.
main = do
words <- liftM lines $ readFile "WORD.LST"
let wordset = S.fromList words
isRotonym w = S.member (rot13 w) wordset
rots = S.fromList [R w | w <- words, isRotonym w]
mapM_ (putStrLn . show) (S.elems rots)
Sticking Rotonym instances in a set requires them to be instances of Ord and Eq:
instance Eq Rotonym where
(R w1) == (R w2) =
let r1 = rot13 w1
r2 = rot13 w2
in (w1 == w2 && r1 == r2) || (w1 == r2 && w2 == r1)
instance Ord Rotonym where
compare (R w1) (R w2) =
let r1 = rot13 w1
r2 = rot13 w2
in compare (length w1, (min w1 r1)) (length w2, (min w2 r2))
dmwit pointed out that what is actually going on here is taking an intersection of the the words and their rotated counterparts. This means the main could be written
main = readFile "WORD.LST" >>=
mapM_ (putStrLn . show) . S.toList . S.map R . findRotonyms . S.fromList . lines
where findRotonyms ws = ws `S.intersection` (S.map rot13 ws)
Another idea that dmwit came up with was to introduce a class for rot13:
class Rot13 a where
rot13 :: a -> a
Char is an instance of that class with the expected implementation of rot13:
instance Rot13 Char where
rot13 c = chr ((ord c - ord 'a' + 13) `mod` (ord 'z' - ord 'a' + 1) + ord 'a')
If a is an instance of Rot13 then list of a is as well, again with the expected implementation:
instance (Rot13 a) => Rot13 [a] where
rot13 = map rot13
It is possible to intersect lists (Data.List.intersect) but it turned out to be painfully slow, so back to sets again. A set of a is an instance of Rot13:
instance (Ord a, Rot13 a) => Rot13 (S.Set a) where
rot13 = S.map rot13
Finding all rotonyms is then straight forward:
main = readFile "WORD.LST" >>=
mapM_ (putStrLn . show) . S.toList . S.map R . findRotonyms . S.fromList . lines
where findRotonyms ws = ws `S.intersection` (rot13 ws)
Back to listening to pauldotcom
I just began listening to episode 95 of pauldotcom and was glad to hear that they enjoyed my email. Here’s the complete email I sent them:
Well, something must have changed since I last communicated with you (see http://therning.org/magnus/archives/257). I’m not sure what though. I heard you when you were on the Linux Reality audio cast and thought I’d check you out again, just to see what you were up to. Well, episode 92 (both parts) was bloody brilliant, episode 93 was good too, and now I’m halfway into episode 94. I have no recollection of the earlier episodes being this organised and good. At some point when I wasn’t listening you must have learnt to rock!
I enjoy the tech segment. The amount of banter is down and the episodes
move along a lot more than I remember. No offence to Twitchy, but I’m
not sad he isn’t as involved any more, you know, Kramer is brilliant but
Seinfeld just wouldn’t be a good show if he were in each and every
scene. Twitchy has more of a “celebrity guest” personality… The only
criticism I have, and this is pushing it I know; given my walk to work
I’d prefer each episode to be around 60 minutes, rather than 80-90
Keep it up!
/M
PS I’m planning on posting this email on my blog. I’ll put any reply from you on there as well.
Reading my email on the show sure beats any reply they could have sent by email At some point I have to go back and check out the other podcast I stopped listening to…
BSD or GPL?
Today I had a long and interesting discussion about what is “more free”, GPL or the BSD license. I did a little searching on the internet afterwards and found the following posts quite illuminating:
- GPL and BSD: Which is more “free?”
- Is the BSD license more or less restrictive than the GPL?
- GPL vs BSD, a matter of sustainability
I’ll refrain from saying where I come down on this issue
The KLM way of respecting privacy…
I just received an email from KLM UK. I have probably given them my email address and thereby my consent to them sending me “informative emails”. Still, I think their words sound a bit hollow when the link to unsubscribe takes me to doubleclick:
If you do not wish to receive future communication from us click here to unsubscribe. KLM is firmly committed to respecting your privacy. We don’t share your information with any third party without your consent.
Shame on you!
A visit to the golden prison
My wife managed to win an iPod Touch a the office Christmas party. I got more excited than her; she actually suggested we put it on eBay unopened, of course I simply had to open it and play a little. After a weekend I came to the conclusion that, to me, it was a piece of useless crap that we should try to sell ASAP. Luckily we managed to sell it on to someone who’s recently had a large sip of the Apple Kool-Aid. Here’s what I found out anyway, let’s start with the least bad.
The UIIt’s cute, very cute. Clicking icons, typing in the “keyboard” all very enjoyable. I tried out the zooming in Safari, beautiful. Then the cracks started showing, I can’t zoom everywhere, suggesting that it’s implemented on an application level. Why not provide that on a system level instead, so that all applications have it automatically? I also found it really irritating that there’s no copy-paste (apparently a common gripe). After I broke the jail of the 1.1 firmware and installed a audio cast client I had to use a pen and paper to copy URLs from Safari in order to subscribe. Poor!
Browsing the webGetting network connectivity was a breeze. The UI of Safari is cute and the zoom is really handy. The first thing that irritated me was that there’s no way of saving things. Yes, there’s WiFi available in many large cities nowadays, but there’s still a lack of wireless connectivity outside of cities. So, my hope of being able to look for things while online and read while offline was a no-starter. I also would have liked to download videos and watch them later, on the other hand, and this is such a ridiculous mistake by Apple since it basically breaks the web, there’s no support for flash. Yes, the format that basically everybody uses to post videos online is not supported! Oh, but there’s YouTube you say? Well, on to that then…
The YouTube applicationThe only way of watching videos on YouTube is through this application. Surprisingly it’s not possible to use Safari to browse around using YouTube’s well-known web interface and find interesting things to watch that way. No flash support, remember?
On top of this there is no way of saving a video to watch it later. Again, listen Apple, there are areas that don’t have WiFi connectivity in the world!
Loading things on to the iPod TouchI found this to be most disappointing. The only way to get stuff, music/video/audio cast, on to it one must use iTunes. There are rumours of support in bleeding edge libgpod, but by this time I didn’t bother with trying that out. What I did try was breaking the jail, installing OpenSSH, mounting it using SSHFS just to find out I only had read access in the versions of gtkpod/libgpod that’s in Debian Sid. Then I tried installing iTunes in WINE, but gave up after a few hours of trying to get that working. The next attempt was to use VMWare, using an evaluation license for Workstation I got as far as installing iTunes just to find out that it wouldn’t accept the iPod Touch when I plugged it into the USB port. After all of this, and my other findings, I didn’t think it’d be worth compiling libgpod from source.
Other bits and piecesI’ve heard the calendar and contacts can only be synced to a Mac. Of course I couldn’t try it, since I don’t have a Mac.
The iTunes application on the device itselfi only contains just enough to spend money on the iTunes store. No way to subscribe to audio casts that I could findii.
ConclusionsI’ve never thought quite as much about the words “proprietary” and “technological silo” as I did while playing with the iPod Touch. The experience has put me off all Apple products, sure they are beautiful and cute, but to me they aren’t usable.
- I can’t remember if it were on there when I first opened it of if it only appeared after upgrading to firmware version 1.2.
- I could always set up a personal audio cast containing my music had it been possible.
A somewhat surprising catch
Let’s get straight to it. Here’s an example of something that I found somewhat surprising in Haskell. First a bit of setup:
printNum n = putStrLn $ "num: " ++ (show n)
handleE e = do
putStrLn $ "Caught something: " ++ (show e)
return (-1)
errorP = fromMaybe (error "Got Nothing")
And here it is, in ghci:
> CE.catch (return $ errorP Nothing ) handleE >>= printNum num: *** Exception: Got Nothing
And to show that things are lazy we change handleE:
handleE e = do
putStrLn $ "Caught something: " ++ (show e)
return []
Then we can map errorP onto a list like this:
> CE.catch (return $ map errorP [Just 17, Just 42, Nothing, Just 666]) handleE [17,42,*** Exception: Got Nothing
In neither cas I saw the behaviour I was expecting. A chat on IRC showed that others see this as natural behaviour, explained by laziness. It wasn’t until a night’s sleep that I realised that there still was something that bothered me about that explanation. Another explanation would be that catch isn’t special. At first I didn’t realise I expected it to be special; I expected it to somehow wrap the evaluation of its first argument so that no matter when it was evaluated any exception raised would be caught. As far as I can see this would be no small feat if laziness is to be preserved. It would require catch to be special.
So, what does this mean in practice? Well, here are my thoughts. One needs to think carefully about where using catch makes sense in a program. It has to be inside IO, a well-documented fact, but it also has to cover something that isn’t lazy since it then will have no effect at all. My gut feeling is that catch is useful “in the large”, with that I mean as a sort of catch-all “high up” in the program, e.g. in main. That means its usefulness in libraries is limited (except for IO heavy libs, like FFI bindings to C), it should also probably not be used like try-catch often is used in Python.
I’ve since taken a look at the ErrorT monad transformer and it seems it behaves like I expected catch to. That’s for another post though.
Mail!
Yes, I think there’s an opening for an email client, it doesn’t have to be written in Haskell of course, but if I ever get my arse into gear it will be. Especially now that mutt-ng seems to have stalled in development, and even though mutt still is being developed I’ve gotten too spoilt by using mutt-ng exclusively for the last year or so. I’ve looked extensively at sup and it’s sweet, but due to some recent changes in what kind of machines I have access to on the web it doesn’t quite fit me anymore.
What would my ideal email client look like?
- GMail as backend, accessed through Python’s libgmail. Hopefully it won’t be too difficult to write a Haskell module to deliver this part, but using Python to begin with is absolutely acceptable.
- Haskell for the frontend, specifically using vty for the UI.
- Vim, Yi, or any other old terminal-based editor to write email.
I’m confident vty has enough functionality. I’ve played with libgmail enough to be confident it offers enough access to mail data to do most everything I want from a client (the missing part is sending PGP/MIME messages, but sending mail through Google’s SMTP server is a workable solution). I’ve just started looking at options for mail parsing in Haskell, identifying three and already discarding one…
Yes, it’s all vapourware at this point, but hey, I can dream, right?
N-Queens in Haskell
After reading the chapter on options, exceptions, and failure continuations from Programming in Standard ML I thought spending a few minutes on translating the code to Haskell might be fun.
I should start with a disclaimer, I’ve never coded in SML, never even read any article or book about the language or even looked at code written in it. Nevertheless I seem to have produced runnable, and presumably correct, code in a fairly short amount of time. I’ve tried to stay as close to the original code as possible, there are undoubtably better and more effective way of writing the same code in Haskell. Feel free to provide comments with improvements
First the representation of the board:
data Board = Board Int Int Int [(Int, Int)]
| NoBoard
deriving (Show)
Then some functions to manipulate a board:
new n = Board n 1 0 []
size (Board n _ _ _) = n
complete (Board n _ k _) = k == n
positions (Board _ _ _ qs) = qs
place (Board n i k qs) j = Board n (i + 1) (k + 1) ( (i, j) : qs)
threatens (i, j) (i', j')
| i == i' = True
| j == j' = True
| i + j == i' + j' = True
| i - j == i' - j' = True
| otherwise = False
conflicts q [] = False
conflicts q (q':qs) = threatens q q' || conflicts q qs
safe (Board _ i _ qs) j = not $ conflicts (i, j) qs
These are all straight-forward translations, within minimal “haskell-ifications”.
The first solution using Maybe and explicit checks for failure:
addqueenM bd =
let try j = if j > size bd
then Nothing
else if safe bd j
then case addqueenM (place bd j) of
Nothing -> try $ j + 1
Just bd' -> Just bd'
else try $ j + 1
in
if complete bd
then Just bd
else try 1
queensM = addqueenM . new
The second uses exceptions to avoid the explicit check (note that I’ve imported Control.Exception as CE to avoid the clash with Prelude’s catch; see the documentation of catch if you don’t know why that’s necessary):
addqueenE bd =
let try j = if j > size bd
then error "no more space on board"
else if safe bd j
then CE.catch (addqueenE (place bd j)) (\ e -> try $ j + 1)
else try $ j + 1
in
if complete bd
then return bd
else try 1
queensE n = CE.catch (addqueenE $ new n) (\ e -> return NoBoard)
The last translated version uses an explicit failure continuation to avoid both checking results and dealing with exceptions:
addqueenC bd fc =
let try j = if j > size bd
then fc
else if safe bd j
then addqueenC (place bd j) (try $ j + 1)
else try $ j + 1
in
if complete bd
then Just bd
else try 1
queensC n = addqueenC (new n) Nothing
So far so good, but since this is Haskell, what about monads? Minor changes results in the following somewhat general version of addqueenX:
addqueenH bd =
let try j = if j > size bd
then mzero
else if safe bd j
then addqueenH (place bd j) `mplus` (try $ j + 1)
else try $ j + 1
in
if complete bd
then return bd
else try 1
With that it’s possible to lean on the type system to get something that’s similar to queenM from above:
queensHM :: Int -> Maybe Board queensHM = addqueenH . new
It’s also easy to write a version that calculates all solutions given the size of the board:
queensHL :: Int -> [Board] queensHL = addqueenH . new
Slightly embarrassed about continuations…
Recently I’ve spent some time trying to understand continuations better. First off I have to admit to being a bit daft because it was only recently that I realised that call-with-current-continuation (call/cc in Scheme and callCC in Haskell) actually means “call foo with the current execution point as continuation” rather than “call foo with the continuation passed to the current function”. Well, there’s no way to explain it besides daftness I guess, even though I’d like to think that my decision to look at continuations in Haskell (callCC) to learn about them (the Cont monad just might have confused me somewhat). I really should have started by looking at continuations in Scheme (call/cc). The best description I’ve come across so far is Applications of Continuations.
I still find it somewhat confusing, as can be seen in my latest use of hpaste, but it’s somewhat clearer now than before. At least I seem to be able to almost reason my way through code I write myself, but doesn’t do what I expect
I’m not being alone in thinking del.icio.us is crap
Ah, someone else is feeling the pain with the del.icio.us API.
Interesting information about throttling on usage of posts/all. It all adds up to del.icio.us API being nearly useless for experimentation and interesting new uses of bookmarks. I’m just so happy there are other social bookmark sites that don’t put whimsical limitations on API usage.
Some hope on identity fraud
After the recent cock-up by HMRC I find myself a bit more hopeful for the future.
Hopefully the politicians will start asking themselves if it really is such a good idea to collect information in huge databases. Should we really have ID cards? Is it a good idea to have a huge database with details of every child in the country?
I’m still wondering why it’s possible to “steal someone’s identity” by knowing only what HMRC knows about a parent that receives child support…
Epilicious losing support for del.icio.us
I was getting too many reports of problems on using epilicious together with del.icio.us. What finally did it was Gnome bug #491977. The patch provided was applied in the 2.20 tree. In the current development tree I simply removed support for del.icio.us alltogether. It’s just not worth the hassle!
It’s just somewhat unfortunate that the name of the plugin doesn’t fit that well anymore.
Computer security and liability—my thoughts
Almost three years ago Bruce Schneier posted a blog entry on Computer Security and Liability. Since then he has repeated his opinion several times; one of the more high-profile occasions was in front of the House of Lords. Some people agree, others disagree.
Until just a few days ago I disagreed with him on this particular issue. After the four learned hosts of LugRadio brought up the issue in episode 3 I had another think and I’ve now changed my opinion. I am now in favour of holding companies financially liable for damages resulting form security vulnerabilities in software products.
The software business is interesting because there’s a very obvious asymmetry in what is known about a product between the people who write and sell software and the people who use and buy software. Bruce Schneier has touched on that as well in his post on Security Lemons. Basically the buyer of software knows nothing of the ilities of what they are being sold, so there is very little to hang an informed decision on.
I think that introducing financial liability for software producers should take into consideration whether a buyer can make an informed decision before buying or not. This means that in cases where the buyer has full access to the sourcei there will be no financial liability on the developer. It would be enough to offer all source code under an NDA to a buyer before the deal is finalised. Basically liability would be the price a software vendor has to pay to keep the buyer in the dark regarding how secure the product is.
- Note that the source doesn’t have to be free as in having all four freedoms granted by e.g. the GPL.
Aha-one-liners
I’ve been working with computers for more than seven years now and before that I spent five and a half years in university studying computer science and engineering. During these years I’ve learnt a lot and had many aha-moments. However, since starting learning Haskell I’ve had aha-moments that manifest themselves in a single line of code. This has never happened before. Ever! I’m not sure what that says about Haskell. Maybe it’s computer science distilled, who knows?
Anyway, my latest aha-one-liner is this:
liftM dec $ sequence $ map (flip M.lookup decodeMap) s
I’ll try to recount how I got to it.
When writing dataenc I wrote a function decode :: String -> [Word8]. In a discussion on the Haskell libraries list apfelmus pointed out the necessity of allowing decode to fail. The obvious solution is to change the type to String -> Maybe [Word8].
The decoding is done using a look-up table, with some twiddling of bits to get the original data back from the encoded string. The first version used ! to do the lookup, but when this fails it throws an exception. There have been many emails on Haskell Cafe and several articles written on exceptions in Haskell, and as anyone who’s read them know: it’s better to avoid ever getting exceptions than dealing with them (I suspect this is true for any language). The function lookup offers a nice way of looking up a value without risking getting an exception. By mapping it over t