Re: FP-style map over set

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)

map([],f)=[]
map([h|t],f)=[f(h)|map(t,f)]

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.
.

Relevant Pages

  • Re: FP-style map over set
    ... "Set" is not a data structure, ... asking for advice on how to implement the set ADT? ... > definition similar to map for lists, which might be expressed as (I ... If you are not happy with this implementation, then please specify the ...
    (comp.lang.functional)
  • Re: translating imperative pseudocode to functional
    ... > i have the following pseudocode algorithm for finding the largest ... be translated into a purely functional pseudocode? ... > (perhaps not even using a data structure at all?) ... eliminateNeighbors n'' ...
    (comp.lang.functional)
  • two interesting data structure/algorithm questions
    ... My friend asked me two questions about data structure and algorithms. ... cell phone shows all names start with letters "ab" in sorted order. ... what's the best data structure and algorithm to implement ... for an arbitrary string and return the page numbers where this string ...
    (comp.programming)
  • Re: Surrogate factoring explained
    ... >> he has not specified the algorithm he actually uses these days (else it ... Sorry, it doesn't work that way: either specify a specific algorithm, or ... Obviously, I can't report factoring precentages for "a concept", I can only ... exits at once, without computing more gcds. ...
    (sci.crypt)
  • Re: two interesting data structure/algorithm questions
    ... My friend asked me two questions about data structure and algorithms. ... cell phone shows all names start with letters "ab" in sorted order. ... what's the best data structure and algorithm to implement ... for an arbitrary string and return the page numbers where this string ...
    (comp.programming)