Haskell community, As many of you are aware, Edison is a venerable library of data structures written in Haskell, primarily by Chris Okasaki. I have though for some time that it is a great shame that Edison has been languishing in disuse. It has always seemed to me to be high quality code which is fairly well designed. I believe that the barriers to its adoption have largely been barriers of ease-of-use and project management, and not necessarily problems with the design or implementation of the code itself. Although I am not a data structures expert, several weeks ago I decided that I would try my hand at maintaining Edison and see if I could overcome these barriers. Toward this end I have taken the most recent Edison codebase I could find (from Andrew Bromage's HFL project) and updated it in the following ways: -- Put source code under darcs version control -- Moved modules into a module hierarchy rooted at "Data.Edison" -- Moved to a cabal build system -- Integrated documentation into the source code using Haddock -- Tied together the various unit testing code into a comprehensive test suite -- Altered the API to bring it more closely in line with current practice (as exemplified by the Data.Set and Data.Map standard libraries) -- Added Data.Set and Data.Map as Edison "implementations" I now feel that it is ready for release, and have consequently prepared what I am calling "Edison 1.2, release candidate 1". Before I officially dub Edison 1.2, I would like to request some feedback from the community. In particular, I would very much like to hear people's opinions about the API: naming conventions, argument orders, etc. I have already made a number of changes to the Edison 1.1 API, and if people feel other changes are warranted, I'd like to go ahead and make them all at once. Particular points about which I would like to get feedback are: -- The Sequence 'rcons' method takes its arguments in the opposite order as the 'lcons' method (for mnemonic purposes). Should the arguments to 'rcons' be reversed? -- There are a few places where 'Data.Map' and/or 'Data.Set' have methods named similarly (but not identical) to the Edison API. By and large I have left those differences. Should I instead modify Edison to match those names? -- Are there additional methods that should be added to the API? -- Are there methods that should be removed? And perhaps most important, -- looking at this version of Edison, are there any things that would make you hesitant to use it? You can find Edison 1.2rc1 at the following places: Project homepage: http://www.eecs.tufts.edu/~rdocki01/edison.html API docs: http://www.eecs.tufts.edu/~rdocki01/docs/edison/index.html Darcs repository: http://www.eecs.tufts.edu/~rdocki01/edison/ Source tarball: http://www.eecs.tufts.edu/~rdocki01/projects/edison-1.2rc1-source.tar.gz Many thanks, Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG
Sorry for replying to myself....
Haskell community,
As many of you are aware, Edison is a venerable library of data structures written in Haskell, primarily by Chris Okasaki. I have though for some time that it is a great shame that Edison has been languishing in disuse. It has always seemed to me to be high quality code which is fairly well designed. I believe that the barriers to its adoption have largely been barriers of ease-of-use and project management, and not necessarily problems with the design or implementation of the code itself.
Although I am not a data structures expert, several weeks ago I decided that I would try my hand at maintaining Edison and see if I could overcome these barriers. Toward this end I have taken the most recent Edison codebase I could find (from Andrew Bromage's HFL project) and updated it in the following ways:
-- Put source code under darcs version control -- Moved modules into a module hierarchy rooted at "Data.Edison" -- Moved to a cabal build system -- Integrated documentation into the source code using Haddock -- Tied together the various unit testing code into a comprehensive test suite -- Altered the API to bring it more closely in line with current practice (as exemplified by the Data.Set and Data.Map standard libraries) -- Added Data.Set and Data.Map as Edison "implementations"
I now feel that it is ready for release, and have consequently prepared what I am calling "Edison 1.2, release candidate 1". Before I officially dub Edison 1.2, I would like to request some feedback from the community. In particular, I would very much like to hear people's opinions about the API: naming conventions, argument orders, etc. I have already made a number of changes to the Edison 1.1 API, and if people feel other changes are warranted, I'd like to go ahead and make them all at once.
Particular points about which I would like to get feedback are:
-- The Sequence 'rcons' method takes its arguments in the opposite order as the 'lcons' method (for mnemonic purposes). Should the arguments to 'rcons' be reversed? -- There are a few places where 'Data.Map' and/or 'Data.Set' have methods named similarly (but not identical) to the Edison API. By and large I have left those differences. Should I instead modify Edison to match those names? -- Are there additional methods that should be added to the API? -- Are there methods that should be removed?
One additional point I just remembered: There are a number of methods which take a monad context and call 'fail' (rather than error) under some conditions, usually when the data structure is empty, e.g. lview :: Monad m => s a -> m (a, s a) Separate a sequence into its first (leftmost) element and the remaining sequence. Calls fail if the sequence is empty. I am considering moving to a MonadPlus context and calling 'mzero' in the failure case. For the Maybe and List monads, the results are the same. In general I like using MonadPlus better, but mplus doesn't take a string message like fail does. Thoughts?
And perhaps most important,
-- looking at this version of Edison, are there any things that would make you hesitant to use it?
You can find Edison 1.2rc1 at the following places:
Project homepage: http://www.eecs.tufts.edu/~rdocki01/edison.html
API docs: http://www.eecs.tufts.edu/~rdocki01/docs/edison/index.html
Darcs repository: http://www.eecs.tufts.edu/~rdocki01/edison/
Source tarball: http://www.eecs.tufts.edu/~rdocki01/projects/edison-1.2rc1- source.tar.gz
Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG
G'day again. Quoting Robert Dockins <robdockins@fastmail.fm>:
There are a number of methods which take a monad context and call 'fail' (rather than error) under some conditions, usually when the data structure is empty
[...]
I am considering moving to a MonadPlus context and calling 'mzero' in the failure case.
The problem with MonadPlus is that you don't actually need the Plus functionality. It is usually considered good design to only require what you need, and Monad already has "fail". There has been some discussion on haskell-prime about resurrecting the MonadZero class, for monads with mzero but not mappend. This would be the closest fit, but then, you might want to consider that some people would appreciate having the string diagnostic. Cheers, Andrew Bromage
On Mon, Feb 20, 2006 at 05:29:16PM -0500, ajb@spamcop.net wrote:
The problem with MonadPlus is that you don't actually need the Plus functionality. It is usually considered good design to only require what you need, and Monad already has "fail".
There has been some discussion on haskell-prime about resurrecting the MonadZero class, for monads with mzero but not mappend. This would be the closest fit, but then, you might want to consider that some people would appreciate having the string diagnostic.
I think the problem is that 'mzero' exists, the correct solution seems to be to get rid of the 'mzero' method of MonadPlus. Since haskell is lazy, all Monads have at least the zero of _|_ which can be overriden by 'fail' with a more suitable one. MonadPlus should be about extending monads with an additive operator, there is no need for another concept of zero and it seems to me that is the real issue. mzero can simply be defined as 'fail "mzero"'. John -- John Meacham - ⑆repetae.net⑆john⑈
Hello, On 2/20/06, John Meacham <john@repetae.net> wrote:
I think the problem is that 'mzero' exists, the correct solution seems to be to get rid of the 'mzero' method of MonadPlus. Since haskell is lazy, all Monads have at least the zero of _|_ which can be overriden by 'fail' with a more suitable one. MonadPlus should be about extending monads with an additive operator, there is no need for another concept of zero and it seems to me that is the real issue. mzero can simply be defined as 'fail "mzero"'.
In what sense is _|_ a 'zero'? -iavor
On Mon, Feb 20, 2006 at 05:10:02PM -0800, Iavor Diatchki wrote:
On 2/20/06, John Meacham <john@repetae.net> wrote:
I think the problem is that 'mzero' exists, the correct solution seems to be to get rid of the 'mzero' method of MonadPlus. Since haskell is lazy, all Monads have at least the zero of _|_ which can be overriden by 'fail' with a more suitable one. MonadPlus should be about extending monads with an additive operator, there is no need for another concept of zero and it seems to me that is the real issue. mzero can simply be defined as 'fail "mzero"'.
In what sense is _|_ a 'zero'?
Ah, Sorry, I meant to say that every monad in haskell has a natural 'failure' and by the zero-as-failure model has a natural mzero too. However that does weaken my argument if there are examples of monads where having failure and zero be distinct is a useful thing. Consider my argument weakened appropriatly. In any case, treating a map lookup as a 'failure' rather than a 'zero' does make more sense to me independent of this and the need for error messages. Actually, sort of on this note, I would like to see 'mempty' separated out of the Monoid class... If we had class aliases ideally it would be something like: class MEmpty a where mempty :: a class MAppend a where mappend :: a -> a -> a class alias Monoid a = (MEmpty a,MAppend a) where mconcat = foldr mappend mempty not that I am seriously suggesting class aliases for haskell'. First a few well tested implementations need to appear which I doubt will happen before haskell' is well on its way. John -- John Meacham - ⑆repetae.net⑆john⑈
On 20/02/06, Iavor Diatchki <iavor.diatchki@gmail.com> wrote:
Hello,
On 2/20/06, John Meacham <john@repetae.net> wrote:
I think the problem is that 'mzero' exists, the correct solution seems to be to get rid of the 'mzero' method of MonadPlus. Since haskell is lazy, all Monads have at least the zero of _|_ which can be overriden by 'fail' with a more suitable one. MonadPlus should be about extending monads with an additive operator, there is no need for another concept of zero and it seems to me that is the real issue. mzero can simply be defined as 'fail "mzero"'.
In what sense is _|_ a 'zero'?
-iavor
This ties in with an important point which I've been pushing lately, that bottom should not be used for expected failure. Expected failure should be explicit, and appropriate monads (not monads in general!) make this convenient. I am rather strongly of the opinion that fail should not be a method of the monad class, since it is so common that the only implementation one can give, even in perfectly reasonable monads, is 'error'. Bottom is acceptably used in sanity checks where if it occurs, the programmer must be at fault. However, due to the inconvenience of catching _|_ in IO, I really find that in the vast majority of cases, explicitly representing failure (the Maybe and Either String monads being common candidates) is much nicer when errors are to be expected and handled internally to the application. One thing which I found odd about the NotJustMaybe pattern is that not much is really gained apart from a small amount of convenience. Of course, you get to pass back that string which is sometimes an advantage over Maybe but Either String gives you that as well. It's rather easy to embed Either String, or Maybe into any suitable larger monad which would otherwise apply, and you get more information about what type of errors can be passed back. (Maybe of course just represents partiality, while the use of Either String explicitly tells you that the function is prepared to hand you some form of error string.) Further, if the inconvenience of doing that embedding is still too great, we have the typeclass MonadError to differentiate between monads with and without failure mechanisms -- perhaps it could be cleaned up a bit in a few ways, but I think the idea is right. - Cale
G'day all. Quoting Cale Gibbard <cgibbard@gmail.com>:
One thing which I found odd about the NotJustMaybe pattern is that not much is really gained apart from a small amount of convenience.
That's not the whole truth. It buys you abstraction, in that the library function can signal an error without caring what specific mechanism is used to support it.
Further, if the inconvenience of doing that embedding is still too great, we have the typeclass MonadError to differentiate between monads with and without failure mechanisms -- perhaps it could be cleaned up a bit in a few ways, but I think the idea is right.
That's also possible. MonadError is designed so that errors can be caught. Maybe this is not the most important feature. Cheers, Andrew Bromage
On Mon, Feb 20, 2006 at 04:22:19PM -0500, Robert Dockins wrote:
Sorry for replying to myself.... There are a number of methods which take a monad context and call 'fail' (rather than error) under some conditions, usually when the data structure is empty, e.g.
lview :: Monad m => s a -> m (a, s a) Separate a sequence into its first (leftmost) element and the remaining sequence. Calls fail if the sequence is empty.
I am considering moving to a MonadPlus context and calling 'mzero' in the failure case. For the Maybe and List monads, the results are the same. In general I like using MonadPlus better, but mplus doesn't take a string message like fail does. Thoughts?
I very strongly depend on that string error message. It would be a bad thing to loose it. Monad failure also feels more appropriate to me, there isn't really an 'mplus' you are going to use so making it the mzero just doesn't feel right. John -- John Meacham - ⑆repetae.net⑆john⑈
G'day all. Quoting Robert Dockins <robdockins@fastmail.fm>:
Although I am not a data structures expert, several weeks ago I decided that I would try my hand at maintaining Edison and see if I could overcome these barriers. Toward this end I have taken the most recent Edison codebase I could find (from Andrew Bromage's HFL project) and updated it in the following ways:
Yay! Thanks for doing this. Maybe I can close down HFL now. :-)
-- The Sequence 'rcons' method takes its arguments in the opposite order as the 'lcons' method (for mnemonic purposes). Should the arguments to 'rcons' be reversed?
The argument is that they both take their arguments in the order that they would do were they implemented with concatenation: lcons x xs === [x] ++ xs rcons xs x === xs ++ [x] This certainly makes sense to me. Is there an argument for using the other order?
-- There are a few places where 'Data.Map' and/or 'Data.Set' have methods named similarly (but not identical) to the Edison API. By and large I have left those differences. Should I instead modify Edison to match those names?
If you want to change it, change it to whatever makes the most sense for you. (This, for example, is why I dumped all of the old Edison Maybe-like data structures in favour of a NotJustMaybe-like interface. It made more sense at the time.) Data.Set, Data.Map, Data.Hash and the various Array interfaces are all inconsistent in subtle ways, so whatever you do, do not take them as the ideal to which Edison should aspire. A better idea would be to look at all of them, and decide which convention you think makes the most sense. An even better idea is to lay out the differences and invite feedback on which is best. Cheers, Andrew Bromage
On Feb 20, 2006, at 5:19 PM, ajb@spamcop.net wrote:
G'day all.
Quoting Robert Dockins <robdockins@fastmail.fm>:
Although I am not a data structures expert, several weeks ago I decided that I would try my hand at maintaining Edison and see if I could overcome these barriers. Toward this end I have taken the most recent Edison codebase I could find (from Andrew Bromage's HFL project) and updated it in the following ways:
Yay! Thanks for doing this. Maybe I can close down HFL now. :-)
-- The Sequence 'rcons' method takes its arguments in the opposite order as the 'lcons' method (for mnemonic purposes). Should the arguments to 'rcons' be reversed?
The argument is that they both take their arguments in the order that they would do were they implemented with concatenation:
lcons x xs === [x] ++ xs rcons xs x === xs ++ [x]
This certainly makes sense to me. Is there an argument for using the other order?
Consistency. Almost all the other API functions take the data structure argument last. This seems to be a kind of de facto standard and deviations from it are likely to cause confusion. In Edison 1.1, the collection and associative collection APIs had several functions with the "opposite" order, but I reversed those to match usage of Data.{Set,Map}. Now Sequence is the only class which still contains methods with the data structure in other-than-last position; 'rcons' is one of these, 'inBounds' another, and the 'lookup*' functions are the others. This makes for a total of about 6, in an API consisting of about 200 functions.
-- There are a few places where 'Data.Map' and/or 'Data.Set' have methods named similarly (but not identical) to the Edison API. By and large I have left those differences. Should I instead modify Edison to match those names?
If you want to change it, change it to whatever makes the most sense for you. (This, for example, is why I dumped all of the old Edison Maybe-like data structures in favour of a NotJustMaybe-like interface. It made more sense at the time.)
Data.Set, Data.Map, Data.Hash and the various Array interfaces are all inconsistent in subtle ways, so whatever you do, do not take them as the ideal to which Edison should aspire.
This is all true. The main advantage that the current Data.* APIs have is that people use them ;-)
A better idea would be to look at all of them, and decide which convention you think makes the most sense. An even better idea is to lay out the differences and invite feedback on which is best.
That is a good idea. I will think on this. Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG
Robert Dockins <robdockins@fastmail.fm> wrote:
On Feb 20, 2006, at 5:19 PM, ajb@spamcop.net wrote:
Data.Set, Data.Map, Data.Hash and the various Array interfaces are all inconsistent in subtle ways, so whatever you do, do not take them as the ideal to which Edison should aspire.
This is all true. The main advantage that the current Data.* APIs have is that people use them ;-)
And AFAIK the only reason people use them is because they are widely distributed, not because they are a perfect design. I certainly have reservations about the Data.* APIs, such as the left bias and so on, and personally preferred the older Data.FiniteMap API. Regards, Malcolm
ajb@spamcop.net writes:
G'day all.
Quoting Robert Dockins <robdockins@fastmail.fm>:
-- The Sequence 'rcons' method takes its arguments in the opposite order as the 'lcons' method (for mnemonic purposes). Should the arguments to 'rcons' be reversed?
The argument is that they both take their arguments in the order that they would do were they implemented with concatenation:
lcons x xs === [x] ++ xs rcons xs x === xs ++ [x]
This certainly makes sense to me. Is there an argument for using the other order?
The order of rcons is also natural for using in-line, e.g. "xs `rcons` x". -- David Menendez <zednenem@psualum.com> | "In this house, we obey the laws <http://www.eyrie.org/~zednenem> | of thermodynamics!"
participants (7)
-
ajb＠spamcop.net -
Cale Gibbard -
David Menendez -
Iavor Diatchki -
John Meacham -
Malcolm Wallace -
Robert Dockins