When I set out to do this in Haskell I discovered that there wasn’t anything available that would let me get the address information for my network interfaces. So, I set out build network-info and learned how to use the Foreign Function Interface (FFI) in the process.

Getting the IPv4, IPv6 and MAC addresses of your local network interfaces is now just a “cabal install” away:

cabal install network-info

Once you’ve got the library installed it’s simple to get your network details:

import Network.Info
 
main = do
    ns <- getNetworkInterfaces
    mapM_ (putStr . showInterface) ns
 
showInterface n = name n ++ "\n"
               ++ "  IPv4: " ++ show (ipv4 n) ++ "\n"
               ++ "  IPv6: " ++ show (ipv6 n) ++ "\n"
               ++ "  MAC:  " ++ show (mac n) ++ "\n"

Running this on my Ubuntu box yields something similar to this:

$ runghc getaddr.hs
lo
  IPv4: 127.0.0.1
  IPv6: 0:0:0:0:0:0:0:1
  MAC:  00:00:00:00:00:00
eth0
  IPv4: 10.0.2.5
  IPv6: fe80:0:0:0:f00:15ff:fcf9:c677
  MAC:  08:00:72:5f:6c:19

And on Windows 7:

> runghc getaddr.hs
Local Area Connection
  IPv4: 192.168.0.107
  IPv6: fe80:0:0:0:ef54:7861:7df:6b7c
  MAC:  00:26:c9:e1:87:8c
VirtualBox Host-Only Network
  IPv4: 192.168.56.1
  IPv6: fe80:0:0:0:14b4:b3af:557:ad4a
  MAC:  08:00:27:00:d8:2a
Loopback Pseudo-Interface 1
  IPv4: 127.0.0.1
  IPv6: 0:0:0:0:0:0:0:1
  MAC:  00:00:00:00:00:00
... snipped out some garbage network interfaces

You’ll notice that the IPv6 addresses don’t have fully collapsed groups of zeros just yet, but they are still valid addresses.

I’ve tested this on Ubuntu 10.04, Windows XP & Windows 7. It won’t install on Mac OS X or BSD just yet because of restrictions in the cabal file. I need to check out how getifaddrs works on those systems so I know what to do in the FFI code.

The solution was to install the x86 vim from vim.org, then take the gvimext.dll from the 64-bit vim, and apply the following registry tweaks.

Windows Registry Editor Version 5.00

[HKEY_LOCAL_MACHINE\SOFTWARE\Vim\Gvim]
"path"="C:\\Program Files (x86)\\Vim\\vim72\\gvim.exe"

[HKEY_CLASSES_ROOT\CLSID\{51EEE242-AD87-11d3-9C1E-0090278BBD99}]
@="Vim Shell Extension"

[HKEY_CLASSES_ROOT\CLSID\{51EEE242-AD87-11d3-9C1E-0090278BBD99}\InProcServer32]
@="C:\\Program Files (x86)\\Vim\\vim72\\gvimext64.dll"
"ThreadingModel"="Apartment"

To save anyone else the hassle of getting the bits you need from the 64-bit vim, I’ve zipped up everything you need (gvimext64.zip). Just extract it to C:\Program Files (x86)\Vim\vim72 and run the gvimext64.reg file.

Not to be outdone, I though I’d delve in to GeSHi’s regular expression features to see if I could improve upon the default. I struggled a bit with things getting highlighted that had already been processed and matched to an alternate regular expression until I dug in to the GeSHi source to and found out how it escapes potential highlights. This led to some lovely regex like the one below as I attempted to work around things like <PIPE>, <SEMI> and other magical GeSHi escapes like <|!REG3XP1!>.

/<[A-Z]+>|<\|!REG3XP\d*!>.*?\|>/

One I figured this out things got a lot easier and I was able to get to a point that I’m pretty happy with. The symbol highlighting is still a bit hacky and I’d like to get to a point where all non-alphanumeric character groups are highlighted as symbols. For now though I’ve just added a few more (<$>, <|>, etc) to the hardcoded list that comes with GeSHi out of the box. So without any further ado, here are the results.

Before

module Main where
 
import Control.Monad.Identity
import Text.Parsec (ParseError,parse,char,oneOf,(<?>),(<|>))
import Text.Parsec.ByteString
import Text.Parsec.Expr
import qualified Data.ByteString.Char8 as S
 
data Expr = Op Char Expr Expr
          | Value Char
          deriving Show
 
-- This is a comment
main :: IO ()
main = do
  xs <- S.getContents
  let f = S.unlines . translate . (drop 1) . S.lines
  S.putStr $ f xs
  return ()
 
{- This is a multiline
    comment -}
