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

[Brian Hulley]

ajb at spamcop.net wrote:
> G'day all.
>
> Quoting Brian Hulley <brianh at metamilk.com>:
>
>> The problem is that some people will be using Data.Edison.Seq at the
>> moment and will naturally not want it to change. However I'd suggest
>> that all the common operations be factored out into separate classes
>> eg:
>
> While I think the huge typeclass is unfortunate, one of Edison's
> greatest strengths is that every sequence supports every sequence
> operation.  (The catch, of course, is that the operation may be
> inefficient.)
>
> This was a deliberate design decision, and I'd be sorry to see it go.
> Many is the time in C++ when I started, say, with a std::stack, then
> discovered soon after that I needed to peer at the top few elements
> on the stack, only to find that std::stack doesn't support that.

As an aside, if I was needing any kind of sequence in C++ I'd use a 
std::vector because it supplies all the ops you need (and is usually fast 
enough for exploratory programming). I've never seen any point in stack or 
deque etc because they're far too limited.

>
> Supporting all operations supports exploratory/agile programming.  You
> don't have to decide up front what operations you need to be fast.
> You can discover this as you go.
>
> Yes, this is orthogonal to breaking up the huge typeclass, but I
> thought I'd just mention it.

As you've pointed out, there are 2 separate issues that are in danger of 
being confused:
1) Forcing all sequence instances to support all operations
2) Bundling all the ops into a single huge class

I'd suggest that while 1) may be useful for the classes that are there at 
present, there are many ops that they don't yet support and also some ops 
that are never needed. Also, surely as long as there is one concrete type 
that supports everything that should be good enough for exploratory 
programming (I'm thinking of FingerTrees which seem to be able to do 
absolutely anything in logarithmic time!!! :-) )

For 2), you could still have a Sequence class to gather all the separate 
functionality together but I'd make it inherit from all the separate pieces 
of functionality rather than being the place where all the functionality is 
defined eg:

     class Viewable c a | c -> a where
         viewL :: Monad m => c -> m (a, c)
         viewR :: Monad m => c -> m (c, a)
         atL :: c -> a  -- must be called on non-empty sequence
         atR :: c -> a

     class Indexable c a | c -> a where
         length :: c -> Int
         at :: Int -> c -> a -- index must be in range
         splitAt :: Int -> c -> (c, c)

     -- in same module as Indexable
     take :: Indexable c a => Int -> c -> c
     take i c = let (l, _) = splitAt i c in l

     class (Monoid c, Foldable c a, Indexable c a, Filterable c a, Viewable 
c a) => Sequence c a

This way, we'd get the advantages of being able to write (Sequence c a) as 
well as the advantages of being able to supply a sequence to a function that 
needed a Foldable - at the moment the fold methods of sequence are invisible 
to the rest of Haskell because they're trapped inside the Sequence class.

Regards, Brian.

-- 
Logic empowers us and Love gives us purpose.
Yet still phantoms restless for eras long past,
congealed in the present in unthought forms,
strive mightily unseen to destroy us.

http://www.metamilk.com