<< Back to previous view

[CLJ-1382] Vector sort order should be specified sufficiently to embrace sort-by-juxt Created: 13/Mar/14  Updated: 15/Mar/14  Resolved: 15/Mar/14

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.5
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Phill Wolf Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: data-structures, documentation, idiom


 Description   

Vectors of equal length sort in a way that seems natural – by
comparing their 0th elements, then their 1st, etc., until something
is different:

user> (def vv '(["c" 9] ["a" 100] ["a" 33] ["b" 8]))
#'user/vv
user> (sort vv)
(["a" 33] ["a" 100] ["b" 8] ["c" 9])

This property enables a blisteringly wonderful idiom for sorting
records by multiple keys:

user> (def mm (->> vv (map (fn [[p q]] {:p p :q q}))))
#'user/mm
user> (sort-by (juxt :p :q) mm)
({:p "a", :q 33} {:p "a", :q 100} {:p "b", :q 8} {:p "c", :q 9})

The sort-by-juxt idiom was described on briancarper.net[1], where it
was refined for Clojure 1.1 by Malcolm Sparks. Andy Fingerhut has
also written about it, thoroughly.[2]

Such lore gives it the odor of respectability, but the sort-by-juxt
idiom takes liberties beyond the documented behavior ("contract") of
vectors. APersistentVector indulges the idiom, but the clojure.org
Data Structures page does not say how vectors should compare.

The vector specification should be bolstered with enough traits of
vectors' sorting behavior to make the sort-by-juxt idiom safe to use
wherever Clojure might be implemented.

[1] http://briancarper.net/blog/488/sort-a-clojure-map-by-two-or-more-keys

[2] https://github.com/jafingerhut/thalia/blob/master/doc/other-topics/comparators.md



 Comments   
Comment by Alex Miller [ 13/Mar/14 9:52 PM ]

I don't understand what this ticket is asking for.

Comment by Andy Fingerhut [ 13/Mar/14 10:32 PM ]

It sounds like he is asking that the doc of clojure.core/compare say that vectors of equal length are compared in lexicographic order.

Comment by Phill Wolf [ 15/Mar/14 1:07 PM ]

"(sort-by (juxt" relies on a feature of vectors that the Clojure documentation does not guarantee. But using juxt in this way is part of the cultural fabric and helps make concise programs that "read like a definition" of the problem, to quote Halloway in "Programming Clojure". Therefore, let's document the sort order of equal-length vectors. I looked for this information on the Data Structures page, which has a section on vectors.

Comment by Alex Miller [ 15/Mar/14 11:11 PM ]

I added a line to the Vectors section on the Data Structures (http://clojure.org/data_structures) page: "Vectors are compared first by length, then each element is compared in order."





[CLJ-1078] Add queue and queue? to clojure.core Created: 26/Sep/12  Updated: 06/Feb/14

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.5
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Timothy Baldridge Assignee: Unassigned
Resolution: Unresolved Votes: 4
Labels: data-structures, queue

Attachments: File clj-1048-add-queue-functions.diff     Text File queue.patch    
Patch: Code and Test
Approval: Triaged

 Description   

Add queue function to create queues from collections and queue? predicate to check queueness.

Patch: clj-1048-add-queue-functions.diff



 Comments   
Comment by Andy Fingerhut [ 28/Sep/12 8:43 AM ]

Timothy, I tried applying both of these Sep 26, 2012 patches to latest Clojure master as of that date. I had to apply 0001-make-PersistentQueue-ctor-public.patch by hand since it failed to apply using git or patch. It built fine, but failed to pass several of the Clojure tests. Have you looked into those test failures to see if you can find the cause and fix them? I tested on Ubuntu 11.10 with Oracle JDK 1.6 and 1.7, and saw similar failures with both.

Comment by Timothy Baldridge [ 26/Oct/12 5:23 PM ]

Fixed the patch. Tests pass, created the patch, applied it to a different copy of the source and the tests still pass. So this new patch should be good to go.

Comment by Andy Fingerhut [ 26/Oct/12 5:43 PM ]

Timothy, I'm not sure how you are getting successful results when applying this patch. Can you try the steps below and see what happens for you? I get errors trying to apply the patch with latest Clojure master as of Oct 26, 2012. Also please use the steps on the JIRA workflow page to create a git format patch (http://dev.clojure.org/display/design/JIRA+workflow under "Development" heading).

% git clone git://github.com/clojure/clojure.git
% cd clojure
% patch -p1 < queues.patch
patching file src/clj/clojure/core.clj
patching file src/jvm/clojure/lang/PersistentQueue.java
Hunk #1 FAILED at 32.
1 out of 1 hunk FAILED – saving rejects to file src/jvm/clojure/lang/PersistentQueue.java.rej
patching file test/clojure/test_clojure/data_structures.clj
Hunk #1 succeeded at 123 with fuzz 2.
Hunk #2 succeeded at 861 with fuzz 2.
Hunk #3 FAILED at 872.
1 out of 3 hunks FAILED – saving rejects to file test/clojure/test_clojure/data_structures.clj.rej
patching file test/clojure/test_clojure/java_interop.clj

Comment by Timothy Baldridge [ 26/Oct/12 6:08 PM ]

I was using git apply. I tried the method you show above, and now I'm seeing the same issues you show above.

Comment by Andy Fingerhut [ 26/Oct/12 6:26 PM ]

Just so you know, the preferred way to create and apply patches are the "git format-patch master --stdout > patch.txt" to create a patch (after doing the branching commands described on the JIRA workflow page to create a branch for your changes), and the "git am --keep-cr -s < patch.txt" to apply a patch. If a patch was created that way and applies cleanly with that command, then you are definitely good to go.

The "patch -p1 < patch.txt" command is just a secondary method sometimes used to try to apply patches that aren't in the format produced above, or have errors when applying using that method.

Comment by Timothy Baldridge [ 26/Oct/12 9:15 PM ]

Just so you know, the preferred way to create and apply patches are the "git format-patch master --stdout > patch.txt" to create a patch (after doing the branching commands described on the JIRA workflow page to create a branch for your changes), and the "git am --keep-cr -s < patch.txt" to apply a patch. If a patch was created that way and applies cleanly with that command, then you are definitely good to go.

The "patch -p1 < patch.txt" command is just a secondary method sometimes used to try to apply patches that aren't in the format produced above, or have errors when applying using that method.

Comment by Timothy Baldridge [ 26/Oct/12 9:16 PM ]

added patch

Comment by Andy Fingerhut [ 26/Oct/12 9:37 PM ]

That one applies cleanly and passes all tests. It should show up on the next list of prescreened patches. Thanks.

Comment by Rich Hickey [ 29/Nov/12 9:54 AM ]

we don't use the queue* convention elsewhere, e.g. vec and vector. I think queue should take a collection like vec and set. (queue [1 2 3]) could be made to 'adopt' the collection as front.

Comment by Andy Fingerhut [ 11/Dec/12 1:00 PM ]

Patch queue.patch dated Oct 26 2012 no longer applies cleanly after recent CLJ-1000 commits, but only because of one line of changed patch context. It still applies cleanly with "patch -p1 < queue.patch". Not bothering to update the stale patch given Rich's comments suggesting more substantive changes.

Comment by Steve Miner [ 06/Apr/13 8:06 AM ]

See also CLJ-976 (tagged literal support for PersistentQueue)

Comment by John Jacobsen [ 23/May/13 8:54 PM ]

Don't want to step on Timothy B's toes here, but it looks straightforward to adopt his patch to implement Rich's suggestion. I'd offer to give it a whack if nobody else wants the ticket now.

Comment by John Jacobsen [ 26/May/13 9:04 AM ]

Discussion initiated on clojure-dev: https://groups.google.com/forum/?fromgroups#!topic/clojure-dev/2BOqHm24Vc4

Comment by John Jacobsen [ 31/May/13 9:58 AM ]

This patch (if accepted) supersedes Timothy Baldridge's patch; it implements "queue" and "queue?" (but not "queue*"); "queue" accepts a collection rather than being a variadic function, as per Rich's suggestion.

Comment by Andy Fingerhut [ 30/Jan/14 5:00 PM ]

The patch clj-1048-queue-takes-collections.diff applied cleanly to latest Clojure master as of Jan 23 2014, but not on Jan 30 2014. There were several commits made to Clojure during that week involving updating the hash functions that conflict in some way with this patch. I have not checked to see how easy or difficult it might be to update the patch.

Comment by John Jacobsen [ 05/Feb/14 1:45 PM ]

Hi Andy, I updated the patch and removed my previous version. The new one should apply cleanly and pass all tests.

Comment by John Jacobsen [ 05/Feb/14 2:24 PM ]

Updated ticket title.

Comment by Alex Miller [ 05/Feb/14 5:33 PM ]

Hi John... Can you condense these changes into a single commit? Please also remove the comments above queue* in java_interop.clj. Thanks...

Comment by John Jacobsen [ 05/Feb/14 6:55 PM ]

Hi Alex, the updated patch removes that comment and rebases all three commits into c9f77dd. Let me know if you need anything else. Thanks!





[CLJ-976] Implement reader literal and print support for PersistentQueue data structure Created: 27/Apr/12  Updated: 22/Aug/13

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.5
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Fogus Assignee: Fogus
Resolution: Unresolved Votes: 4
Labels: data-structures, queue, reader, tagged-literals

Attachments: File CLJ-976-queue-literal-eval-and-synquote.diff     Text File clj-976-queue-literal-eval-and-synquote-patch-v3.txt     File CLJ-976-queue-literal-eval.diff    
Patch: Code and Test
Approval: Triaged

 Description   

Clojure's PersistentQueue structure has been in the language for quite some time now and has found its way into a fair share of codebases. However, the creation of queues is a two step operation often of the form:

(conj clojure.lang.PersistentQueue/EMPTY :a :b :c)

;=> #<PersistentQueue clojure.lang.PersistentQueue@78d5f6bc>

A better experience might be the following:

#queue [:a :b :c]

;=> #queue [:a :b :c]

(pop #queue [:a :b :c])

;=> #queue [:b :c]

This syntax is proposed and discussed in the Clojure-dev group at https://groups.google.com/forum/?fromgroups#!topic/clojure-dev/GQqus5Wycno

Open question: Should the queue literal's arguments eval? The implications of this are illustrated below:

;; non-eval case
#queue [1 2 (+ 1 2)]

;=> #queue [1 2 (+ 1 2)]


;; eval case
#queue [1 2 (+ 1 2)]

;=> #queue [1 2 3]

The answer to this open question will determine the implementation.



 Comments   
Comment by Steve Miner [ 27/Apr/12 10:18 AM ]

I think the non-eval behavior would be consistent with the other reader literals in Clojure 1.4. It's definitely better for interop where some other language implementation could be expected to handle a few literal representations, but not the evaluation of Clojure expressions. Use a regular function if the args need evaluation.

Comment by Chas Emerick [ 27/Apr/12 10:19 AM ]

The precedent of records seems relevant:

=> (defrecord A [b])
user.A
=> #user.A[(+ 4 5)]
#user.A{:b (+ 4 5)}
=> #user.A{:b (+ 4 5)}
#user.A{:b (+ 4 5)}

This continues to make sense, as otherwise queues would need to print with an extra (quote …) form around lists — which records neatly avoid:

=> (A. '(+ 4 5))
#user.A{:b (+ 4 5)}

Does this mean that a queue fn (analogous to vector, maybe) will also make an appearance? It'd be handy for HOF usage.

Comment by Fogus [ 27/Apr/12 11:00 AM ]

Added a patch for the tagged literal support ONLY. This is only one part of the total solution. This provides the read-string and printing capability. I'd like more discussion around the eval side before I get dive into the compiler.

Comment by Paul Michael Bauer [ 27/Apr/12 6:45 PM ]

In addition to Chas' observations on consistency with record literals, would eval in queue literals open up the same security hole as #=, needing to respect *read-eval*?
When needing eval inside a queue literal, embedding a #= seems more apropos.

Comment by Fogus [ 04/May/12 1:14 PM ]

Evalable queue literal support.

Comment by Andy Fingerhut [ 10/May/12 5:54 PM ]

Neither of the patches CLJ-976-queue-literal-tagged-parse-support-only.diff dated Apr 27, 2012 nor CLJ-976-queue-literal-eval.diff dated May 4, 2012 apply cleanly to latest master as of May 10, 2012.

Comment by Fogus [ 11/May/12 10:15 AM ]

Updated patch file to merge with latest master.

Comment by Fogus [ 20/Jul/12 1:14 PM ]

New patch with support fixed for syntax-quote.

Comment by Stuart Sierra [ 17/Aug/12 12:41 PM ]

Patch does not apply as of commit f5f4faf95051f794c9bfa0315e4457b600c84cef

Comment by Fogus [ 17/Aug/12 3:06 PM ]

Weird. I was able to download the CLJ-976-queue-literal-eval-and-synquote.diff patch and apply it to HEAD as of just now (f5f4faf95051f794c9bfa0315e4457b600c84cef). There were whitespace warnings, but the patch applied, compiles and passes all tests.

Comment by Andy Fingerhut [ 17/Aug/12 7:29 PM ]

With latest head I was able to successfully apply patch CLJ-976-queue-literal-eval-and-synquote.diff with this command:

git am --keep-cr -s < CLJ-976-queue-literal-eval-and-synquote.diff

with some warnings, but successfully applied. If I try it without the --keep-cr option, the patch fails to apply. I believe this is often a sign that either one of the files being patched, or the patch itself, contains CR/LF line endings, which some of the Clojure source files definitely do.

The command above (with --keep-cr) is currently the one recommended for applying patches on page http://dev.clojure.org/display/design/JIRA+workflow in section "Screening Tickets". I added the suggested --keep-cr option after running across another patch that applied with the option, but not without it.

Comment by Andy Fingerhut [ 28/Aug/12 5:45 PM ]

Presumptuously changing Approval from Incomplete back to Test, since the latest patch does apply cleanly if --keep-cr option is used.

Comment by Rich Hickey [ 08/Sep/12 6:48 AM ]

this needs more time

Comment by Fogus [ 18/Sep/12 8:15 AM ]

Rich,

Do you mind providing a little more detail? I would be happy to make any changes if needed. However, if it's just a matter of its relationship to EDN and/or waiting until the next release then I am happy to wait. In either case, I'd like to complete this or push it to the back of my mind. Thanks.

Comment by Andy Fingerhut [ 05/Oct/12 7:49 AM ]

clj-976-queue-literal-eval-and-synquote-patch-v2.txt dated Oct 5 2012 is identical to Fogus's patch CLJ-976-queue-literal-eval-and-synquote.diff dated Jul 20 2012. It simply removes one line addition to clojure.iml that Rich has since added in a different commit, so that this patch now applies cleanly to latest master.

Comment by Andy Fingerhut [ 16/Oct/12 12:20 PM ]

clj-976-queue-literal-eval-and-synquote-patch-v3.txt dated oct 16 2012 is identical to Fogus's patch CLJ-976-queue-literal-eval-and-synquote.diff dated Jul 20 2012. It simply removes one line addition to clojure.iml that Rich has since added in a different commit, so that this patch now applies cleanly to latest master.

Comment by Andy Fingerhut [ 20/Oct/12 12:26 PM ]

Fogus, with the recent commit of a patch for CLJ-1070, my touched-up patch clj-976-queue-literal-eval-and-synquote-patch-v3.txt dated Oct 16 2012 doesn't apply cleanly. In this case it isn't simply a few lines of context that have changed, it is the interfaces that PersistentQueue implements have been changed. It might be best if you take a look at the latest code and the patch and consider how it should be updated.

Comment by Steve Miner [ 06/Apr/13 8:07 AM ]

Related to CLJ-1078.

Comment by Alex Miller [ 22/Aug/13 10:38 PM ]

Moving back to Triaged as Rich has not vetted.





Generated at Wed Jul 30 12:26:12 CDT 2014 using JIRA 4.4#649-r158309.