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.

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: