On Jul 30, 2006, at 5:28 PM, Brian Hulley wrote:
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.
So, what you want is a sequence of sequences that can be
transparently converted to a "flattened" sequence and vice versa? And
you also want to keep track of the total number of lines and
characters within each line. Additionally, you want to keep track of
the maximum number of characters in any one line.
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.
Edison has support for transparently keeping track of the size of a
sequence.
http://www.eecs.tufts.edu/~rdocki01/docs/edison/Data-Edison-Seq-
SizedSeq.html
It may well be possible to create a slightly generalized wrapper that
keeps track of arbitrary "measures". (If they can be computed by a
function which is associative, commutative and has a unit).
Humm, sort of an incremental fold.... I like it.
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").
OK. Point taken. I'm not sure I agree with the no-exceptions camel-
case, but the lexicographical-listing-groups-functionality holds
strong appeal for me.
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 :-)
Well, I guess I'd suggest you attempt to identify specific problems
with already existing packages and attempt to work with those who
maintain such packages before reinventing something as basic (and
difficult to get right!) as data structure abstractions.
Such maintainers may be willing to accept patches and/or implement
requested features in order to reduce fragmentation in this space
*hint, hint* :-)
<soapbox type="Edison plug">
I personally think that Edison is a great piece of work, and I took
up maintainership because I felt it was a great shame that no one was
using it. My ultimate goal is to make Edison the package that
everyone thinks of first when they discover they need a Haskell
datastructure for some purpose. Even if Edison does not fill that
need, I want every Haskeller to compare his needs against what Edison
provides before striking out on his own, and I want that to be a
decision made with some hesitation. Over time I hope to make the
cases where Edison doesn't cut the mustard fewer and further between.
So, if you've ever looked at Edison, or ever do so in the future, and
decide it isn't what you need, please let me know why so I can make
it better for the next time. After all, squeaky wheels get the
grease, but only if I can hear the squeaking!
</soapbox>
Rob Dockins
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
-- TMBG
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