translate :: [S.ByteString] -> [S.ByteString]
translate = map $ f . readExpr
  where f (Left err) = S.pack $ show err
        f (Right val) = showRPN val
 
showRPN :: Expr -> S.ByteString
showRPN (Value v)  = S.singleton v
showRPN (Op o a b) = showRPN a `S.append` showRPN b `S.append` S.singleton o
 
table :: [[Operator S.ByteString st Identity Expr]]
table = [[op '^', op '/', op '*', op '-', op '+']]
  where op c = Infix (liftM Op $ char c) AssocLeft
 
term :: Parser Expr
term = brackets <|> value <?> "term"
 
brackets :: Parser Expr
brackets = char '(' >> expr >>= \x -> char ')' >> return x

After

module Main where
 
import Control.Monad.Identity
import Text.Parsec (ParseError,parse,char,oneOf,(<?>),(<|>))
import Text.Parsec.ByteString
import Text.Parsec.Expr
import qualified Data.ByteString.Char8 as S
 
data Expr = Op Char Expr Expr
          | Value Char
          deriving Show
 
-- This is a comment
main :: IO ()
main = do
  xs <- S.getContents
  let f = S.unlines . translate . (drop 1) . S.lines
  S.putStr $ f xs
  return ()
 
{- This is a multiline
    comment -}
translate :: [S.ByteString] -> [S.ByteString]
translate = map $ f . readExpr
  where f (Left err) = S.pack $ show err
        f (Right val) = showRPN val
 
showRPN :: Expr -> S.ByteString
showRPN (Value v)  = S.singleton v
showRPN (Op o a b) = showRPN a `S.append` showRPN b `S.append` S.singleton o
 
table :: [[Operator S.ByteString st Identity Expr]]
table = [[op '^', op '/', op '*', op '-', op '+']]
  where op c = Infix (liftM Op $ char c) AssocLeft
 
term :: Parser Expr
term = brackets <|> value <?> "term"
 
brackets :: Parser Expr
brackets = char '(' >> expr >>= \x -> char ')' >> return x

You can download my modifications to the Haskell syntax file for GeSHi here. If I get some more time I’ll probably submit it back to the GeSHi project as a replacement or an alternative for Haskell.

One thing to note is that I’ve stripped out the url linking of Prelude functions. I felt that it wasn’t really that useful as I rarely want to know the details of those functions, it’s all the other ones that I want to know about! I toyed with the idea of linking functions and types to Hoogle or Hayoo!, that might be worthwhile in the future.

Download haskell.php

The syntax file above was built and tested on GeSHi 1.0.8.7, it will probably work on other versions, but you never know :)

My first attempt took me a few hours to come up with. It’s been a little while since I’ve played with Haskell so a lot of time was spent fighting with the type checker. Eventually though I produced a solution that solved the problem. It works by exploding each building in to a set of discrete points, where a building (1,11,3) becomes the coordinates [(1,11),(2,11),(3,11)]. The points are then sorted and various filters are run across the data until we get the answer.

import Data.List
 
main =
  putStrLn $
  unwords $ 
  concatMap (map show . list . head) $
  groupBy' snd $
  map last $
  groupBy' fst $
  sort $
  concatMap explode buildings
 
list (x,y) = [x,y]
groupBy' f = groupBy (\x y -> f x == f y)
explode (l,h,r) = [(x,h) | x <- [l..r-1]] ++ [(r,0)]
 
buildings = [(1,11,5),(2,6,7),(3,13,9),(12,7,16),
             (14,3,25),(19,18,22),(23,13,29),(24,4,28)]

This seemed like it wasn’t the most efficient way to do things and I wasn’t reading my data from an input file yet. So, after a bit more thinking (and some cheating) I got some ideas on how to implement the program coming from a different angle. At some point I also wanted to try a golf solution (using as few characters as possible) so I stuck to using only the Prelude.

The revised solution works by scanning each building for every x-coordinate (1 – 9999) and calculating the height at that coordinate. The output is built by showing the current coordinates every time the maximum height changes. The thing I like about the revised solution is that it is basically just restating the problem in Haskell. I’ve included the type signatures below for completeness, but as always, they’re not required.

main :: IO ()
main = interact $ showSkyline . skyline . readBuildings
 
readBuildings :: String -> [[Int]]
readBuildings = map (map read . words) . lines
 
skyline :: [[Int]] -> [(Int,Int)]
skyline buildings = [(x, height x) | x <- [1..9999], isDiff x]
  where isDiff  x = height x /= height (x - 1)
        height    = maximum . heights
        heights x = 0 : [h | [s,h,e] <- buildings, s <= x, x < e]
 
showSkyline :: [(Int,Int)] -> String
showSkyline = unwords . (map showPoint)
 
