[Haskell-cafe] The difficulty of designing a sequence class
brianh at metamilk.com
Mon Jul 31 20:43:23 EDT 2006
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
> 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
> 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
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
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.
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.
More information about the Haskell-Cafe