talkingCode

Archive for June, 2008

Coding style, Haskell

posted by codders in haskell, rant

I finished chapter five of the Haskell book I’m reading last night, and the bits of it are starting to make sense. I was doing some of the exercises and managing to write functions that compiled first time – I’m all about the small victories.

What I’m enjoying most about the book, though, is that as well as teaching the language it does a good job of teaching some of the culture. A lot of writing good software is about making the most effective use of the tools a language provides and that usually only comes with time and experience. The book helps, though, providing gentle prods in the right direction:

Many tail recursive functions are better expressed using list manipulation functions like map, take, and filter. Without a doubt, it takes some practice to get used to using these. What we get in return for our initial investment in learning to use these functions is the ability to skim more easily over code that uses them.

The reason for this is simple. A tail recursive function definition has the same problem as a loop in an imperative language: it’s completely general, so we have to look at the exact details of every loop, and every tail recursive function, to see what it’s really doing. In contrast, map and most other list manipulation functions do only one thing; we can take for granted what these simple building blocks do, and focus on the idea the code is trying to express, not the minute details of how it’s manipulating its inputs.

In the middle ground between tail recursive functions (with complete generality) and our toolbox of list manipulation functions (each of which does one thing) lie the folds. A fold takes more effort to understand than, say, a composition of map and filter that does the same thing, but at the same time it behaves more regularly and predictably than a tail recursive function. As a general rule, don’t use a fold if you don’t need one, but think about using one instead of a tail recursive loop if you can.

As for anonymous functions, they tend to interrupt the “flow” of reading a piece of code. It is very often as easy to write a local function definition in a let or where clause, and use that, as it is to put an anonymous function into place. The relative advantages of a named function are twofold: we’re not confronted with the need to understand the function’s definition when we’re reading the code that uses it; and a well chosen function name acts as a tiny piece of local documentation.

… and they’ve not once suggested I write any comments yet. Woot :)

The Book:

http://book.realworldhaskell.org/beta/

Chapter 5:

http://book.realworldhaskell.org/beta/fp.html

More Haskell fun

posted by codders in code, haskell

Define a tree type that has only one constructor, like our Java example. Instead of the Empty constructor, use the Maybe type to refer to a node’s children.

Fair enough. How bout this?

data MaybeTree a = MaybeNode (Maybe (a (MaybeTree a) (MaybeTree a)))

It’s a real type. I can even make real values in the type:

maybeTree = MaybeNode (Just ("fish",
             (MaybeNode (Just ("left", 
                               (MaybeNode Nothing),
                               (MaybeNode Nothing)))),
             (MaybeNode (Just ("right",
                               (MaybeNode Nothing),
                               (MaybeNode Nothing))))))

Buuut I can’t print them. Because I don’t derive Show. If I try to derive Show:

    No instance for (Show (a (MaybeTree a) (MaybeTree a)))
      arising from the 'deriving' clause of a data type declaration
                   at working.hs:(51,0)-(52,30)
    Possible fix:
      add an instance declaration for
      (Show (a (MaybeTree a) (MaybeTree a)))
    When deriving the instance for (Show (MaybeTree a))

