Lists defined as Maybe in Haskell? Why not?

Question

You don't offen see Maybe List except for error-handling for example, because lists are a bit Maybe themselves: they have their own "Nothing": [] and their own "Just": (:). I wrote a list type using Maybe and functions to convert standard and to "experimental" lists. toStd . toExp == id.

data List a = List a (Maybe (List a))
    deriving (Eq, Show, Read)

toExp [] = Nothing
toExp (x:xs) = Just (List x (toExp xs))

toStd Nothing = []
toStd (Just (List x xs)) = x : (toStd xs)

What do you think about it, as an attempt to reduce repetition, to generalize?

Trees too could be defined using these lists:

type Tree a = List (Tree a, Tree a)

I haven't tested this last piece of code, though.

Answer 1

All ADTs are isomorphic (almost--see end) to some combination of (,),Either,(),(->),Void and Mu where

data Void --using empty data decls or
newtype Void = Void Void

and Mu computes the fixpoint of a functor

newtype Mu f = Mu (f (Mu f))

so for example

data [a] = [] | (a:[a])

is the same as

data [a] = Mu (ListF a)
data ListF a f = End | Pair a f

which itself is isomorphic to

newtype ListF a f = ListF (Either () (a,f))

since

data Maybe a = Nothing | Just a

is isomorphic to

newtype Maybe a = Maybe (Either () a)

you have

newtype ListF a f = ListF (Maybe (a,f))

which can be inlined in the mu to

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

and your definition

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

is just the unfolding of the Mu and elimination of the outer Maybe (corresponding to non-empty lists)

and you are done...

a couple of things

1. Using custom ADTs increases clarity and type safety

2. This universality is useful: see GHC.Generic

---

Okay, I said almost isomorphic. It is not exactly, namely

hmm = List (Just undefined)

has no equivalent value in the [a] = [] | (a:[a]) definition of lists. This is because Haskell data types are coinductive, and has been a point of criticism of the lazy evaluation model. You can get around these problems by only using strict sums and products (and call by value functions), and adding a special "Lazy" data constructor

data SPair a b = SPair !a !b
data SEither a b = SLeft !a | SRight !b
data Lazy a = Lazy a --Note, this has no obvious encoding in Pure CBV languages,
--although Laza a = (() -> a) is semantically correct, 
--it is strictly less efficient than Haskell's CB-Need 

and then all the isomorphisms can be faithfully encoded.

Answer 2

You can define lists in a bunch of ways in Haskell. For example, as functions:

{-# LANGUAGE RankNTypes #-}

newtype List a = List { runList :: forall b. (a -> b -> b) -> b -> b }

nil :: List a
nil = List (\_ z -> z )

cons :: a -> List a -> List a
cons x xs = List (\f z -> f x (runList xs f z))

isNil :: List a -> Bool
isNil xs = runList xs (\x xs -> False) True

head :: List a -> a
head xs = runList xs (\x xs -> x) (error "empty list")

tail :: List a -> List a
tail xs | isNil xs = error "empty list"
tail xs = fst (runList xs go (nil, nil))
    where go x (xs, xs') = (xs', cons x xs)

foldr :: (a -> b -> b) -> b -> List a -> b
foldr f z xs = runList xs f z

The trick to this implementation is that lists are being represented as functions that execute a fold over the elements of the list:

fromNative :: [a] -> List a
fromNative xs = List (\f z -> foldr f z xs)

toNative :: List a -> [a]
toNative xs = runList xs (:) []

In any case, what really matters is the contract (or laws) that the type and its operations follow, and the performance of implementation. Basically, any implementation that fulfills the contract will give you correct programs, and faster implementations will give you faster programs.

What is the contract of lists? Well, I'm not going to express it in complete detail, but lists obey statements like these:

1. head (x:xs) == x
2. tail (x:xs) == xs
3. [] == []
4. [] /= x:xs
5. If xs == ys and x == y, then x:xs == y:ys
6. foldr f z [] == z
7. foldr f z (x:xs) == f x (foldr f z xs)

EDIT: And to tie this to augustss' answer:

newtype ExpList a = ExpList (Maybe (a, ExpList a))

toExpList :: List a -> ExpList a
toExpList xs = runList xs (\x xs -> ExpList (Just (x, xs))) (ExpList Nothing)

foldExpList f z (ExpList Nothing) = z
foldExpList f z (ExpList (Just (head, taill))) = f head (foldExpList f z tail)

fromExpList :: ExpList a -> List a
fromExpList xs = List (\f z -> foldExpList f z xs)

Answer 3

You could define lists in terms of Maybe, but not that way do. Your List type cannot be empty. Or did you intend Maybe (List a) to be the replacement of [a]. This seems bad since it doesn't distinguish the list and maybe types.

This would work

newtype List a = List (Maybe (a, List a))

This has some problems. First using this would be more verbose than usual lists, and second, the domain is not isomorphic to lists since we got a pair in there (which can be undefined; adding an extra level in the domain).

Answer 4

If it's a list, it should be an instance of Functor, right?

instance Functor List
  where fmap f (List a as) = List (f a) (mapMaybeList f as)

mapMaybeList :: (a -> b) -> Maybe (List a) -> Maybe (List b)
mapMaybeList f as = fmap (fmap f) as

Here's a problem: you can make List an instance of Functor, but your Maybe List is not: even if Maybe was not already an instance of Functor in its own right, you can't directly make a construction like Maybe . List into an instance of anything (you'd need a wrapper type).

Similarly for other typeclasses.

---

Having said that, with your formulation you can do this, which you can't do with standard Haskell lists:

instance Comonad List
  where extract (List a _) = a
        duplicate x @ (List _ y) = List x (duplicate y)

A Maybe List still wouldn't be comonadic though.

Answer 5

When I first started using Haskell, I too tried to represent things in existing types as much as I could on the grounds that it's good to avoid redundancy. My current understanding (moving target!) tends to involve more the idea of a multidimensional web of trade-offs. I won't be giving any “answer” here so much as pasting examples and asking “do you see what I mean?” I hope it helps anyway.

Let's have a look at a bit of Darcs code:

data UseCache = YesUseCache | NoUseCache
    deriving ( Eq )

data DryRun = YesDryRun | NoDryRun
    deriving ( Eq )

data Compression = NoCompression
                 | GzipCompression
    deriving ( Eq )

Did you notice that these three types could all have been Bool's? Why do you think the Darcs hackers decided that they should introduce this sort of redundancy in their code? As another example, here is a piece of code we changed a few years back:

type Slot = Maybe Bool                  -- OLD code
data Slot = InFirst | InMiddle | InLast -- newer code

Why do you think we decided that the second code was an improvement over the first?

Finally, here is a bit of code from some of my day job stuff. It uses the newtype syntax that augustss mentioned,

newtype Role = Role { fromRole :: Text }
  deriving (Eq, Ord)

newtype KmClass = KmClass { fromKmClass :: Text }
  deriving (Eq, Ord)

newtype Lemma = Lemma { fromLemma :: Text }
  deriving (Eq, Ord)

Here you'll notice that I've done the curious thing of taking a perfectly good Text type and then wrapping it up into three different things. The three things don't have any new features compared to plain old Text. They're just there to be different. To be honest, I'm not entirely sure if it was a good idea for me to do this. I provisionally think it was because I manipulate lots of different bits and pieces of text for lots of reasons, but time will tell.

Can you see what I'm trying to get at?