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)