That’s fair enough. And GHC’s even provided me with a hint. So I just… err… instance Show something, right? Wrong :(

Let’s write the show function for my tree type:

showTree (MaybeNode Nothing) = "empty"
showTree (MaybeNode (Just (a, b, c))) = "Node: " ++ (show a) ++ 
              ", Left: " ++ (showTree b) ++ 
              ", Right: " ++ (showTree c)

s’all good. But the type of that function?

showTree :: (Show t) => MaybeTree ((,,) t) -> [Char]

See that ((,,) t)? That’s the badness.

*Main> :kind (,,)
(,,) :: * -> * -> * -> *

Yeah. So it’s a tuple that has three type variables. Fun. Now I’m pretty sure that I ought to be able to define an instance of Show for my type, but I can’t for the life of me work out what the syntax is going to be

instance (Show a) => Show (MaybeTree ((,,) a)) where
       show t = showTree t

working.hs:58:0:
    Illegal instance declaration for `Show (MaybeTree ((,,) a))'
        (All instance types must be of the form (T a1 ... an)
         where a1 ... an are distinct type *variables*
         Use -XFlexibleInstances if you want to disable this.)
    In the instance declaration for `Show (MaybeTree ((,,) a))'

??? How about

instance (Show a) => Show (a, MaybeTree a, MaybeTree a) where
        show t = showTree t

working.hs:61:40:
    Kind mis-match
    Expected kind `* -> * -> *', but `a' has kind `*'
    In the type `MaybeTree a'
    In the type `(a, MaybeTree a, MaybeTree a)'
    In the type `(Show a) => Show (a, MaybeTree a, MaybeTree a)'

Any answers much appreciated, glorious lazyweb. I’m adding this to the list of exercises in the book that you can’t answer at the point you’ve reached in the book (this is chapter 4). Even after reading around about types and kinds and other peoples’ use of instance, I’m clueless.

And changing my type to be something sane doesn’t count. If it’s not possible to Show my type, I’d like to know why :)

Update:
After much discussion with sffubs and sos, it seems the only reasonable thing to do is to

{-# LANGUAGE FlexibleInstances #-}
instance (Show t) => Show (MaybeTree ((,,) t)) where
  show = showTree

We’re not quite sure what Flexible Instances are, but it seems that’s what’s needed to make this datatype work. The real answer is obviously not to use a crazy datatype:

data FooTree a = Maybe a ((FooTree a), (FooTree a)) deriving (Show)

Thanks both.

Getting started with Haskell… still

posted by codders in code, haskell

I can’t help but think there’s a bit of a gap in the market for introductory texts on Haskell. I say this in part because, at time of writing, if you google (hah! I’m using it as a verb! Trademark that!) “Getting Started Haskell”, you might end up here =/

I’d resolved to try getting started again on account of continuing to hear people rave about the language, so last night I did what I always do when learning something new – I googled “Getting Started X”. I found this awesome e-book / blog:

http://book.realworldhaskell.org/beta/index.html

It’s very well written (if a little rough round the edges – beta is the word), but I still think the learning curve presented is a _little_ steep for simpletons like myself. Bear with me while I expose my ignorance.

We’re using GHC. GHC is recommended by the book, it’s recommended by Don (who is indescribably leet: http://cgi.cse.unsw.edu.au/~dons/blog/), and it’s recommended by my n-sim colleagues (who mostly are, except for me: http://www.n-sim.com).

# apt-get install ghc6
# ghci
GHCi, version 6.8.2: http://www.haskell.org/ghc/  : ? for help
Loading package base ... linking ... done.
Prelude>

aaah. Prelude. Don’t I feel at home. In fact I don’t – this is all pretty weird, but working through the first couple of chapters of the book was fun. Walk with me a while…

Type Porn
If types don’t excite you, this probably isn’t the language for you. But they should; they’re awesome.

Prelude> :set +t
Prelude> 1337
1337
it :: Integer

In GHCI (interactive GHC interpreter), setting “+t” makes the interpreter print the type of whatever you’ve just evaluated. Technically, it prints the type of “it” – the special value in to which your last evaluated expression is loaded (there is no spoon, there are no variables). I know what “1337″ is, I know what “it” is, but what’s “Integer”?

Prelude> :info Integer
data Integer
  = GHC.Num.S# GHC.Prim.Int#
  | GHC.Num.J# GHC.Prim.Int# GHC.Prim.ByteArray#
        -- Defined in GHC.Num
instance Enum Integer -- Defined in GHC.Num
instance Eq Integer -- Defined in GHC.Num
instance Integral Integer -- Defined in GHC.Real
instance Num Integer -- Defined in GHC.Num
instance Ord Integer -- Defined in GHC.Num
instance Read Integer -- Defined in GHC.Read
instance Real Integer -- Defined in GHC.Real
instance Show Integer -- Defined in GHC.Num

ooo… fancy. What does that all mean? Well, I’m only on chapter 3, but in my simplistic Object Oriented view of the world, we’re effectively saying that Integer implements the interfaces Enum, Eq, Integral, Num, Org, Read, Real and Show (but the truth is a little more involved).

Prelude> :info Enum
class Enum a where
  succ :: a -> a
  pred :: a -> a
  toEnum :: Int -> a
  fromEnum :: a -> Int
  enumFrom :: a -> [a]
  enumFromThen :: a -> a -> [a]
  enumFromTo :: a -> a -> [a]
  enumFromThenTo :: a -> a -> a -> [a]
        -- Defined in GHC.Enum
instance Enum Integer -- Defined in GHC.Num
instance Enum Float -- Defined in GHC.Float
instance Enum Double -- Defined in GHC.Float
instance Enum Bool -- Defined in GHC.Enum
instance Enum Ordering -- Defined in GHC.Enum
instance Enum Char -- Defined in GHC.Enum
instance Enum () -- Defined in GHC.Enum
instance Enum Int -- Defined in GHC.Enum

You kind of have to be comfortable with looking at types of the form:

a -> a -> a -> [a]

“enumFromThenTo” obviously takes three values and returns a list of values. (The joy of types, right? You know what it does by what its type is.) Moreover, we can see that it’s defined for the instances Integer, Float, Double, Bool, Ordering, Char, () and Int.

Prelude> enumFromThenTo 1 2 8
[1,2,3,4,5,6,7,8]
Prelude> enumFromThenTo () () ()
[(),(),(),(),(),()^CInterrupted.

and we can type functions too:

Prelude> :type fst
fst :: (a, b) -> a

What does that one do? There's only one thing it can do! Yes, I know, that's practically pornographic.

The exercise
"Write a function lastButOne, that returns the element before the last."

Trivial, right? A five year old could do it. Well, excuse me while I have a quick flashback to ML ticks (PDF) and rock gently back and forth in the corner. You have to bear in mind that, at this point in the book, we don't know there's a 'length' function in Prelude, we've not been taught pattern matching or case statements, and we're still simplistically minded imperative programmers. So naïvely, the best we might be able to do is:

-- in add.hs
count n [] = n
count n xs = count (n+1) (drop 1 xs)

myLastButOne xs = head (drop ((count 0 xs) - 2) xs)

Prelude> :load add.hs
[1 of 1] Compiling Main             ( add.hs, interpreted )
Ok, modules loaded: Main.
*Main> myLastButOne [1,2..10]
9

Repeat after me… “ewww”. And even to do that, I’ve had to use mysterious pattern matching which hasn’t been explained at that point in the book. Now, we could assume that a resourceful reader might find the ‘length’ function:

myLastButOne xs = head (drop ((length xs) - 2) xs)

But that’s still pretty unsatisfactory. For all I know, length is O(n) in the length of the list, so I’ll be going down the list twice. I daren’t imagine what Don would say. Even if it’s O(1), it doesn’t feel right. After a bit of head scratching and syntax guessing, I came to:

lastButOne (h:t) = case t of
                       (a:[]) -> h
                       (a:b) -> lastButOne t

which, for me at least, feels a little better. But I don’t know it’s right. I’m welcoming any pointers here. Now obviously for the “Find the last but nth item”, going down the list twice is looking less unattractive:

myLastButN n xs = head (drop ((length xs) - (n+1)) xs)

It’s still not great though. Would that I could list[-n]. But that’s not the point.

Summary
I’m determined to learn more Haskell and continue to expose my ignorance on this blog. Any pointers to good docs are welcome – “Haskell for simpletons”, that sort of thing. Meantimes I’ll continue to read the book. My stretch goal is to understand the things written on Don’s blog and on the following:

Conal Elliott:
http://conal.net/blog/

Kenn Knowles:
http://www.kennknowles.com/blog/

Removing bytes from a file

posted by codders in c, code

Morning,

I copied and pasted a (Ruby) script from a PDF this morning, and on executing it I got a whole pile of:

webservice.rb:33: Invalid char `\240' in expression
webservice.rb:33: Invalid char `\302' in expression

which was annoying. For reasons best known to KPDF (or oowriter, or my window manager’s cut-and-paste buffer), the spaces in the script (” “) had been encoded as 0xc2 0xa0, which is sort of UTF16 if you look at it sideways, but essentially useless to me.

So how do you remove 200 instances of a 2-byte sequence from a file? I didn’t have a good way, but this bad way sufficed:

cat > rm.c << EOF
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

int main(int arcg, char *argv[])
{
  unsigned char c;
  
  while (read(0, &c, 1)==1)
  {
    if (c != 0xc2 && c != 0xa0)
    {
      write(1, &c, 1);
    }
    else if (c == 0xc2)
    {
      write(1, " ", 1);
    }
  }
}
EOF
make rm
cat webservice.rb | ./rm > output.rb

So, my dearest lazyweb… better answers?

Awesome D-Bus

posted by codders in code, python

I’ve been using a new window manager – Awesome WM. It’s pretty fine. At version 2.3, it doesn’t currently support window tabbing in the way Ion does, but I’m assured that that feature is on its way. Everything else works pretty swishly, and the desktop tagging features are particularly nice.

It doesn’t come with a system tray out of the box, so I’d managed to miss some incoming instant messages. Fortunately you can write your own widgets for Awesome – you just pipe your widget updates into ‘awesome-client’.

So all I needed was a way to get the new message notification out of Pidgin…

#!/usr/bin/env python

from BeautifulSoup import BeautifulSoup
import os
import dbus.glib
import gobject
import sys

class CheckedObject:
    def __init__(self, obj):
        self.obj = obj

    def __getattr__(self, attr):
        return CheckedAttribute(self, attr)

class CheckedAttribute:
    def __init__(self, cobj, attr):
        self.cobj = cobj
        self.attr = attr

    def __call__(self, *args):
        result = self.cobj.obj.__getattr__(self.attr)(*args)
        if result == 0:
            raise "Error: " + self.attr + " " + 
               str(args) + " returned " + 
               str(result)
        return result

def awesome_write(string):
    awesome = os.popen("awesome-client", "w")
    widget_message = "0 widget_tell widgetbar im text %s\n" % string
    awesome.write(widget_message)
    awesome.close()

def message_received(account, sender, message, conversation, flags):
    html = BeautifulSoup(message)
    try:
      message = html.font.font.string
    except Exception, e:
      pass
    awesome_write("%s <%s>" % (message, sender))

def message_sent(account, receiver, message):
    awesome_write("")

bus = dbus.SessionBus()

obj = None
try:
    obj = bus.get_object(
        "im.pidgin.purple.PurpleService",
        "/im/pidgin/purple/PurpleObject")
except:
    print "Couldn't find Pidgin on the Bus"
    sys.exit(1)

purple = dbus.Interface(obj, "im.pidgin.purple.PurpleInterface")

cpurple = CheckedObject(purple)

bus.add_signal_receiver(message_received, dbus_interface="im.pidgin.purple.PurpleInterface", signal_name="ReceivedImMsg")
bus.add_signal_receiver(message_sent, dbus_interface="im.pidgin.purple.PurpleInterface", signal_name="SentImMsg")

gobject.MainLoop().run()

D-Bus really seems to be coming along quite nicely. dbus-inspector shows that there are a bunch of applications enabled for it (including Pidgin and XChat), and the language support seems to be fairly polished. Can’t wait to see what else ends up on the bus.

Ars run-through (with code):
http://arstechnica.com/reviews/apps/pidgin-2-0.ars/4

Pidgin list of conversation signals:
http://developer.pidgin.im/doxygen/dev/html/conversation-signals.html#sent-im-msg

D-Bus Inspector:
http://www.vitavonni.de/projekte/dbus-inspector.html.en

Awesome WM:
http://awesome.naquadah.org/

Ion WM:
http://modeemi.fi/~tuomov/ion/

Normalising MP3s

posted by codders in debian

I’m changing the way I blog, and possibly starting to do it again. But I digress…

The OpenRightsGroup blog linked a recording of an interesting talk with Jonathan Zittrain (whose new book is getting some press and whose e-book PDF is available for free download), but the recording was a bit quiet and I wanted to listen to it while cooking my lunch…

# sudo apt-get install mp3gain
# mp3gain /tmp/org.mp3

/tmp/org.mp3
Recommended “Track” dB change: 25.760000
Recommended “Track” mp3 gain change: 17
WARNING: some clipping may occur with this gain change!
Max PCM sample at current gain: 21450.428803
Max mp3 global gain field: 190
Min mp3 global gain field: 129

Recommended “Album” dB change for all files: 25.760000
Recommended “Album” mp3 gain change for all files: 17
WARNING: with this global gain change, some clipping may occur in file /tmp/org.mp3

# mp3gain -g 17 /tmp/org.mp3
Applying gain change of 17 to /tmp/org.mp3…

done

…which was nice.

Talk:
http://www.openrightsgroup.org/2008/06/06/the-future-of-the-internet-in-focus/

Book:
http://futureoftheinternet.org/

Recent Posts
Recent Comments
About Us
jp: works like a charm! thanks!...
Blake: Check this out: http://bugs.adobe.com/jira/browse/SDK-28016...
Boydell: Wow. That was it. You are the only one that had it figured out, and I looked at many...
mark van schaik: thanks! was using a beta SDK version for a production app, which stopped working over...
Sebastian: Steve, I find most asynchronous programming to be incredibly painful. Haskell's appro...

This is the personal blog of a professional software engineer. This site and the views expressed on it are in no way endorsed by the RIAA.