Articles

A doubly-linked list in Haskell

In Uncategorized on March 30, 2010 by Matt Giuca

I wrote it this morning. I wasn’t sure if it could be done.

Since Haskell is a pure language, you can’t mutate things. That makes it tricky to construct cyclic data structures, but you can using Haskell’s laziness. A quick example is the cycle function in the Haskell prelude, defined thusly:

cycle            :: [a] -> [a]
cycle []          = error "Prelude.cycle: empty list"
cycle xs          = xs' where xs'=xs++xs'

Note that you could write “cycle xs = xs ++ cycle xs”, but that isn’t strictly a cyclic list, it’s an infinite list. There is no semantic difference, only a very subtle operational one.

I used the same trick to create a full doubly-linked list (note that you can’t update this data structure, you can just create one from a singly-linked list and explore it as you wish).

data DoubleList a = Cons (DoubleList a) a (DoubleList a)
                  | Nil

instance Show a => Show (DoubleList a) where
show Nil = "Nil"
show (Cons left x right) = "Cons <left> " ++ show x ++ " " ++ show right

fromList :: [a] -> DoubleList a
fromList xs = fromList' Nil xs
    where
        fromList' :: DoubleList a -> [a] -> DoubleList a
        fromList' _ [] = Nil
        fromList' prev (x:xs) = self
            where self = Cons prev x (fromList' self xs)

interactive :: Show a => DoubleList a -> IO ()
interactive Nil = putStrLn "Empty list"
interactive (Cons left x right) = do
    putStr $ show x ++ " (l, r)> "
    prompt <- getLine
    case prompt of
        "l" -> goto left
        "r" -> goto right
        _ -> interactive (Cons left x right)
    where
        goto Nil = do
            putStrLn "End of list"
            interactive (Cons left x right)
        goto target = interactive target

The show function doesn’t show the left side, because that would create an infinite string. But you can use the “interactive” function to explore the list interactively.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: