How to covert the 'Real World Haskell' list data type to using Maybe?

Question

I've been studying 'Real World Haskell' and I'm stuck on working out how to use Maybe. I wrote this data type and corresponding function from Chapter 3. The book suggests trying to convert it to use Maybe and get rid of the Nil type. I've been playing around with this but I can't work out how to do it. I've tried adding maybe in different places, but I'm really just guessing rather than knowing how to do it.

data List a = List a (List a)
            | Nil
            deriving (Show)

toList :: List a -> [a]
toList (List a Nil) = a:[]
toList (List a as)  = a:(toList as)

Answer 1

Look at this:

data List a              data Maybe a
    = List a (List a)        = Just a
    | Nil                    | Nothing

When you write it this way, the parallel looks pretty clear -- we just need to put some extra data in the Just side! To put "extra" data, we can use a tuple. The only other wrinkle is that we must name a constructor.

data List' a = List' (Maybe (a, List' a {- here's the extra bit -}))

Answer 2

data List a = List a (Maybe (List a))

would do it. You'd have List 1 (Just (List 2 Nothing)) to represent [1, 2]. I don't know if it's the most elegant or the easiest to use, though.