map semantics

[Andy C]

Hi,

I have a short question, why map builds up a LazySeq instead of an input collection as found below:

user=> (type (map #(mod % 3) #{3 6}))
clojure.lang.LazySeq
user=> (type (map #(mod % 3) '(3 6)))
clojure.lang.LazySeq
user=> (type (map #(mod % 3) [3 6]))
clojure.lang.LazySeq
user=> (type (map #(mod (% 1) 3) {:a 3, :b 6}))
clojure.lang.LazySeq

One would expect to "(map #(mod % 3) #{3 6})" evaluate into "#{0}". Is it arbitrary decision or there is a theory behind it?

Best,

Andy

[Atamert Ölçgen]

Why should it build a concrete result?

Here's my reasons why it makes sense to be lazy here:

- It would use more memory otherwise. Since, if you are transforming a list to a set there's got to a transformed copy of the original data structure when it's materialized.

- It might take longer than necessary to calculate. Suppose you've threaded the result into (take n), now, you need to call the predicate of map only n times.

If you think about large data structures (maybe even infinite sequences), laziness makes more sense.

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--
Kind Regards,
Atamert Ölçgen

-+-
--+
+++

www.muhuk.com

[Andy C]

On Fri, Feb 7, 2014 at 7:53 PM, Atamert Ölçgen <mu...@muhuk.com> wrote:

Why should it build a concrete result?

I realize the benefits of using LazySeq and do not have a strong opinion besides things gotta be consistent. Putting practical advantages and having a good default behaviour aside, I was wondering if there is a strong argument to use one vs another.

set-s are indeed a sticky point here since the result of a map would different depending in the convention. So by that token there is something not abstracted well .... or I just do not understand map semantics well.

This topic was in fact inspired by Scala implementation where map on Set returns Set (and so forth).

Thx,

A.

[Atamert Ölçgen]

On Sat, Feb 8, 2014 at 3:05 AM, Andy C <andy.c...@gmail.com> wrote:

set-s are indeed a sticky point here since the result of a map would different depending in the convention.

No the result would be the same. Only the order of the elements in the lazy sequence would differ, but that's to be expected since sets are not ordered.

[Andy C]

user=> (map #(mod % 3) #{3 6})
(0 0)
user=> (set (map #(mod % 3) #{3 6}))
#{0}

[Andy C]

I do perceive sets, lists, vector as atoms which are indivisible (well, this is not true but this is popular meaning) from semantics standpoint. Therefore map is just a function which processes them as whole, again from semantics point of view. Implementation and laziness should not matter really and we still should get the same result.

[Mars0i]

Andy C, I think that in the Clojure world, there is a widespread view that lazy sequences should be the (or one of the) primary datatypes, that iteration should usually produce lazy sequences, etc.  They are something like the default in Clojure.  Clojure includes a systematically organized and very handy collection of functions all of which are designed to produce and/or use lazy sequences.  That collection of tools is one of Clojure's strengths.  From this point of view, it's very natural that map should return a lazy sequence, no matter what kind of collection(s) is (are) passed into it.  And then if one doesn't want a lazy sequence as output, there are various ways to realize the output or convert it.   The into function is a general-purpose tool that can often be used for this purpose.

(That said, I currently hold the heretical view that laziness should be optional in Clojure--that maybe there should be a parallel set of non-lazy tools, or even, possibly, that there should be a switch to turn laziness on or off before compilation.  I suspect that most Clojure programmers would disagree with me, and I am a relative newbie in any event.  (If anyone wants to discuss this point now, we should probably start another thread.))

[Andy C]

I actually like the laziness by default but as you suggest, wish there is a way to switch it on/off for blocks of the code (rather than compiler option). Scala guys did some research and in most practical cases Lists are very short hence they are not lazy and evaluated at once. Just an interesting tidbit, not an argument.

But what really bothers me is that laziness / not laziness affects the result of evaluation as in above example. That is against some fundamental rules of FP (gotta check how Haskell does it :-P).

Again, question is what map really is, and why it gotta be invertible. Let's say that we have a new collection type, a tree. And mapping every node in the tree to a new value rearranges entire construct. Having map to produce a lazy seq implies that the input must be serializable (or linear).

[Michael Gardner]

On Feb 7, 2014, at 22:17 , Andy C <andy.c...@gmail.com> wrote:

> Having map to produce a lazy seq implies that the input must be serializable (or linear).

That's just what map is in Clojure: an operation on sequences. It works on various concrete types because those can be viewed as sequences; map knows nothing of their structure. What you're looking for is another abstraction entirely (see clojure.walk, for example).

[John D. Hume]

On Fri, Feb 7, 2014 at 9:41 PM, Andy C <andy.c...@gmail.com> wrote:

I do perceive sets, lists, vector as atoms which are indivisible (well, this is not true but this is popular meaning) from semantics standpoint. Therefore map is just a function which processes them as whole, again from semantics point of view. Implementation and laziness should not matter really and we still should get the same result.

Following your intuition, what would you expect from the following?

> (map + [1 3 5] '(2 4 6)) 

# => ?

[Mars0i]

On Friday, February 7, 2014 10:17:15 PM UTC-6, Andy C wrote:

But what really bothers me is that laziness / not laziness affects the result of evaluation as in above example. That is against some fundamental rules of FP (gotta check how Haskell does it :-P).

Well, it's not really laziness that's affecting the result of evaluation, in the sense that you mean.  It's just the design decision that the result of evaluation should always be the same type.  mapv does the same thing, but returns a vector.  Giving functions polymorphic return types makes things more complicated.

[Andy C]

Following your intuition, what would you expect from the following?

> (map + [1 3 5] '(2 4 6)) 

# => ?

It only gets worse, as the result of below should be undefined (using classic set definition):

 

user=> (map + #{0 1} #{0 1})
(0 2)
user=> (map + #{1 0} #{1 0})
(0 2)

[Sean Corfield]

But you're misunderstanding what map does: it converts its collection
arguments to _sequences_ and then it processes those sequences. Map
doesn't operate on sets, or vectors, or maps, only on sequences.

Scala goes out of its way to retain input types as output types on
many of its collection operations, and that's its choice. But it's not
how Clojure is defined - Clojure operates on abstractions above the
concrete types.

Sean

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your
> first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups
> "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to clojure+u...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.



--

Sean A Corfield -- (904) 302-SEAN
An Architect's View -- http://corfield.org/
World Singles, LLC. -- http://worldsingles.com/

"Perfection is the enemy of the good."
-- Gustave Flaubert, French realist novelist (1821-1880)

[Andy C]

On Sat, Feb 8, 2014 at 12:06 AM, Sean Corfield <se...@corfield.org> wrote:

But you're misunderstanding what map does: it converts its collection
arguments to _sequences_ and then it processes those sequences. Map
doesn't operate on sets, or vectors, or maps, only on sequences.

Your assertion that I "am misunderstanding something" is wrong.

One cannot convert amorphic set into linear sequence without assuming certain order. And as with every assumption, it always comes with some less or more pragmatic but arbitrary decision which might change over time and ruin peoples programs.

I would expect Clojure to throw "IllegalArgumentException Don't know how to create ISeq from: clojure.lang.PersistentHashSet" or document it well in map somewhere. 

"Perfection is the enemy of the good."

Now judging by your sig, it all does not surprise me LOL

[Jozef Wagner]

Every persistent collection in Clojure supports conversion to the sequence of items. This is clearly documented in the official docs and there is no surprise here.

The order or items in the resulting sequence is dependent on the collection type. As the conversion to the sequence is a referentially transparent function, you will always get the same order for the same collection. 

JW

[Andy C]

>Every persistent collection in Clojure supports conversion to the sequence of items. This is clearly documented in the official docs and there is no surprise here.

Would you mind to point me to that piece where doc describes what order seq chooses when converting a set to it. (I honestly tried to find it but could not.)

>The order or items in the resulting sequence is dependent on the collection type. As the conversion to the sequence is a referentially transparent function, you will always get the same order for the same collection.

So for particularly huge sets, I understand Clojure will not attempt to sort them (read be inefficient) before producing the sequence, is it correct?

[Ambrose Bonnaire-Sergeant]

On Sun, Feb 9, 2014 at 12:40 AM, Andy C <andy.c...@gmail.com> wrote:

>Every persistent collection in Clojure supports conversion to the sequence of items. This is clearly documented in the official docs and there is no surprise here.

Would you mind to point me to that piece where doc describes what order seq chooses when converting a set to it. (I honestly tried to find it but could not.)

The seq order is undefined for non-sequential, unsorted collections like clojure.lang.PersistentHashSet (the result of clojure.core/{hash-,}set).

Thanks,

Ambrose

[Gary Verhaegen]

The definition of map in Clojure is that it is a function on seqs. It is defined as operating on a seq, and returning a seq.

Whereas in Scala, you hold an object and have thus access to its class (so you can call Set.map on a set and List.map on a map), in Clojure there is only one function clojure.core/map, and it is defined as taking a seq as argument. seq is an abstraction, for which there are many functions in the Clojure standard library. Whenever you are calling any one of them, you leave the realm of concrete collection and enter the realm of seqs. 

Functions that operate on seqs are listed on the following page: http://clojure.org/sequences.

Now, these functions only accept seqs as arguments. You are right that one possible choice would have been to throw an expection every time you pass in something else than a seq, which would force you to write something along the lines of:

(map #(mod % 3) (seq #{3 6}))

The language designer has decided that all of the sequence functions in the standard library would, instead of throwing an exception when the argument is not a seq, first try to convert it to a seq (by calling the seq function as illustrated above).

This is a design choice which could have been different. This choice in particular is based on the famous Perlis quote "It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures." So the standard library focuses on providing a lot of very useful functions on the sequence abstraction; what all of these functions have in common is that they can be described in terms of considering the elements of the seq one at a time.

Arguably, most collections should be able to provide access to all of their elements one at a time. Any collection that can do that can participate in the seq abstraction. Practically, this means that if you define your own data structure (to build on the running example in this thread, some kind of tree), you only have to implement one function - seq - on your collection to enable the use of all the seq functions from the standard library (and many other functions from other libraries that also build on the seq abstraction). However, since all of these functions know nothing about your data structure except that they can ask for the next element, they have no way to keep the structure of your collection.

As a general rule, in Clojure, each collection type has a small number of functions that are defined for that collection (and are thus type-preserving when it makes sense), but all basic collections support the seq abstraction and most of the work is done through the sequence functions.

Each collection type defines how to turn itself into a seq; non-ordered collections in the Clojure base language (sets and maps) make no promise about the order of their elements when turned into a seq (if you really want to know, you can look at the implementation, but you cannot count on it not changing in the future).

[Timothy Baldridge]

First of all, you are right. Map with things like sets is a bit of iffy concept. Now, most of the the time, I just don't care. If I was to increment every value in a set I'll just do (set (map inc #{1 2 3})) and not really care less about data structure theory. It works and I can get work done. 

However, the bigger problem comes when we start discussing parallel operations on these datasets. Here it makes no sense to define an order for (pmap inc #{1 2 3}) when there is no defined order in the input collection to begin with. This is the entire reason behind clojure's reducers, they allow the input and output data structures to drive how processing is handled.

http://clojure.com/blog/2012/05/08/reducers-a-library-and-model-for-collection-processing.html

And as the article states, reducers "use(s) regular data structures, not 'parallel collections' or other OO malarkey"

Timothy Baldridge 

--
“One of the main causes of the fall of the Roman Empire was that–lacking zero–they had no way to indicate successful termination of their C programs.”
(Robert Firth)

[Andy Fingerhut]

This might be too detailed a point, but I wanted to mention that while you will always get the same order for the same collection (same as determined by identical?, or Java ==, i.e. it is the same object in memory), you are *not* guaranteed to get the same order for collections of the same type that are equal to each other as determined by Clojure = or Java .equals.  In particular, if two values have the same hash value, then if they are used as a set in a Clojure PersistentHashSet or a key in a PersistentHashKey, they are put into a linear list in a hash bucket for that hash value, and their order in that list can be different in different sets/maps, and the order that (seq ...) returns on those sets/maps will be different.

I am not certain, but this might violate referential transparency (replacing a value that is equals for another value in an expression will always give you an equal result).

I was curious whether anyone knows whether Haskell has hash-based data structures like this, and do they somehow guarantee referential transparency?  Perhaps by requiring the items to be sortable?

Andy

[Softaddicts]

The sequence abstraction is documented here:

http://clojure.org/sequences

Clearly map is documented as working on sequences.

A sequence is not a concrete type as explained by others on
this thread.

If you really need some specific behavior from a concrete type then
do not rely on sequences. Use the concrete type directly in all your code.

Choose the right tool to do your job. Clojure offers so many options
that this should not be difficult.

Luc P.

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
--

Softaddicts<lprefo...@softaddicts.ca> sent by ibisMail from my ipad!

[Moritz Ulrich]

On Sat, Feb 8, 2014 at 6:39 PM, Timothy Baldridge <tbald...@gmail.com> wrote:
> First of all, you are right. Map with things like sets is a bit of iffy
> concept. Now, most of the the time, I just don't care. If I was to increment
> every value in a set I'll just do (set (map inc #{1 2 3})) and not really
> care less about data structure theory. It works and I can get work done.

(let [x #{1 2 3}]
(into (empty x) (map inc x)))

[Andy C]

First, thanks everybody for explanations of design decision behind map and collections. I should in fact change subject to seq semantics ;-).

For me the bottom line is that while I do not care about order so much I still can count on that  seq function will produce consistent sequences. Or wait a sec:

 

This might be too detailed a point, but I wanted to mention that while you will always get the same order for the same collection (same as determined by identical?, or Java ==, i.e. it is the same object in memory), you are *not* guaranteed to get the same order for collections of the same type that are equal to each other as determined by Clojure = or Java .equals.  In particular, if two values have the same hash value, then if they are used as a set in a Clojure PersistentHashSet or a key in a PersistentHashKey, they are put into a linear list in a hash bucket for that hash value, and their order in that list can be different in different sets/maps, and the order that (seq ...) returns on those sets/maps will be different.

I am not certain, but this might violate referential transparency (replacing a value that is equals for another value in an expression will always give you an equal result).

This is not too detailed. In fact this is the ultimate question. It would mean that two logically identical sets can produce different LazySeq's depending how they came to existence ...

[Jozef Wagner]

By 'same' I've meant an identical :). 

Two collections equivalent by their values may easily have a different order of their items. This is because in unordered collections, their internal order (as any other implementation detail) must not be taken into account when comparing for value equivalence.

user=> (def s1 #{-3 2 1})

#'user/s1

user=> (def s2 (apply sorted-set s1))

#'user/s2

user=> s1

#{1 -3 2}

user=> s2

#{-3 1 2}

user=> (identical? s1 s2)

false

user=> (= s1 s2)

true

user=> (= (seq s1) (seq s2))

false

user=> (seq s1)

(1 -3 2)

user=> (seq s2)

(-3 1 2)

JW

[Andy C]

On Sat, Feb 8, 2014 at 1:46 PM, Jozef Wagner <jozef....@gmail.com> wrote:

Two collections equivalent by their values may easily have a different order of their items.

It all boils down this:
  is it possible to have two clojure.lang.PersistentHashSet with identical values (in mathematical sense) but producing different seqs?

[Michael Gardner]

On Feb 8, 2014, at 15:14 , Andy C <andy.c...@gmail.com> wrote:

> It all boils down this:
> is it possible to have two clojure.lang.PersistentHashSet with identical values (in mathematical sense) but producing different seqs?

Are you serious? The entire point of the email you responded to was to answer that question.

("But why male models?")

[Jozef Wagner]

Yes. Behold a Murmur3 hash collision:

user> (def n1 -2023261231)

#'user/n1

user> (def n2 9223372036854771971)

#'user/n2

user> (== (hash n1) (hash n2))

true

user> (def s1 (conj #{} n1 n2))

#'user/s1

user> (def s2 (conj #{} n2 n1))

#'user/s2

user> (= s1 s2)

But practically, I cannot think of any scenario where you will need a guarantee that two unordered non identical but value equivalent collections need to produce same ordered seq.

JW

--

[Jozef Wagner]

I've forgot the most interesting part :)

user> (= s1 s2)

true

user> (= (seq s1) (seq s2))

false

JW

[Jozef Wagner]

Well it does not break referential transparency if both equalities (for input values and for results) are of a same kind. You would have to compare inputs by value and outputs by identity, if you want to percieve an inconsistency.

JW

[Sean Corfield]

On Feb 8, 2014, at 7:59 AM, Andy C <andy.c...@gmail.com> wrote:
> Your assertion that I "am misunderstanding something" is wrong.

Now that you've seen everyone else's responses, perhaps you understand my assertion was correct? :)

Sean Corfield -- (904) 302-SEAN

An Architect's View -- http://corfield.org/

"If you're not annoying somebody, you're not really alive."
-- Margaret Atwood

[Andy C]

user> (= s1 s2)

true

user> (= (seq s1) (seq s2))

false

Thx. If a=b  then f(a) must = f(b). Something is broken here.

[Andy Fingerhut]

It is working as designed.

If you do not want this, consider using sorted sets / sorted maps, where (= s1 s2) implies (= (seq s1) (seq s2)).

Or, perhaps another programming language would be more to your liking.

Andy

[John Mastro]

Hi Andy,

If a seq is a sequential view of a thing, and a set is an unordered thing, then
it does not seem shocking to me that multiple sequential views of a given set,
with different orderings, are possible.

This may not be the only way to do things; and it may not be the way other
languages do it; and it may not match your preference. But I think it's clearly
wrong to say that it's internally inconsistent or "broken".

It's perhaps hard to say this without sounding condescending, but rather than
seeking to identify all the ways in which Clojure isn't Haskell, it might be
more useful to pursue an understanding of Clojure (including its
definitely-not-nonexistent flaws!) on its own terms.

- John

[John Mastro]

To add just one more thing to this: Referential transparency is clearly
valuable, but it's not the *only* valuable property a function or system might
have. There are always tradeoffs to be made. Clojure has made different
tradeoffs than you expected, or would yourself have made, but that doesn't
/a priori/ mean they're wrong.

- John

[Andy C]

I can ensure all of you that it is very uncomfortable for a newcomer with a goofy nick to just come in and say things are broke LOL . So at that point I have two choices:

1) as suggested, find another programming language but that would mean that I would have to erase my Clojure tattoo (very painful).

2) stop making enemies and pretend that seq on sets is cools and neat and we really do not need to stick to fundeaments of FP:  a=b => f(a) = f(b) in critical part of the language. It ain't going to happen either.

Although, the worst part about it all is that my carefully crafted piece of software used for controlling nuclear power plants relies on Clojure set-s. As we above some part of it is non deterministic as the calculated controls paramters depends on the order of adding elements to set .... That literally sucks!

In any case, see you at Clojure West conference and thanks again for all the replies,

Best regards,
Andy

 

[Mars0i]

Maybe another way to put it is that what is, uh, "broken" isn't 'map' or 'seq', but '=', which is willing to tell you that two things (sets) are the same when they're not!  We also have the non-broken predicate 'identical?', however, that gets it right.  It's nice to also have a set-equal predicate, which ignores differences in how sets are stored, and ... that's what '=' is!  However, if we interpret '=' as implying that when the same function is applied to things that are "equal" in its sense, then we are making a mistake: '=' doesn't mean that.  According to this reasoning, nothing here is broken, even from an extra-linguistic perspective.  '=' just shouldn't be misunderstood.  (In a language with different design and style goals, it might been preferable to define "=" to mean what Clojure means by 'identical?', and use something else--perhaps "equivalent?"--for a predicate analogous to Clojure's '='.)

[Mars0i]

Maybe physical identity is too strong of a requirement for equality.  So another way to think about it is that it's 'hash-set', 'set', and '#{}' that are--you know--"broken", but that there's a fix, which is to always use 'sorted-set'.  (I'm assuming that calling 'seq' on any two sorted sets that are = always returns seqs that are =.)

(Don't take offense at the tone of my remarks.  I think we're all on the same side here.)

[Michał Marczyk]

The Contrib library algo.generic provides a function fmap which does
preserve the type of its input.

As for the idea that clojure.core/map should preserve type, it's worth
remembering that in order to map a function over a set and return a
set, we must do two things: (1) apply the function to each element of
the input set, (2) produce a set containing the resulting values. In
general, there is no better way to do this than to pour (map f s) into
a new set, because the shape of the output is for the most part
undetermined by the input (except if the input is empty or is a
*sorted* set of size 1; actually in the latter case there is the
comparator issue, see below).

So, the fundamental operations here are (1) mapping a function over a
sequence / iterator, (2) pouring a sequence of items into a
collection. As it happens, both (1) and (2) are useful in many
different scenarios, separately and together. Thus, they make great
primitives, and Clojure chooses to expose them as such.

Then of course map and filter are lazy and can be used to do things
like (->> some-sorted-set (filter p?) (map f) (take n)); take could be
reordered with map, but not with filter, and if it's ok for filter to
convert to seq implicitly, then it is also ok for map.

In the case of sorted sets and maps, there is no guarantee that the
input collection's comparator can deal with outputs from the function
passed to map.

So, these are some of the available conceptual arguments. There is
also a rather convincing practical argument in the form of the
existing body of Clojure code, written using the existing Clojure core
library and its conventions and achieving, in many cases, amazing
levels of clarity and concision.

Cheers,
Michał

[Jozef Wagner]

There are many types and flavors of equality, and only handful of symbols. Symbol '=' in Clojure does not represent yours fundamental = comparison operator. = in Clojure compares for the actual value ignoring concrete types of collections and the internal representation of how the items are stored. 

user=> (= [\1 \2] '(\1 \2) (first {\1 \2}) (seq "12"))

true

I has some not so obvious consequences for sure

user=> (assoc {[1 2] :foo} '(1 2) :bar)

{[1 2] :bar}

But it was carefuly designed that way, considering many trade-offs. Nothing stops you from defining another equality predicate that will suits your need.

JW

--

[Korny Sietsma]

Agreed - there are always tradeoffs.  Another common example is that pretty well any language that uses IEEE floating point is also breaking referential transparency in the interest of pragmatism:

user=> (= 0.3 (+ 0.1 0.2))

false

user=> (= (bigdec 0.3) (+ (bigdec 0.1) (bigdec 0.2)))

true

- Korny

[Andy C]

On Sun, Feb 9, 2014 at 4:46 AM, Michał Marczyk <michal....@gmail.com> wrote:

The Contrib library algo.generic provides a function fmap which does
preserve the type of its input.

Thanks for the pointer.
 

So, these are some of the available conceptual arguments. There is
also a rather convincing practical argument in the form of the
existing body of Clojure code, written using the existing Clojure core
library and its conventions and achieving, in many cases, amazing
levels of clarity and concision

 

Clojure is indeed very coherent with a few exceptions called "design trade-offs" :-). Deriving from Lisp wisdom and expanding those powerful concepts into a modern programming is priceless.

It is all good now.

Pozdr,
Andy