Wednesday, January 02, 2008

Associative Lists

Normal lists are indexed by position, an associative list is one which is indexed by some other key. Take for example my fruit basket at the moment: I have 7 apples and 3 bananas. In Haskell the obvious way of writing an associative list is:


fruit :: [(String,Int)]
fruit = [("apple",7),
("banana",3)]


I can then ask questions about my fruit basket:


-- How many apples do I have?
> lookup "apple" fruit
Just 7
> lookup "orange" fruit
Nothing

-- How much fruit do I have?
> sum (map snd fruit)
10

-- What fruit do I have most of?
> fst $ maximumBy (comparing snd) fruit
"apple"


Since I am storing associative lists as lists of tuples, to search through the list for a key requires O(n) time. By using the Data.Map module, this can be reduced to O(log n).


import qualified Data.Map as Map
fruitMap :: Map.Map String Int
fruitMap = fromList fruit

> lookup "apple" fruitMap
Just 7


Often when writing a large associative list, it can get a bit tiresome with all the (,) tuples. To alleviate this, I tend to write my associative lists as:


fruit = let (*) = (,) in
["apple" * 7
,"banana" * 3
]


I redefine the (*) operator to be tuple, to remove the extra bracketing. I like the use of * as it has a nice cross-product feel, which goes well with the idea of tuples. I also align the commas at the start of the list, which I think looks more attractive.

Disclaimer: When I started writing this article I had 7 apples, now I only have 6. I also threw away the 3 bananas as they had started to go bad.

3 comments:

Anonymous said...

Plural words don't have apostrophes, please! Bananas, not banana's. Commas, not comma's.

Neil Mitchell said...

Anon: Fixed. I did know that, and did get it right with apples earlier on in the post, but must have had a brain freeze.

Anonymous said...

Heh, I have

infixr 0 ~>
(~>) :: a -> b -> (a, b)
(~>) = (,)

in my xmonad.hs for that. It just looks so much better in associative lists, especially if the key is another tuple.