showPoint :: (Int,Int) -> String
showPoint (x, y) = show x ++ " " ++ show y

Finally, I reduced the above solution to as few characters as possible so I could write an answer for the Stack Overflow code golf question.

It turned out to be 149 characters, which I was pretty happy with. I could have shaved off four more by inlining ‘b’, but that made the program take a lot longer to execute when using runghc for some reason. I’m not sure if it would have made a difference if I compiled it.

main=interact f
f i=unwords[show x++" "++show(h x)|x<-[1..9999],h x/=h(x-1)] where
 h x=maximum$0:[y|[l,y,r]<-b,l<=x,x<r]
 b=map(map read.words)$lines i

If you discount reading the input or writing the output in a particular format, then it can be trimmed down to 75 characters. The input, stored in ‘b’, is the ‘buildings’ list from the first solution.

h x=maximum$0:[y|(l,y,r)<-b,l<=x,x<r]
print[(x,h x)|x<-[1..9999],h x/=h(x-1)]

I love the idea of having a massive workspace and being able to see relevant functions side by side. It was also really cool how you can email workspaces around with annotations.

Happstack/Helpers/DirBrowse.hs:88:105:
    Couldn't match expected type `String' against inferred type `Bool'
    In the third argument of `hscolour', namely `False'
    In the second argument of `(.)', namely
        `(hscolour defaultColourPrefs False False f)'
    In the first argument of `($)', namely
        `BrowseHtmlString . (hscolour defaultColourPrefs False False f)'
cabal: Error: some packages failed to install:
happs-tutorial-0.9.0 depends on happstack-helpers-0.30 which failed to
install.
happstack-helpers-0.30 failed during the building phase. The exception was:
exit: ExitFailure 1

It turns out that happstack-helpers is listed as dependening on hscolour >= 1.0 && < 2.0 when in reality it fails to compile against v1.15 of hscolour. I was thinking, damn, I'm going to have to manually download the sources for happstack-helpers, edit the cabal file so it has the right references and compile it manually. That's horribly convoluted for something that must happen all the time, there must be a better way!

I've been sitting on #haskell recently so I asked the question, and got some very speedy responses:

cabal install happs-tutorial --constraint="hscolor == 1.14"

That did the trick, and with a lot less effort!

I’ve asked quite a few questions on #haskell in the last few days and the response has been almost immediate every time and I’ve had my problem solved within minutes. Granted I’m still a Haskell newbie so my questions are probably trivial, but even still, it puts to shame the support I’ve received from a lot of commercial companies.

Configuring hsp-0.4.5...
Preprocessing library hsp-0.4.5...
Building hsp-0.4.5...
ghc: could not execute: trhsx
cabal: Error: some packages failed to install:
happstack-0.3.2 depends on hsp-0.4.5 which failed to install.
hsp-0.4.5 failed during the building phase. The exception was:
exit: ExitFailure 1

After some digging I found out that I was supposed to have ~/.cabal/bin in my path, who would have thought? Anyway, I added the following to my .bashrc:

PATH=$PATH:~/.cabal/bin

…and happstack installed without a hitch.

Win!

Lets see how I go getting the dependencies by hand…

ReSharper has some useful attributes that can be used to mitigate this somewhat. NotNullAttribute and CanBeNullAttribute give the ReSharper engine some hints that it can use to warn developers about potential mistakes, but at the end of the day you still end up with a boilerplate mess of if statements:

Apple apple = PickApple();
 
if (apple == null)
{
    return null;
}
 
Orange orange = PickOrange();
 
if (orange == null)
{
    return null;
}
 
FruitSalad fruitSalad = MakeFruitSalad(apple, orange);
 
if (fruitSalad == null)
{
    return null;
}
 
return PackageForSale(fruitSalad);

Or perhaps even worse, the lovely arrow-head pattern. Reaching for the far edge of the screen with every possible null:

Apple apple = PickApple();
 
if (apple != null)
{
    Orange orange = PickOrange();
 
    if (orange != null)
    {
        FruitSalad fruitSalad = MakeFruitSalad(apple, orange);
 
        if (fruitSalad != null)
        {
            return PackageForSale(fruitSalad);
        }
    }
}

A solution to this problem that I’ve been using recently is straight out of the Haskell playbook, the Maybe monad. This simple tool wraps up the concept of uncertainty so that it is composable. This allows you to rewrite the above code like this using LINQ:

return from apple in PickApple()
       from orange in PickOrange()
       from fruitSalad in MakeFruitSalad(apple, orange)
       select PackageForSale(fruitSalad);

Sweet! So it’s just like an IEnumerable<T> that is either empty, or contains a single value. So how does it work? Lets look at the type signature for PickApple:

Maybe<Apple> PickApple()

