Re: FP-style map over set
- From: RobertSzefler <NOSPAMrszeflerNOSPAM@xxxxxxxxxxxxxx>
- Date: Mon, 28 Nov 2005 14:53:33 +0100
Lauri Alanko wrote:
In article <dmelce$12ce$1@xxxxxxxxxxxxxxxxxx>, RobertSzefler <NOSPAMrszeflerNOSPAM@xxxxxxxxxxxxxx> wrote:
How do you elegantly define functional map over sets?
"Set" is not a data structure, it is an abstract datatype. If you want advice on how to implement an algorithm, you have to specify the data structure that you want the algorithm to operate on. Or are you also asking for advice on how to implement the set ADT?
Well, "list" also is an ADT and Haskell (and other FPL's) have these cute formalisms with deconstruction (matching) and reconstruction I provided. I was looking for something equally elegant from the theoretical point of view as well as actually implementable. Ie. a set of primitives for set manipulation (such as head/tail decomposition in Haskell) that is both elegant, theoretically sound and possible to implement and use without scaring people with monads ;)
My aim is a definition similar to map for lists, which might be expressed as (I think the syntax here is haskellish if not strictly haskell)
which is (arguably) expressing map in simpler terms.
This, as it happens, is also a valid implementation of the map for sets, when you represent sets as lists that may contain duplicates. It is not the most efficient representation, but it fulfills the specification.
It is invalid as it depends on internal representation, and, more importantly, it's unsound as it allows to order (linearize) a set which is algebraically evil (see the grim shadow of SQL's data model?).
If you are not happy with this implementation, then please specify the additional requirements that you have.
Listed above. I'm not about implementation; implementing a set ADT is a trivial matter.
- Prev by Date: Re: FP-style map over set
- Next by Date: Re: FP-style map over set
- Previous by thread: Re: FP-style map over set
- Next by thread: Re: FP-style map over set