DData in hierarchical libraries

JP Bernardy jyp_7 at yahoo.com
Thu Feb 26 06:44:40 EST 2004


I've compiled a haddock documentation for my proposal
"DData in hierarchical libraries". I submit it to
you for review.


The source code is available too.


Daan: I take the liberty to "publish" this without
knowing the exact terms of your license. Given the
audience of this list, I think it will be no problem.


For easier review, a summary of changes follow.
The source distribution also contains a diff.

* Scc module removed 

  More an algorithm than a data structure.
  Sort of (but not quite) redundant with SCC in

* renamed "single" to "singleton"

  more explicit, more usual.

* removed find, favouring (!) and lookup.

  avoids incoherency with Data.List.find

  Map.find :: Map k v -> k -> v

  List.find :: (a -> Bool) -> [a] -> Maybe a

* removed (<>), prefering append

  More explicit. Besides, operators might be a problem
in the
  current scheme of using modules qualified.

* rename "isEmpty" to "null"

  to match List.null

* foldL, foldR, foldI -> foldl, foldr, foldi

  to match Prelude.fold[lr]

* Added instances

* renamed "subset" to "isSubsetOf"

  this matches isPrefixOf, isSuffixOf

* Added documentation / changed it to reflect changes
  incl. hints on how to use the module system.

I think I should explain why I wanted to change the
interface of Maps.

Consider the type of these functions:

Set.fromList :: Ord a => [a] -> Set a
Set.member :: Ord a => a -> Set a -> Bool
Set.fold :: (a -> b -> b) -> b -> Set a -> b
Set.filter :: 
   Ord a => (a -> Bool) -> Set a -> Set a

Map.fromList :: Ord k => [(k, a)] -> Map k a
Map.member :: Ord k => k -> Map k a -> Bool
Map.fold :: (a -> b -> b) -> b -> Map k a -> b
Map.filter :: 
   Ord k => (a -> Bool) -> Map k a -> Map k a

With respect to fold and filter (and most functions),
maps have the shape of collections of values. (The key
type does not appear as such in the functions'

Yet, a few functions break this conventions.
For example, "member" tests the presence of a key,
not a value. 

This is justified by the implementation. I've come
to think it is the way to go (given it is a "concrete"
library). It makes me slightly uneasy that a few
functions stand out, still.

Do you Yahoo!?
Get better spam protection with Yahoo! Mail.

More information about the Libraries mailing list