therning.org/ magnus

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

Another dear lazyweb post.

Yesterday night I hacked up a silly little tool for use at work. Nothing spectacularⁱ 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 lhs2Texⁱⁱ 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.

1. I’ll post the source here shortly.[back]
2. I’ll probably have a closer look at it later but for now I wanted to keep things as easy as possible.[back]

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.

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):

1. saddle-ex - “extract” the security descriptor for a number of different kinds of objects
2. 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

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 package. I’m planning on building a Debian package for it as soon as I find the time.

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 setup

Besides 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 jEditⁱ. Last but not least I installed Console, it addresses the fact that Windows’ “DOS-box” is an amazing piece of crap.

FFI on Windows

First, 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 modules

Admittedly 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.

Conclusions

I 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.

1. 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.[back]

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)

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.

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?

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