therning.org/ magnus

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

Close Bookmark and Share This Page

Save to Browser Favorites / Bookmarks

Ask backflip blinklist BlogBookmark Bloglines BlogMarks Blogsvine BuddyMarks BUMPzee! CiteULike co.mments Connotea del.icio.us

Digg diigo DotNetKicks DropJack dzone Facebook Fark Faves Feed Me Links Friendsite folkd.com Furl Google

Hugg Jamespot Jeqq Kaboodle kirtsy linkaGoGo LinkedIn LinksMarker Ma.gnolia Mister Wong Mixx MySpace MyWeb

Netvouz Newsvine oneview OnlyWire PlugIM Propeller Reddit Rojo Segnalo Shoutwire Simpy Slashdot Sphere

Sphinn Spurl Squidoo StumbleUpon Technorati ThisNext Twitter Webride Windows Live Worlds Movies Yahoo!

Email This to a Friend

Copy HTML: 

 If you like this then please subscribe to the RSS Feed.

Powered by Bookmarkify™

More »