<< Back to previous view

[MCOMB-8] Better support for sets Created: 12/Mar/17  Updated: 27/May/17

Status: Open
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Greg Chapman Assignee: Mark Engelberg
Resolution: Unresolved Votes: 0
Labels: None


It seems reasonable to want to use a clojure set as the items parameter for the combinatoric functions. However, in the case of (combinations some-set 1), an exception is raised because Clojure's distinct function (called when (= t 1)) does not support sets. This problem can be worked around by converting the set to a seq before calling combinations.

For all the other functions, it appears extending all-different? with a set? check would make the functions slightly more efficient (by avoiding the linear distinct? scan).

Comment by Greg Chapman [ 12/Mar/17 2:12 PM ]

I looked a little further: it looks like nth-permutation-distinct will call nth on its l parameter. Sets do not support nth, so better set support would require a change to that function.

Comment by Mark Engelberg [ 13/Mar/17 4:13 AM ]

See discussion here: https://groups.google.com/forum/#!topic/clojure/XUEqdCSI6c4

I don't think it necessarily makes sense for sets to be valid inputs. What these algorithms return is highly dependent on the order of elements in the seq. Since sets are unordered, such a change would make it so that these are not pure functions, i.e., they could return completely different outputs for the same (equal) inputs. That's because two sets that compare as equal may return a different ordering of elements when applying seq. This could wreak havoc with people's test cases in their functions which call these with sets, etc.

I think it is better for the user to be forced to apply seq directly rather than have it happen implicitly, so he/she can think about the consequences, and maybe do a sort of the seq or something to ensure a consistent output, if desired.

Comment by Nathan Irwin Smutz [ 17/Mar/17 4:46 PM ]

Fix or no fix, the least that needs to happen is an edit to the docstring.

As it is, combinations is going to work just fine until the size-1 corner-case hits. Hidden land-mines like this need some kind of fix.
Forcing action on ordering issues would entail throwing an exception, popping a warning, or making functions error on sets consistently.

Comment by Mark Engelberg [ 17/Mar/17 5:08 PM ]

I agree that the current behavior is unfriendly. Possible solutions are:

1) Implicitly call seq on all inputs (disadvantage: no longer pure functions)
2) Throw errors on sets (disadvantage: adds runtime check)
3) Add info to docstring that inputs must be a sequential (disadvantage: need to read docstring to understand constraint, does everyone know what a "sequential" means, and that sets and maps do not qualify?)
4) Add discussion on this point to README (disdavantage: does anyone read the README?)

I'd lean towards 3 or 4. I'm happy to make a change along those lines.

Comment by Nathan Irwin Smutz [ 18/Mar/17 4:52 PM ]

Thinking about #1, for anything but size-1 combinations, the behavior wouldn't be any less pure than it is now. It would also have the exact same purity as seq, vec, map or any other order-preserving function. (map inc some-set) has the same caveat for order. Since the issue of equality on order-hiding data-structures and order-preserving (revealing?) functions is a lot bigger than combinatorics functions, a suitable equality-warning really belongs with order-hiding objects themselves.

Thinking about the discussion on the mailing list, one of the reasons people use sets is to deliberately ignore order. I think the best advice would be to convert sequences back to sets before testing. (set (map inc some-set))

I think if we wouldn't leave map broken on sets, it's worth fixing here.

Comment by Nathan Irwin Smutz [ 18/Mar/17 5:13 PM ]

I see some of the issue with combinations. Mathematical combinations are order-agnostic; but these are lists. For equality-testing you'd use: (set (map set (combinations some-set n)))

Comment by Mark Engelberg [ 27/May/17 2:58 AM ]

For the time being, I've added a note to the top of the usage notes in the README. The only thing that really breaks down for sets is the call to `distinct`, so if Clojure ever modifies the code for `distinct` so that it works on sets (which seems like it would be a trivial change), then this note can be removed.

[MCOMB-6] Support ClojureScript by converting from CLJ to CLJC Created: 18/Mar/16  Updated: 18/Mar/16

Status: Open
Project: math.combinatorics
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Eric Lavigne Assignee: Mark Engelberg
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File combinatorics-cljc.patch    
Patch: Code


Patch attached with two changes:
1) Rename main source file to change extension from .clj to .cljc.
2) Add Clojure 1.7 dependency to pom.xml.

Ran "mvn clojure:test" and confirmed that old tests still pass.

Did not test in ClojureScript environment.

Main downside is increasing the minimum Clojure version from 1.2 to 1.7 for CLJC support. Alex Miller also indicated that the Clojure CI system was not ready for CLJC files yet, but that it would be nice to have the ticket and patch ready.

See previous clojure-dev discussion: https://groups.google.com/forum/#!topic/clojure-dev/PDyOklDEv7Y

Generated at Mon Jul 24 01:45:53 CDT 2017 using JIRA 4.4#649-r158309.