Posts

When debugging or profiling Haskell code, it’s common practice to pepper it with cost centre annotations, often called SCC (for strongly connected component set cost centre) annotations. If you compile a program using ghc -prof -auto-all, this causes all of the top-level names in every module you compile to automatically be annotated with their names, which will show up in a profile file later on when you run your program with +RTS -P -RTS. ...

Tim Bray has recently been writing about a simple log file processing task, giving his efforts the (decidedly peculiar) name of Wide Finder. The task at hand is to count popular links in an Apache log file. Here’s my two minutes’ worth of hat in the ring, in Haskell. > main = do > args <- getArgs > forM_ args $ \name -> do > m <- (foldl' count M.empty . LB.lines) `fmap` LB.readFile name > mapM_ print ((take 10 . sortBy (flip compare `on` snd) . M.toList) m) > where on f g x y = g x `f` (g y) > count m line = case line =~ "\"GET /en/([^ ]+\\.html)" of > ((_:g:_):_) -> M.insertWith' (+) g 1 m > _ -> m :: M.Map LB.ByteString Int Here’s some comparable Python: ...

I’ve spent a few spare hours here and there working on a pure Haskell interface to MySQL recently. On the principle that perhaps someone else might want to join in the fun, I’ve published a darcs repository already (see the link above for more details): <br /> darcs get http://darcs.serpentine.com/mysql<br /> There are a few reasons I’m doing this. One is licensing-related: the existing hsql-mysql bindings claim to be BSD-licensed, but they’re just an FFI wrapper around the MySQL client library, so they (and any program that uses them) are subject to the GPL. My library speaks the MySQL wire protocol in pure Haskell, and I’ve BSD-licensed it. ...

Some months ago, I wrote a Python implementation of Daniel Lemire’s Weighted Slope One collaborative filtering algorithm. Steve Jenson sent me a pointer to his Scala implementation last week, but his code is a straight port of the Python version, not using any of Scala’s tasty functional crunchiness. In an idle period the other evening, I ported my Python code to Haskell. module SlopeTwo (Rating, SlopeOne, empty, predict, update) where import Data.List (foldl') import qualified Data.Map as M newtype SlopeOne a = SlopeOne (M.Map a (M.Map a (Int, Double))) deriving (Show) type Rating a = M.Map a Double empty = SlopeOne M.empty addT (a,b) (c,d) = let (l,r) = (a+c, b+d) in l `seq` r `seq` (l, r) update :: Ord a => SlopeOne a -> [Rating a] -> SlopeOne a update (SlopeOne s) = SlopeOne . M.map (M.map norm) . foldl' update' s where norm (a,b) = (a, b / fromIntegral a) update' s rm = foldl' (\m (k, v) -> insert m k v) s prod where prod = [((a, b), (1, m - n)) | (a, m) <- rs, (b, n) <- rs] rs = M.toList rm insert m (a, b) v = M.alter foo a m where foo = Just . maybe (M.singleton b v) (M.insertWith' addT b v) predict :: Ord a => SlopeOne a -> Rating a -> Rating a predict (SlopeOne s) rm = let freqm = foldl' insert M.empty [(a,b,r) | (a, m) <- M.keys s, (b, r) <- M.toList rm] insert n (a,b,r) = let (f, d) = find s (a, b) in M.insertWith' addT a (f, fromIntegral f * (r + d)) n norm = M.map (\(a, b) -> b / fromIntegral a) freqm find m (a,b) = M.findWithDefault (0,0) b (M.findWithDefault M.empty a m) in M.filterWithKey (\k v -> v > 0 && M.notMember k rm) norm The Haskell code uses essentially the same approach as the Python code, though of course it has to use purely functional maps instead of dicts (hash tables), because hash tables don’t make much sense in a functional language. I also cut down the number of maps from two to one, which simplified the code a little. ...

A few days ago, I wrote a Haskell library for building and working with suffix trees. It builds a suffix tree lazily, so even though its performance is O(n log n) on large input strings, it often has linear performance for many applications. The implementation is simple and easy to read; the API is well-documented and easy to use; and the internals of the tree structure are exposed, so you can build your own traversal, inspection, and manipulation functions on top of it. The code is liberally licensed (BSD3), to encourage wide use. ...

I’ve had an account on del.icio.us for several years, but I only started using it heavily perhaps a year ago. While it’s a wonderful site in many respects, I’ve been surprised and disappointed by what’s happened since Yahoo acquired the company: nothing at all. Clearly, Yahoo has had no idea what to do with their acquisition: almost its first reaction to the grafted del.icio.us antibodies was to roll out a homegrown NIH tagging site, the name of which nobody now remembers. Since then, Yahoo hasn’t even bothered to switch users over to its unified login system as it did with Flickr. Whether you liked that move or not, it was a clear sign that Yahoo had some interest in Flickr. ...

Irish television hasn’t changed much since I left the country twelve years ago. The main national broadcaster, RTÉ, mainly serves up imported American and British shows, with locally originated fare dominated by vast quantities of sports coverage, a few soaps and talk shows, and the occasional documentary. It’s a tepid, uninspiring mix. Except for one show, that is. Soupy Norman is a Polish soap opera (Pierwsza miÅ‚ość), dubbed into English and utterly twisted out of recognition by a team of Irish comedians. The writing, air of absurdity, and comic timing are pitch-perfect. (Mind you, the Cork accents might be a bit tough for non-native ears to decipher. My wife kept asking me “can you really understand what they’re saying?”) ...

Here’s a great quote from Yaron Minsky about the use of types in functional programs. […] most of the advantage of types in a language like ML comes from completely vanilla uses of the type system. One of our programming maxims at Jane Street is to “make illegal states unrepresentable”. Algebraic datatypes, parametric polymorphism and abstraction can be used to great effect in this regard. I think that people who are new to ML think of the type system as merely a constraint, that is to say, you write code as you did before, and then you see whether the compiler accepts it. As people get more experienced, they start to use the type system as a tool in its own right, and one of the things that is constantly on one’s mind is how to pass off as much of the proof burden as possible to the compiler. Most of this work can and should be done using boring old vanilla ML types. ...

Here’s a fabulous way to start a research paper. In 1995, McArthur Wheeler walked into two Pittsburgh banks and robbed them in broad daylight, with no visible attempt at disguise. He was arrested later that night, less than an hour after videotapes of him taken from surveillance cameras were broadcast on the 11 o’clock news. When police later showed him the surveillance tapes, Mr. Wheeler stared in incredulity. “But I wore the juice,” he mumbled. Apparently, Mr. Wheeler was under the impression that rubbing one’s face with lemon juice rendered it invisible to videotape cameras. The paper in question, Unskilled and Unaware of It: How Difficulties in Recognizing One’s Own Incompetence Lead to Inflated Self-Assessments is a great read. Personally, I have my nose rubbed in the evidence of my own ineptitude often enough that I hope that I’m not in the category of people the authors study. That said, “but I wore the juice!” has now become my catch-all excuse for error. ...

I’ve been running test releases of Fedora 7, and lately the final release, for a number of months on my fairly new Lenovo Thinkpad X60. Here’s a brief summary of my experiences. I’ve been using Fedora since 0.92 (Taroon), and while I’ve generally been happy with it, F7 is not exactly a model of stability or sleekness. Here’s a list of problems I’ve run into. My biggest problems so far have been with suspend and resume, and network drivers. ...