[Haskell-cafe] empty Array?

[Abraham Egnor]

As a project mostly motivated by personal curiosity, I've been
implementing a Sequence class:

class Sequence s where
    front :: s a -> (a, s a)
    back :: s a -> (s a, a)
    null :: s a -> Bool

    empty :: s a
    prepend :: a -> s a -> s a
    append :: s a -> a -> s a
    concat :: s a -> s a -> s a

The intent is to make it almost as easy to use, via pattern guards, as
pattern matching on lists:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x:map f xs

smap :: Sequence s => (a -> b) -> s a -> s b
smap f s | null s = empty
         | (a, s') <- front s = prepend (f a) $ smap f s'

It is, of course, trivial to implement this for lists.  I've run into
a snag, however, when trying to implement this for Arrays (as in
Data.Array) - I can't seem to find a way to represent an empty array,
which makes implementing 'empty' and 'null' impossible.  Suggestions?

Abe