[Haskell-cafe] The difficulty of designing a sequence class

David Menendez zednenem at psualum.com
Mon Jul 31 18:35:04 EDT 2006

ajb at spamcop.net writes:

> G'day all.
> Quoting Robert Dockins <robdockins at fastmail.fm>:
> > I've considered reformulating the Sequence class to be more similar
> > to the Collection classes (which use MPTCs, fundeps and mention the
> > element type),
> The redesign of the Collection hierarchy was from my tree.  The main
> reason why I changed it was that ternary tries couldn't really be
> typed properly.  (Chris' implementation of Patricia trees used a
> phantom key type along with a stern warning to only define the Int
> instance.  That didn't work for ternary tries, since the key type is
> polymorphic.)
> I didn't get around to fixing Sequence because there wasn't a need for
> it yet, but yes, it should be done.

That's a tough call to make. Changing the kind of Sequence to * from *
-> * means losing the Functor, Monad, and MonadPlus superclasses and all
the various maps and zips.

I guess you could separate those into an auxiliary class,

    class (Functor s, MonadPlus s) => SeqFunctor s where
        mapWithIndex :: (Int -> a -> b) -> s a -> s b
        zip :: s a -> s b -> s (a,b)

and require that any instance of SeqFunctor also be an instance of

A pity we can't do something like,

    class (Functor s, MonadPlus s, forall a. Sequence (s a) a) =>
            SeqFunctor s where

David Menendez <zednenem at psualum.com> | "In this house, we obey the laws
<http://www.eyrie.org/~zednenem>      |        of thermodynamics!"

More information about the Haskell-Cafe mailing list