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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