Instead of returning an Apple directly, we return Maybe<Apple> (I like to pronounce this “maybe an apple”). This gives us two advantages. Firstly, it captures in the type system that we might not return a value. Secondly, it allows us to define a raft of common functions for working with Maybe<T> values.

So what does Maybe<T> look like? Here are the basics:

public struct Maybe<T>
{
    private readonly bool m_HasValue;
    private readonly T m_Value;
 
    public Maybe(T value)
    {
        m_Value = value;
        m_HasValue = value != null;
    }
 
    public T Value
    {
        get
        {
            return m_Value;
        }
    }
 
    public bool HasValue
    {
        get
        {
            return m_HasValue;
        }
    }
 
    public bool HasNothing
    {
        get
        {
            return !m_HasValue;
        }
    }
 
    public static implicit operator Maybe<T>(T value)
    {
        return new Maybe<T>(value);
    }
 
    public static Maybe<T> Nothing
    {
        get
        {
            return default(Maybe<T>);
        }
    }
}

It’s important to note that Maybe<T> is a struct. If it was a class then Maybe could be null, nothing or contain a value. So you’d need to check for three possible cases and we wouldn’t have gained much at all!

So far this is looking pretty similar to Nullable<T> from the BCL. Unfortunately we can’t use Nullable<T> because it constrains T to structs only. This does bother me too much, I think Maybe<T> is a better name anyway.

So how do we do the funky LINQ stuff? We have to define what’s called the bind operator in functional languages. It describes how we can chain one maybe on to the next, and what to do if we encounter a maybe which has nothing in it. Unfortunately, because LINQ was designed to have a familiar SQL feel to it, this bind operation needs to be an extension method called SelectMany. This enables C# and Visual Basic to make use of it with the LINQ syntax.

So this is what “bind” looks like for our Maybe monad:

public static Maybe<B> SelectMany<A, B>(this Maybe<A> maybeA, Func<A, Maybe<B>> aToMaybeB)
{
    if (maybeA.HasNothing)
    {
        return Maybe<B>.Nothing;
    }
 
    return aToMaybeB(maybeA.Value);
}

It’s nothing special, it takes maybe an A and a function which goes from an A to maybe a B. The important thing here is that if A doesn’t have a value then the function aToMaybeB isn’t called. We’re still missing a small piece of the puzzle, but we’re able to write our original function as this:

return PickApple().SelectMany(apple =>
       PickOrange().SelectMany(orange =>
       MakeFruitSalad(apple, orange).SelectMany(fruitSalad =>
       PackageForSale(fruitSalad))));

The query syntax does work yet because LINQ requires one extra overload of SelectMany. This overload will describe how to chain two maybes together to yield a third. It’s purely an optimisation, so we’re not going to bother taking advantage of it in this case. We’ll just implement it in terms of our singular SelectMany:

public static Maybe<C> SelectMany<A, B, C>(this Maybe<A> maybeA, Func<A, Maybe<B>> aToMaybeB, Func<A, B, Maybe<C>> abToMaybeC)
{
    return maybeA.SelectMany(a => aToMaybeB(a).SelectMany(b => abToMaybeC(a, b)));
}

Ouch! That’s one scary looking method! You don’t need to worry too much about this guy. Unless you’re planning to do optimisations it’s exactly the same for every single monad. Having said that, you should see similarities between it and our usage of SelectMany in the previous example.

Once we have our “double bind” operation defined, the linq syntax should work as described earlier:

return from apple in PickApple()
       from orange in PickOrange()
       from fruitSalad in MakeFruitSalad(apple, orange)
       select PackageForSale(fruitSalad);

Now that you have the basics you can add all sorts of extra functions for dealing with Maybe<T>. If I’m feeling keen I might post a follow up article on the additional functions that I’ve found useful. OrNull is a handy one for “unboxing” a Maybe<T> back to a naked value and OrThrow is another useful one which gets the inner value but throws if the Maybe<T> contains nothing.

So now you can say goodbye to if (a != null) right? Well, not quite, naked values always have the possibility of being null. It’s just an uncertainty that we’re going to have to deal with for the time being. However, if you always use Maybe<T> when a method might return “nothing” then you can fairly safely avoid checking for null when you’re working with values returned from your own code.

Hopefully we’ll be able to lock down naked values completely when we get code contracts in .NET 4.0. I’d love to see something which automatically annotates all arguments and return values with a contract ensuring that they can never be null.

A world without null, luxury!

The Jystic Theme uses a dark blue background and different colours for classes, interfaces, structs, delegates and enums. In addition to C# highlighting, it also supports xaml, aspx and css.

C#

XAML

ASPX

CSS

Download Jystic Theme

The font I like to use is DejaVu Sans Mono.

Download DejaVu Sans Mono