DData in hierarchical libraries

[Robert Will]

On Thu, 26 Feb 2004, JP Bernardy wrote:
>
> 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'
> signiatures)
>
> 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.

Yes, the way you go looses some important laws of functional programming,
e.g.

prop_elements_are_member coll = all ('member'coll) coll

where 'all' is defined via 'fold' as in the Prelude.

A simple fix would be to change the type of 'member' and provide an
additional function 'has_key' (or 'key_member') on Maps.  Note also that
the most general way is to view Maps as Collections of pairs, since than
users can fold/filter/apply on the domain and range by composing their
functions with 'fst' and 'snd'.


Robert