FP-style map over set
RobertSzefler
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. Now the similar
approach won't work consistently over sets without introducing ugly
things like deconstructing sets into an arbitrary element ("head") and
the rest ("tail") like this (hypothetical syntax):
map({},f)={}
map({e|S},f)={f(e)|map(S,f)}
The problem is taking an arbitrary element of set is not FP-kosher as it
allows ordering of an arbitrary set which is obviously un-nice (and
would almost certainly violate generic referential transparency). How is
this problem solved in practice? I think map if defined as basic would
be powerful enough to implement most if not all set ops, is it the case
in practice that maps over sets are built-in in functional languages?
I am aware that my question is stated a bit ambiguously as I dont quite
imagine what appropriate elementary set operations would be FP-wise. All
comments are welcome.
christop...@gmail.com
your mapping function is injective with respect to the set ordering
function. Otherwise it will not be a true map anymore.
Henning Makholm
> The problem with mapping over a set is that you have to ensure that
> your mapping function is injective with respect to the set ordering
> function. Otherwise it will not be a true map anymore.
It seems that you are reading more into "a set" than people in general
do. There is no intrinsic requirement that the elements of a set have
to be ordered at all. Many _implementations_ of sets require such an
ordering for internal purposes, but it is not a part of the "set"
abstraction.
--
Henning Makholm "It was intended to compile from some approximation to
the M-notation, but the M-notation was never fully defined,
because representing LISP functions by LISP lists became the
dominant programming language when the interpreter later became available."
RobertSzefler
Not at all. Consider a finite set of finite sets of integers. The
construct is perfectly sensible from both mathematical and computational
point of view while there is obviously no natural ordering of sets of
integers. Moreover, there obviously are numerous practical applications
of such a construct, for example sum-of-sums or sum-of-maxima (sum in
the set theoretic sense).
Dinko Tenev
> Scripsit "christop...@gmail.com" <christop...@gmail.com>
>
> > The problem with mapping over a set is that you have to ensure that
> > your mapping function is injective with respect to the set ordering
> > function. Otherwise it will not be a true map anymore.
>
> It seems that you are reading more into "a set" than people in general
> do. There is no intrinsic requirement that the elements of a set have
> to be ordered at all. Many _implementations_ of sets require such an
> ordering for internal purposes, but it is not a part of the "set"
> abstraction.
But equality is, and it's all that it takes to make the point about
injection.
Cheers,
D. Tenev
Henning Makholm
> I am aware that my question is stated a bit ambiguously as I dont
> quite imagine what appropriate elementary set operations would be
> FP-wise. All comments are welcome.
I believe a common way is to consider "set" a monad with extra
primitives for membership testing, cardinality, folding over the set,
etc. Mapping can then be done by standard monad operations. Something
like (excuse my rusty Haskell syntax)
map f set = do x <- set
return (f x)
--
Henning Makholm "Jeg har tydeligt gjort opmærksom på, at man ved at
følge den vej kun bliver gennemsnitligt ca. 48 år gammel,
og at man sætter sin sociale situation ganske overstyr og, så
vidt jeg kan overskue, dør i dybeste ulykkelighed og elendighed."
Henning Makholm
>> > The problem with mapping over a set is that you have to ensure that
>> > your mapping function is injective with respect to the set ordering
>> > function. Otherwise it will not be a true map anymore.
>> It seems that you are reading more into "a set" than people in general
>> do. There is no intrinsic requirement that the elements of a set have
>> to be ordered at all.
> But equality is, and it's all that it takes to make the point about
> injection.
But what is a "true map", then? Wihtout any nonstandard context I
would think it perfectly reasonable to have
map (\x -> x mod 10) {23,44,53} == {3,4}
--
Henning Makholm "Det er du nok fandens ene om at
mene. For det ligger i Australien!"
Dinko Tenev
> christop...@gmail.com wrote:
> > The problem with mapping over a set is that you have to ensure that
> > your mapping function is injective with respect to the set ordering
> > function. Otherwise it will not be a true map anymore.
>
> Not at all. Consider a finite set of finite sets of integers. The
> construct is perfectly sensible from both mathematical and computational
> point of view while there is obviously no natural ordering of sets of
> integers.
But with maps you have a one-to-one correspondence between input and
output structures. That may not be the case for sets if your mapping
function is not injective.
Cheers,
Dinko
RobertSzefler
> Scripsit RobertSzefler <NOSPAMrsze...@murator.com.pl>
>
>>I am aware that my question is stated a bit ambiguously as I dont
>>quite imagine what appropriate elementary set operations would be
>>FP-wise. All comments are welcome.
>
>
> I believe a common way is to consider "set" a monad with extra
> primitives for membership testing, cardinality, folding over the set,
> etc. Mapping can then be done by standard monad operations. Something
> like (excuse my rusty Haskell syntax)
>
> map f set = do x <- set
> return (f x)
>
Yes, of course. Although I was aiming at something more elementary (not
theoretically, as monads are quite elegant and unifying indeed, but from
an implementation's point of view). I guess it can't be done, can it?
Lutz Donnerhacke
> I believe a common way is to consider "set" a monad with extra
> primitives for membership testing, cardinality, folding over the set,
> etc. Mapping can then be done by standard monad operations. Something
> like (excuse my rusty Haskell syntax)
>
> map f set = do x <- set
> return (f x)
So you can simplify it to:
map f set = set >>= (return . f)
= fmap f set
= liftM f set
RobertSzefler
> Scripsit "Dinko Tenev" <dinko...@gmail.com>
>
>>Henning Makholm wrote:
>>
>>>Scripsit "christop...@gmail.com" <christop...@gmail.com>
>
>
>>>>The problem with mapping over a set is that you have to ensure that
>>>>your mapping function is injective with respect to the set ordering
>>>>function. Otherwise it will not be a true map anymore.
>
>
>>>It seems that you are reading more into "a set" than people in general
>>>do. There is no intrinsic requirement that the elements of a set have
>>>to be ordered at all.
>
>
>>But equality is, and it's all that it takes to make the point about
>>injection.
>
>
> But what is a "true map", then? Wihtout any nonstandard context I
> would think it perfectly reasonable to have
>
> map (\x -> x mod 10) {23,44,53} == {3,4}
Exactly. That is *the* map in a standard sense, obviously.
RobertSzefler
That's certainly not the case with a standard map. Consider
map(\x->0)[1,2,3]=[0,0,0]
map(\x->0)[4,5,6]=[0,0,0]
Henning Makholm
> But with maps you have a one-to-one correspondence between input and
> output structures.
Says who?
--
Henning Makholm "My fate? Servitude to the Embodiment of Whoops."
Dinko Tenev
[...]
> But what is a "true map", then? Wihtout any nonstandard context I
> would think it perfectly reasonable to have
>
> map (\x -> x mod 10) {23,44,53} == {3,4}
I give you that it is quite reasonable to have computations of this
kind, but they are easily implemented through "deconstructing,"
mapping, and rebuilding the set, and this is the most straightforward
way of defining the computation (in abstract terms) that I can think
of.
How would you propose to define what map means for sets, otherwise?
Cheers,
Dinko
Dinko Tenev
> Scripsit "Dinko Tenev" <dinko...@gmail.com>
>
> > But with maps you have a one-to-one correspondence between input and
> > output structures.
>
> Says who?
Just an observation :) I'd be rather curious to see a practical
counter-example.
Cheers,
Dinko
RobertSzefler
> Henning Makholm wrote:
> [...]
>
>>But what is a "true map", then? Wihtout any nonstandard context I
>>would think it perfectly reasonable to have
>>
>> map (\x -> x mod 10) {23,44,53} == {3,4}
>
>
> I give you that it is quite reasonable to have computations of this
> kind, but they are easily implemented through "deconstructing,"
> mapping, and rebuilding the set, and this is the most straightforward
> way of defining the computation (in abstract terms) that I can think
> of.
My original post was about exactly this problem. IMHO it's hard to give
a theoretically sound deconstruction for sets that allows building a
map-over-set on it. Mapping and rebuilding themselves are not the
problem. The deconstruction is.
Dinko Tenev
> Henning Makholm wrote:
> > But what is a "true map", then? Wihtout any nonstandard context I
> > would think it perfectly reasonable to have
> >
> > map (\x -> x mod 10) {23,44,53} == {3,4}
>
> Exactly. That is *the* map in a standard sense, obviously.
And what exactly is the "standard" sense?
Cheers,
DInko
RobertSzefler
Oouch, a little confusion precipitated. The "standard" sense of map is
the FP sense, the Haskell sense. The extension to sets should work like
this (using informal mathematical notation):
map(f,set)={f(x) for x in set}
Lauri Alanko
RobertSzefler <NOSPAMrsze...@murator.com.pl> 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?
> 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.
If you are not happy with this implementation, then please specify the
additional requirements that you have.
Lauri
RobertSzefler
> In article <dmelce$12ce$1...@news2.ipartners.pl>,
> RobertSzefler <NOSPAMrsze...@murator.com.pl> 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.
Dinko Tenev
> Dinko Tenev wrote:
> > But with maps you have a one-to-one correspondence between input and
> > output structures. That may not be the case for sets if your mapping
> > function is not injective.
>
> That's certainly not the case with a standard map. Consider
>
> map(\x->0)[1,2,3]=[0,0,0]
> map(\x->0)[4,5,6]=[0,0,0]
1 corresponds to the first 0, 2 to the second, etc, and likewise with
the second case. A list like [0, 0, 0] does make sense, and is very
different from [0, 0] or [0], while a set like {0, 0, 0} either doesn't
make any sense at all, or is just the same as {0}.
Cheers,
Dinko
RobertSzefler
Well, map(\x->0){1,2,3} should eval to {0}, obviously.
Dinko Tenev
> Oouch, a little confusion precipitated. The "standard" sense of map is
> the FP sense, the Haskell sense. The extension to sets should work like
> this (using informal mathematical notation):
>
> map(f,set)={f(x) for x in set}
OK, but you're implicitly enumerating f(x) over set, then combining the
values into the result -- otherwise you are saying that things like {0,
1, 0} are sets.
To get rid of the implicit enumeration/composition thing, you would
have to define map(f,set) = {y | (exists x in set | f(x) = y)}, and
that doesn't look like a map in the usual sense.
Cheers,
Dinko
Lauri Alanko
RobertSzefler <NOSPAMrsze...@murator.com.pl> wrote:
> Lauri Alanko wrote:
> > "Set" is not a data structure, it is an abstract datatype.
> Well, "list" also is an ADT
Granted, in the vacuous sense of fulfilling the following interface:
class List l where
nil :: l a
cons :: a -> l a -> l a
match :: forall r. l a -> r -> (a -> l a -> r) -> r
and the algebraic properties:
match nil kn kc = kn
match (cons h t) kn kc = kc h t
cons h t = cons h' t' --> h = h' /\ t = t'
cons h t != nil
and maybe some others.
(Note that we are here talking about _abstract_ datatypes, but ADT is
also, somewhat misleadingly, used as a general name for concrete
sum-of-products datatypes.)
However, usually when we talk about abstract datatypes, we mean
algebraic specifications that are a bit more complex than those
provided by the primitive data structures of the language.
> 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 ;)
All right, so you are looking for an interface for sets that allows
implementing map on top of them, while still not exposing any
implementation details?
> >>map([],f)=[]
> >>map([h|t],f)=[f(h)|map(t,f)]
> >
> > 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
No, the interface would not expose distinctions between sets that had
the same elements but in different order. But my idea was that this
operation would be a part of the implementation of the ADT, but I now
see that you want it to be _outside_ the implementation.
What you could perhaps do is provide a fold operation:
class Set s where
empty :: s a
single :: a -> s a
union :: s a -> s a -> s a
member :: a -> s a -> Bool
fold :: s a -> b -> (a -> b) -> (b -> b -> b) -> b
and various algebraic properties, most relevantly:
fold empty e s u = e
fold (single a) e s u = s a
fold (union s s') e s u = u (fold s e s u) (fold s' e s u)
Now fold must have the added constraint to the interface that when it
is called with "fold set e s u", then u must be idempotent,
commutative and associative. If these conditions are fulfilled, then
the implementation of fold can do an ordinary tree fold in some
definite order, but the result still cannot expose the ordering.
Now you can implement map as:
map f s = fold s empty (single . f) union
However, the constraints on the u parameter cannot be expressed in the
type systems of most practical languages (you need dependent types),
so you may have to rely on an informal interface specification (i.e.
human-readable documentation), which is of course amenable to abuse.
Lauri
Dinko Tenev
> Well, map(\x->0){1,2,3} should eval to {0}, obviously.
Given your intent, it is obvious, but you're losing the structure of
the original set -- there is no one-to-one correspondence between {1,
2, 3} and {0}. This is not the case with eg lists: map (\x -> 0) [1,
2, 3] = [0, 0, 0], the structure is preserved.
Cheers,
Dinko
Dinko Tenev
> > I give you that it is quite reasonable to have computations of this
> > kind, but they are easily implemented through "deconstructing,"
> > mapping, and rebuilding the set, and this is the most straightforward
> > way of defining the computation (in abstract terms) that I can think
> > of.
>
> My original post was about exactly this problem. IMHO it's hard to give
> a theoretically sound deconstruction for sets that allows building a
> map-over-set on it. Mapping and rebuilding themselves are not the
> problem. The deconstruction is.
I don't get this. For deconstruction, what's wrong with taking just
any bijection i: S <-> {1, 2, 3, ..., |S|}, for a finite set S?
Cheers,
Dinko
RobertSzefler
> RobertSzefler wrote:
>
>>Oouch, a little confusion precipitated. The "standard" sense of map is
>>the FP sense, the Haskell sense. The extension to sets should work like
>>this (using informal mathematical notation):
>>
>>map(f,set)={f(x) for x in set}
>
>
> OK, but you're implicitly enumerating f(x) over set, then combining the
> values into the result -- otherwise you are saying that things like {0,
> 1, 0} are sets.
That definition was for clarification. I agree it's inelegant precisely
because it uses implicit iteration, though iteration in the mathematical
sense does not neccesarily mean it is possible to linearize anything in
the system.
> To get rid of the implicit enumeration/composition thing, you would
> have to define map(f,set) = {y | (exists x in set | f(x) = y)}, and
> that doesn't look like a map in the usual sense.
That's a good definition and a correct one. Not very practical, though :(
RobertSzefler
Now I don't get you ;)
By list deconstruction I mean mapping it (in the mathematical sense of
map) onto a finite system (such as a pair) plus binding (in the FP
sense). An example is the typical head-tail decomposition. I'm not
strong about the terminology, though.
RobertSzefler
All that matters is type correctness. We have (currently)
map: x->y->[x]->[y]
I'd like to have ({x} is for a set of x)
map: x->y->{x}->{x}
defined elegantly without introducing {arbitrary-element|the-rest} and,
if possible, without resorting to monads.
I don't really understand your complaints about loosing the structure.
Extensionally the structure (types) is preserved in a strict and natural
way.
RobertSzefler
> In article <dmf24v$1a8p$1...@news2.ipartners.pl>,
> RobertSzefler <NOSPAMrsze...@murator.com.pl> wrote:
>
>>Lauri Alanko wrote:
>>
>>>"Set" is not a data structure, it is an abstract datatype.
>
>>Well, "list" also is an ADT
>
> Granted, in the vacuous sense of fulfilling the following interface:
>
> class List l where
> nil :: l a
> cons :: a -> l a -> l a
> match :: forall r. l a -> r -> (a -> l a -> r) -> r
>
> and the algebraic properties:
>
> match nil kn kc = kn
> match (cons h t) kn kc = kc h t
> cons h t = cons h' t' --> h = h' /\ t = t'
> cons h t != nil
>
> and maybe some others.
Yes. List implementations differ (linked list, vectors, VLists, implicit
sequences...). Match, cons and friends should and do work indifferently
to them.
> (Note that we are here talking about _abstract_ datatypes, but ADT is
> also, somewhat misleadingly, used as a general name for concrete
> sum-of-products datatypes.)
Yes, that's something of a terminology abuse.
> However, usually when we talk about abstract datatypes, we mean
> algebraic specifications that are a bit more complex than those
> provided by the primitive data structures of the language.
Right.
>>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 ;)
>
>
> All right, so you are looking for an interface for sets that allows
> implementing map on top of them, while still not exposing any
> implementation details?
More or less, yes. I'm not so much about the implementation (interface
rings an alarm bell in my head), I'm just thinking about expressing it
elegantly using some valid algebraic notation.
>>>>map([],f)=[]
>>>>map([h|t],f)=[f(h)|map(t,f)]
>>>
>>>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
>
> No, the interface would not expose distinctions between sets that had
> the same elements but in different order. But my idea was that this
OK, tweaking it would probably allow for such encapsulation.
> operation would be a part of the implementation of the ADT, but I now
> see that you want it to be _outside_ the implementation.
Yep.
> What you could perhaps do is provide a fold operation:
Ah! Folds! Didn't think of this straightforward primitive.
> class Set s where
> empty :: s a
> single :: a -> s a
> union :: s a -> s a -> s a
> member :: a -> s a -> Bool
> fold :: s a -> b -> (a -> b) -> (b -> b -> b) -> b
>
> and various algebraic properties, most relevantly:
>
> fold empty e s u = e
> fold (single a) e s u = s a
> fold (union s s') e s u = u (fold s e s u) (fold s' e s u)
Exactly
> Now fold must have the added constraint to the interface that when it
> is called with "fold set e s u", then u must be idempotent,
> commutative and associative. If these conditions are fulfilled, then
> the implementation of fold can do an ordinary tree fold in some
> definite order, but the result still cannot expose the ordering.
>
> Now you can implement map as:
>
> map f s = fold s empty (single . f) union
>
> However, the constraints on the u parameter cannot be expressed in the
> type systems of most practical languages (you need dependent types),
> so you may have to rely on an informal interface specification (i.e.
> human-readable documentation), which is of course amenable to abuse.
Thanks for your input. That's an interesting, though sad conclusion. I
hope something more constructive/well-behaved is possible but fear that
there is some objective obstacle to such a formulation (probably a beast
hiding deep in category theory)...
Dinko Tenev
> Dinko Tenev wrote:
> > any bijection i: S <-> {1, 2, 3, ..., |S|}, for a finite set S?
>
> Now I don't get you ;)
I mean that elements can be ordered in an arbitrary manner, after which
they may be organized as a list. The resulting list will be a value
computed out of the original set. Any reasonable implementation of a
set would give you that, IMHO.
> By list deconstruction I mean mapping it (in the mathematical sense of
> map) onto a finite system (such as a pair) plus binding (in the FP
> sense). An example is the typical head-tail decomposition. I'm not
> strong about the terminology, though.
If you mean deconstruction as for values of an algebraic type, a set
isn't such a value in the first place, so it should come as no surprise
that it can't be decomposed that way :)
Cheers,
Dinko
RobertSzefler
> RobertSzefler wrote:
>
>>Dinko Tenev wrote:
>>
>>>I don't get this. For deconstruction, what's wrong with taking just
>>>any bijection i: S <-> {1, 2, 3, ..., |S|}, for a finite set S?
>>
>>Now I don't get you ;)
>
> I mean that elements can be ordered in an arbitrary manner, after which
> they may be organized as a list. The resulting list will be a value
> computed out of the original set. Any reasonable implementation of a
> set would give you that, IMHO.
Of course it would be in practice trivial in any implementation of set.
But let me repeat, it would violate the basics of algebra (which, as I
said previously, SQL did and wound up a big ball of mud).
Another idea would be to wrap the arbitrary linearization of a set in a
type that explicitly disallows any iteration primitives except for map
(map in the FP sense), and of course allows getting to the set back.
This would IMHO come close to what I'm after. I'm not an expert in
Haskell, is it possible?
But I guess we are back with a monad then, right?
>>By list deconstruction I mean mapping it (in the mathematical sense of
>>map) onto a finite system (such as a pair) plus binding (in the FP
>>sense). An example is the typical head-tail decomposition. I'm not
>>strong about the terminology, though.
>
> If you mean deconstruction as for values of an algebraic type, a set
> isn't such a value in the first place, so it should come as no surprise
> that it can't be decomposed that way :)
I know, I know. Well, I guess I'm looking for a substitute. Some smart
formulation to overcome the obstacle.
Dinko Tenev
> All that matters is type correctness.
I often get to see this stated, mostly implicitly, but I beg to differ.
Consider this:
rMap :: (x -> y) -> [x] -> [y]
rMap f = map f . reverse
You do have type correctness. Now, would you like to call rMap a map?
> We have (currently)
>
> map: x->y->[x]->[y]
>
> I'd like to have ({x} is for a set of x)
>
> map: x->y->{x}->{x}
>
> defined elegantly without introducing {arbitrary-element|the-rest} and,
> if possible, without resorting to monads.
Monads or not, { arbitrary-element | the-rest } is exactly what you
get, both implementation-wise and conceptually, at least as far as
proposals in this thread go :)
> I don't really understand your complaints about loosing the structure.
> Extensionally the structure (types) is preserved in a strict and natural
> way.
Not exactly complaining, just pointing out a difference, and I am
talking about the structure of particular values, not types.
Cheers,
Dinko
christop...@gmail.com
make items no longer unique. That is what I was trying to convey.
Unfortunately my background is not CS so my terminology is a bit skewy.
Regards,
Christophe
Ketil Malde
> You are correct, but a set requires unique itiems. A mapping might
> make items no longer unique. That is what I was trying to convey.
I guess the confusion arrives because the term "mapping" often refers
to a bijective function. In CS (or FP), map is primarily constructing
a list by applying a function to elements in another list, and by
extension, constructing a collection by applying a function to another
collection of the same type. This is, as evidenced by the present
example, not the same thing :-)
-k
--
If I haven't seen further, it is by standing in the footprints of giants
Aaron Denney
> But with maps you have a one-to-one correspondence between input and
> output structures.
Not as the word "map" is generally used in physics or CS, or even math
generally that I know about. There may be a corner of math that uses
"map" to imply that, but I'm unaware of it. To me, "map" just means
"function".
--
Aaron Denney
-><-
RobertSzefler
RobertSzefler napisal(a):
> How do you elegantly define functional map over sets? 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([h|t],f)=[f(h)|map(t,f)]
>
> approach won't work consistently over sets without introducing ugly
> things like deconstructing sets into an arbitrary element ("head") and
> the rest ("tail") like this (hypothetical syntax):
>
> map({},f)={}
> map({e|S},f)={f(e)|map(S,f)}
>
> The problem is taking an arbitrary element of set is not FP-kosher as it
> allows ordering of an arbitrary set which is obviously un-nice (and
> would almost certainly violate generic referential transparency). How is
> this problem solved in practice? I think map if defined as basic would
> be powerful enough to implement most if not all set ops, is it the case
> in practice that maps over sets are built-in in functional languages?
>
> I am aware that my question is stated a bit ambiguously as I dont quite
> imagine what appropriate elementary set operations would be FP-wise. All
> comments are welcome.
I just found this: Martin Erwig, "Categorical Programming with Abstract
Data Types"
http://web.engr.oregonstate.edu/~erwig/papers/CategoricalADT_AMAST98.ps.gz
It seems that the problem is indeed severe, quoting the above:
"It is striking that the categorical framework has been applied only
sporadically to data types that are not just given by free term
structures, such as abstract data types. Although the catamorphism
approach principally works also for sub-algebras that satisfy certain
laws, one cannot map into algebras with less structure [9, 10]. This
innocent looking restriction means a rather severe limitation of
expressiveness: for instance, such a simple task as counting the
elements of a set cannot be expressed by a catamorphism"
Tough luck. I guess even generalizations such as hylomorphisms would
not change this (they decompose to cata * ana). Erwig proposes a
solution for general ADTs (his focus seems mainly to be graph
algorithms) based on bialgebras, but is this some weird math. Anyone
experienced in this field could provide a clue?
Jon Harrop
> On 2005-11-28, Dinko Tenev <dinko...@gmail.com> wrote:
>> But with maps you have a one-to-one correspondence between input and
>> output structures.
>
> Not as the word "map" is generally used in physics or CS, or even math
> generally that I know about.
Yes. However, "map" is a homonym. In this case, Robert has tried to clarify
what he means by stating "the", "standard" and "FP sense". Given Roberts
requirements, I wouldn't call what he wants a map.
> There may be a corner of math that uses "map" to imply that, but I'm
> unaware of it.
The "corner of math" is computer science. This type of "map" is sometimes
called an "inner map" to avoid confusion with mathematical nomenclature (a
mapping) that you refer to. An inner map accepts a function "f" and a data
structure and returns a similarly-shaped data structure with each element
"x" replaced with "f x".
For example, a map over a binary tree:
# type 'a tree = Empty | Node of 'a tree * 'a * 'a tree;;
type 'a tree = Empty | Node of 'a tree * 'a * 'a tree
# let rec map f = function
Empty -> Empty
| Node(l, x, r) -> Node(map f l, f x, map f r);;
val map : ('a -> 'b) -> 'a tree -> 'b tree = <fun>
# map (fun x -> x+1) (Node(Node(Empty, 1, Empty),
2,
Node(Empty, 3, Empty)));;
- : int tree = Node (Node (Empty, 2, Empty),
3,
Node (Empty, 4, Empty))
--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com
Neelakantan Krishnaswami
>
> 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
> ;)
So, the difference between a list and a finite set is that a list is a
free algebra, and sets aren't. You can construct a list of elements of
type t using the following signature:
nil : set
add : t * set -> set
There are no equations between the lists you build up using nil and
add, aside from reflexivity. A finite set is also generated by these
two function symbols, but it satisfies the two additional equations
forall x, y, rest. add x (add y rest) == (add y (add x rest))
and
forall x, rest. add x (add x rest) == add x rest
The first equation says that changing the order of insertion doesn't
change the value, and the second says that adding the same element
multiple times won't change the value. (The second equation is why
sets require equality.)
Assuming that you have a function
choose : set -> (t * set) option
which satisfies the equations
choose nil == None
and
forall x, rest. there exist x', rest'.
(add x rest) == (add x' rest') and
(x' not in rest') and
choose (add x rest) == Some(x', rest')
then you can define a perfectly good map function in the obvious way:
fun map f list =
case choose list of
None => nil
| Some(x', rest') => add x' (map f rest')
Now, you can show the correctness of map with a simple inductive
argument based on the number of distinct elements of a finite
set. There are other ways of specifying sets algebraically, but this
works fine -- you can define map, union, and so on, and relatively
easily prove that they have the desired properties.
If I understand you correctly, the reason you're worried arises from
something like the following implementation:
structure IntSet =
struct
type set = int list
val nil = []
val add (x, set) = x :: set
fun choose [] = NONE
| choose (x :: tail) = SOME(x, filter (fn x' => x <> x') tail)
end
You are worried that if you have
val s = add(1, add(2, nil))
val r = add(2, add(1, nil))
then s and r represent the same set {1,2}, but that calls to s and
r can give different results:
choose(s) evaluates to SOME(1, {2})
and
choose(r) evaluates to SOME(2, {1})
This superficially looks like it breaks the equational reasoning
property. However, this isn't actually so, because of the way that we
specified choose:
forall x, rest. there exist x', rest'.
(add x rest) == (add x' rest') and
(x' not in rest') and
choose (add x rest) == Some(x', rest')
Here, we very carefully DON'T say that
choose (add x rest) == Some(x, rest)
Instead, we use an existential quantifier to say that choose returns
some distinct element of the set, not necessarily the "most recently
inserted" one. Indeed, upon reflection it should be clear that because
of the property that the order of insertion doesn't matter, we /can't/
promise any such behavior.
--
Neel Krishnaswami
ne...@cs.cmu.edu
Dinko Tenev
When you're saying that you're mapping a list or a tree, you mean
something much more specific than just computing a function on it. I
could have called it something else to avoid confusion, but with enough
of the context of this thread, confusion should be out of the question.
Cheers,
Dinko
RobertSzefler
Note the original post's subject: FP-style map *over* set, not "of sets".
RobertSzefler
[...]
> Now fold must have the added constraint to the interface that when it
> is called with "fold set e s u", then u must be idempotent,
> commutative and associative. If these conditions are fulfilled, then
> the implementation of fold can do an ordinary tree fold in some
> definite order, but the result still cannot expose the ordering.
[...]
From what I gather, it all boils down to maps and (especially) folds
working over things in the Cpo category, ie, as Neelakantan Krishnaswami
pointed out, free algebras (is it?). What if we abandon that formalism
and try to work in a different setting, a'la Bird-Meertens, but
dismissing the notion of order in recursion? What would the underlying
category be then? (I'm just starting to learn this, sorry for my
ignorance) I guess the objects would still be sets (?) and arrows would
have to be chosen to reflect the lack of meaningful order... Is it the
case that for example the Third Manifesto can be formalized in such
generic terms?
Next we'd have a problem of recursively (or meta-recursively as a
recursion over a set isn't really a recursion) processing mixed
structure things, like lists of sets of lists. Here's where my mind
starts to crash and burn ;)
Does anyone know about any work in these directions?
> Now you can implement map as:
>
> map f s = fold s empty (single . f) union
>
> However, the constraints on the u parameter cannot be expressed in the
> type systems of most practical languages (you need dependent types),
What about purely relational languages? (Tutorial D?)
> so you may have to rely on an informal interface specification (i.e.
> human-readable documentation), which is of course amenable to abuse.
Sorry again for my ignorance, but I have to push the issue as I have a
gut feeling that what we discuss here is of deep theoretical and
practical importance. Thanks again for your input!
Dinko Tenev
[...]
> >>On 2005-11-28, Dinko Tenev <dinko...@gmail.com> wrote:
> >>
> >>>But with maps you have a one-to-one correspondence between input and
> >>>output structures.
> Note the original post's subject: FP-style map *over* set, not "of sets".
What I actually meant was that there was an *element-to-element*
correspondence between the input and output structures (as explained in
detail in Jon Harrop's post.) My apologies.
Cheers,
Dinko
Henning Makholm
> It seems that the problem is indeed severe, quoting the above:
My impression is that you want too much in too complicated a fashion.
Because "set of T" is not an initial algebra (or sufficiently close to
it for catamorphisms to make sense), you cannot treat it as if it is
one.
However, "set" or "finite set" is still a (covariant) _functor_, and I
would say that the action of a functor on a morphism (i.e., the
function you want to map over the structure) is the most natural and
general way do define what we mean when we say "map f over som data
structure": We view the data structure as a functor in some
appropriate way, and then lift f trough this functor.
Yes, almost nothing happens here, which suggests that "map" should in
general be tought of as a _primitive_, rather than something you
necessarily want to construct out of smaller bits.
The decomposition of the map operation as a catamorphism is nice and
interesting when it works, but it is not the end of the world when it
doesn't.
--
Henning Makholm "We can hope that this serious deficiency will be
remedied in the final version of BibTeX, 1.0, which is
expected to appear when the LaTeX 3.0 development is completed."
Vesa Karvonen
> How do you elegantly define functional map over sets?
Perhaps you want to be able to treat sets as some sort of inductive
datatypes? If that is the case, then you might want to take a look at
Martin Ervig's papers on FGL:
http://web.engr.oregonstate.edu/~erwig/fgl/
IOW, I think that it would probably be possible to specify a "match"
operation on sets (and hopefully implement it reasonable efficiently)
that would allow you to treat sets inductively in a "functional style"
(map, fold, etc... would then fall out naturally). The idea seems so
simple to me that I would not be surprised to hear about prior art.
(If you know of relevant papers, please post details.)
-Vesa Karvonen
RobertSzefler
> RobertSzefler <NOSPAMrsze...@murator.com.pl> wrote:
>
>>How do you elegantly define functional map over sets?
>
> [...]
>
> Perhaps you want to be able to treat sets as some sort of inductive
> datatypes? If that is the case, then you might want to take a look at
> Martin Ervig's papers on FGL:
Yes, I was thinking exactly about that and concluded that it is
essentially impossible (due to free algebra/Cpo obstacle stuff).
> http://web.engr.oregonstate.edu/~erwig/fgl/
Somehow these eluded me (and I did dig through Erwig's papers many
times). I have to read on this.
> IOW, I think that it would probably be possible to specify a "match"
> operation on sets (and hopefully implement it reasonable efficiently)
> that would allow you to treat sets inductively in a "functional style"
> (map, fold, etc... would then fall out naturally). The idea seems so
> simple to me that I would not be surprised to hear about prior art.
> (If you know of relevant papers, please post details.)
I seem to recall some papers from early 80s (?) dealing with such
formalizations in relational calculus, but don't remember them exactly...
genea
list... another words a list with unique elements in it... I saw this post
today and just started thinking that the only thing necessary to
accomplish this and !! in a gene0ric way is that for any type [a] that
there be a derived EQ? ... What came of it was indeed able to do more than
you were asking for, in that one can take a list that is NOT a set to start
with and convert it to one, by making the components contained in it unique
by filtering through the list and removing any redundant components..
giving a list with the order unchanged from the input so:
listToSet [2,4,1,7,4,3] -> [2,4,1,7,3]
and setmap ((*) 3) [2,4,1,7,4,3] -> [6,12,3,21,9]
auto converting to [2,4,1,7,3] prior to doing the mapping and as you will
note it is in the same order... not sure that was important to you or
not... but that is true set behaviour in that it is an unordered
collection of unique items...
now this of course works if the list is already a set.. it just also is
coerced to a set if it is not... Anyway this uses no monads, is purely
functional... and most of all SIMPLE, and out here in the desert where I
live simple is better!! I threw in a foldr function that works also just
for another example of how to do this.. Now I may be missing something so
I just hope this little hack is something you can use... It will work over
list structured sets of any type that you can write an equality test
for... so think it will do what you want. So here for your use and the
worlds use is the whole shebang and I have to agree with the fellow who
said that this has probably all been done before somewhere.. gene
-- setFunctions.hs
-- author Gene A.
-- date last revised: 2005.12.19
-- version 0.1
-- ====================================
-- uniq
-- uniq filters out any non unique items from a list
uniq :: Eq a => [a] -> [a]
uniq [] = []
uniq (x:[]) = [x]
uniq (x:xs) = x : uniq (filter ((/=) x) xs)
-- ====================================
-- setFromList
-- converts a list that may have non unique members to a list with unique
members therefore
-- a set structured as a list, but a set never the less
setFromList :: Eq a => [a] -> [a]
setFromList a = uniq a
-- ====================================
-- setmap
-- this function will take a set as a list and map a function over it and
return a
-- set structured as a list.... well actually it will do that but will
also take a list that is
-- not a set map the function over it and then by eliminating redundant
members turn it into a
-- yup ...umhum a set structured as a list..
setmap :: Eq b => (a -> b) -> [a] -> [b]
setmap f s = uniq $ map f s
-- ====================================
-- setFoldr
-- This function first ensures that a list is a set and then applies the
-- (foldr f) to it giving it a correct result.
setFoldr f a s = foldr f a $ setFromList s
genea
loading it into ghci using
ghci setFunctions.hs which contained the above code...
Loading package base-1.0 ... linking ... done.
Compiling Main ( setFunctions.hs, interpreted )
Ok, modules loaded: Main.
*Main>
*Main>
*Main> :b Main
setFoldr :: Eq a => (a -> b -> b) -> b -> [a] -> b
setFromList :: Eq a => [a] -> [a]
setmap :: Eq b => (a -> b) -> [a] -> [b]
uniq :: Eq a => [a] -> [a]
*Main> setFromList "this is a test to see if it works on chars"
"this aeofwrknc"
*Main> setFromList $ words $ "this is a test to see if the function works
in a test setting on words"
["this","is","a","test","to","see","if","the","function","works","in","setting","on","words"]
*Main> setFromList $ words $ "black blue yellow blue black red crimson
yellow"
["black","blue","yellow","red","crimson"]
*Main> setFoldr (++) " " $ setFromList $ words $ "black blue yellow blue
black red crimson yellow"
"blackblueyellowredcrimson "
*Main> setmap (\x -> x + 3) [2,7,3,1,5]
[5,10,6,4,8]
*Main> setmap (\x -> x * 3) [2,7,3,1,5,2,5,3]
[6,21,9,3,15]
*Main> setmap (\x -> 0) [2,7,3,1,5]
[0]
*Main> setmap (\x -> 5) [2,7,3,1,5]
[5]
*Main> setmap (\(x,y) -> ((x + 3),(y * 2))) [(2,4),(4,4),(3,1)]
[(5,8),(7,8),(6,2)]
*Main> setmap (\(x,y) -> ((x + 3),(y * 2))) [(2,4),(4,4),(3,1),(4,4)]
[(5,8),(7,8),(6,2)]
*Main> setmap (\(a,b,c) -> ((a ++ " programmer"),(b * 4),(c * 5)))
[("gene",10,5),("Robert",12,5)]
[("gene programmer",40,25),("Robert programmer",48,25)]
Anywhere now if you are storing all of this to a graph or a tree structure
of some kind this could still be a useful hack, if you just write the
conversion ... flattening to list and then loading back into the tree or
whatever kind of graph structure you are using, IF .. it is not to be used
too too often and you just need something that works .. like now...
otherwise it is back to the drawing board... although as a sometimes lisp
and scheme user over the much too many years, I kind of overuse the list
structure for everything... so am used to thinking of terms of lists a
lot... hope this is at least interesting even if not terribly useful...
gene