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

[Brian Hulley]

Robert Dockins wrote:
> On Sunday 30 July 2006 07:47, Brian Hulley wrote:
>> Another option, is the Edison library which uses:
>>
>>      class (Functor s, MonadPlus s) => Sequence s where
>>
>> so here MonadPlus is used instead of Monoid to provide empty and
>> append. So I've got three main questions:
>
>> 1) Did Edison choose MonadPlus just because this fitted in with the
>> lack of multi-parameter typeclasses in H98?
> Edison's design hails from a time when MPTCs were not only
> non-standard (as they still are), but also not widely used, and
> before fundeps were avaliable (I think).  So the answer to this one
> is pretty much "yes".
[snip]

Hi - Thanks for the answers to this and my other questions. One thing I just 
realised is that there doesn't seem to be any instance declarations anywhere 
in the standard libs relating Monoid to MonadPlus so it's a bit unsettling 
to have to make a "random" choice on the question of what kind of object a 
Sequence is...

I tried:

    class (forall a. Monoid s a) => Sequence s where ...

but of course that doesn't work, so I suppose MonadPlus is the only option 
when 'a' doesn't appear as a type variable arg of the class being defined.

> BTW, for what purpose are you desiging a new sequence class?  You are
> clearly aware of other efforts in this area; in what ways to they not
> meet your needs?

The existing sequence and collection classes I've looked at don't do enough.

For example, when I tried to represent the text in an edit widget, I 
realised I needed a sequence of characters that could also be considered to 
be a sequence of lines, and it is necessary to be able to index the sequence 
by character position as well as by line position, as well as keeping track 
of the total number of characters, the total number of lines, and the 
maximum number of characters on any one line (so as to be able to calculate 
the x,y extents when laying out the widget, assuming a fixed width font 
(tabs ignored!)), with very efficient split and append operations.

I managed to get a good representation by using a FingerTree of lines where 
each line uses a ByteString.
I made my own FingerTree class based on the one referenced in the paper at 
http://www.soi.city.ac.uk/~ross/papers/FingerTree.html but without the 
symbolic names which I find totally unreadable and confusing, and also so I 
could get full control of the strictness of the implementation, and also as 
a way of understanding them since I'd never come across such a complicated 
data structure before. (I highly recommend this paper to anyone who wants to 
learn about FingerTrees, Monoids and other very useful concepts.)

So one thing existing sequence classes don't have (apart from FingerTree) is 
the concept of measurement which is essential when you want efficient 
updates. Eg in my text buffer, the measurement maintained for a sequence is 
the number of chars and number of lines and maximum line length.

Then I needed a structure for a Trie widget a bit like (details omitted):

      data Node = Expanded Value T | Collapsed Value T | Leaf Value
      newtype T = T (FingerTree (Key, Node))

where objects of type T could be regarded as a finite map (eg from 
hierarchical module names to modules) as well as a flattened linear sequence 
indexed by line number (for display on the screen in a widget given the 
current scroll bar position), and which also needed to keep track of the 
total horizontal and vertical extent of the Trie as it would appear in the 
widget's font.

There are several different kinds of measurement going on in this data 
structure, as well as the complexity of the extra recursion through the leaf 
to a new level. Existing sequence abstractions don't seem to provide the 
operations needed to treat a nested data structure as a single sequence.

In summary:

1) Often a complex data structure must be able to be simultaneously regarded 
as a single flattened sequence
2) Measurements are needed for efficient updates (may need to keep track of 
several at once)
3) Indexing and size are sometimes needed relative to the flattened sequence 
not just the top level
4) It is useful to have a finite map that can also be regarded as a linear 
sequence
5) Such finite maps may also be nested (when the keys are hierarchical) but 
this nesting should be hidden from the user...
6) I want a design that can allow complex data structures to be built up 
easily and instanced to the appropriate interfaces
7) Also naming conventions in the existing libs are a bit irregular and 
burdened with old fashioned lisp-isms eg in Data.Edison.Seq there are 
functions "lview" and "reducel" but I'd argue that there must be one and 
only one way of forming any identifier in any program namely that the 
function should appear first followed by qualifiers (so that related 
functionality always appears together in a lexicographical listing of 
functions) and it must use camel case with no exceptions at all, thus 
"viewL" and "reduceL" (and "foldL").
8) More factoring needs to be done since not all sequences need to be 
indexed or measured or to be "flattened through the leaf" (eg the FingerTree 
paper already has a separate class for Reduce and I believe their 
implementation also referred to a class for Foldable) rather than bundling 
everything in a single Sequence class.

Anyway apologies for my very rambling answer - I'm still a long way from 
finding a good set of classes to address the above issues :-)

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