Clojure: Sets, order and purity

Question

Is (vec #{1 2 3}) guaranteed to always return [1 3 2] or could the order be different?

I am not so much interested in the implementation details behind this but going from unordered to ordered in general in order to keep my functions pure and easily testable.

Answer 1

As mentioned, standard #{} sets (both PersistentArrayMap and PersistentHashMap; depending on the size) are considered unordered.

Regarding purity with respect to calling seq on a set though, the current implementation does seem to return a well-defined, consistent order; just not an easily predictable one:

(let [r (range 1000)

      seqs (repeatedly 1000 #(seq (add-randomly #{} r)))]

  ; See how many different orders were produced
  (println (count (set seqs)))

  (println (first seqs)))

1
(0 893 920 558 453 584 487 637 972 519 357 716 950 275 530 929 789 389 586 410 433 765 521 451 291 443 798 779 970 249 638 299 121 734 287 65 702 70 949 218 648 812 62 74 774 475 497 580 891 164 282 769 799 273 186 430 641 529 898 370 834 233 298 188 240 110 130 982 620 311 931 882 128 399 989 377 468 259 210 229 153 621 213 670 977 343 958 887 472 7 894 59 934 473 86 756 830 613 491 154 20 224 355 592 610 806 571 466 72 454 888 463 851 770 814 859 58 964 980 205 555 552 60 835 459 175 322 510 662 27 352 493 899 416 777 694 1 631 854 69 101 24 901 547 102 788 713 385 988 135 397 773 490 752 354 884 360 998 961 55 568 797 688 763 269 676 448 527 206 966 165 715 387 652 683 85 721 862 615 681 225 865 297 39 805 274 88 217 46 682 508 149 415 239 478 878 157 345 300 743 921 4 550 204 470 646 77 106 197 405 897 726 776 940 755 902 518 232 260 823 267 119 319 534 222 603 293 95 450 329 144 504 819 818 505 723 992 176 863 471 349 512 710 192 54 92 221 141 502 871 464 801 307 935 758 290 627 517 361 264 137 356 728 976 678 327 234 856 817 104 353 15 48 945 759 242 832 969 50 956 917 557 251 394 116 585 583 75 437 516 994 930 967 687 159 848 995 709 99 540 645 749 479 890 630 916 815 281 402 669 781 740 975 429 309 458 21 388 495 952 626 875 31 113 32 811 827 407 398 136 691 847 825 139 506 396 460 483 589 581 932 174 578 855 331 363 284 208 305 955 796 708 182 256 657 514 731 619 985 485 214 193 685 804 869 836 785 635 442 561 954 656 607 241 314 782 226 235 672 420 418 262 263 304 401 673 40 129 600 729 467 445 317 294 91 810 364 987 880 515 412 553 974 341 117 665 523 172 601 108 156 358 308 908 649 531 923 223 419 365 944 181 417 979 278 56 942 33 13 867 22 618 380 257 338 500 909 993 168 833 496 947 347 501 596 872 792 90 237 826 292 109 216 191 498 829 761 375 525 367 143 742 178 640 247 328 391 990 167 707 36 41 474 187 551 996 528 971 599 376 195 889 316 668 428 303 671 794 905 368 560 565 310 366 118 522 150 886 313 384 567 238 846 962 845 196 162 393 184 219 999 461 89 100 426 604 477 844 541 351 243 131 790 963 629 873 122 933 43 231 61 654 883 598 413 29 784 800 151 369 348 575 693 44 739 258 250 674 539 301 838 424 93 6 684 951 573 408 563 850 616 866 111 997 689 28 456 374 608 737 548 538 895 411 957 134 943 64 623 465 816 334 323 189 280 198 155 295 808 248 587 285 507 227 724 476 941 911 853 494 220 842 103 697 611 170 51 25 261 768 822 201 904 590 489 778 166 447 34 252 978 775 325 594 436 828 535 813 146 741 876 228 907 306 125 276 340 148 482 622 588 17 312 606 3 520 760 720 286 279 879 536 663 12 440 332 330 382 152 544 803 642 435 342 703 783 695 973 2 948 66 484 439 236 556 373 142 359 727 371 772 444 570 757 107 532 984 23 745 719 230 625 47 526 180 786 870 537 659 158 991 350 35 849 644 881 127 927 675 383 533 910 302 564 701 566 821 787 82 76 735 492 718 771 215 97 704 277 926 751 19 335 597 938 57 609 202 68 452 200 868 11 115 946 983 339 431 462 337 698 255 503 546 9 953 857 706 632 457 427 145 5 733 624 831 244 918 824 289 112 925 730 699 712 414 839 802 860 179 344 481 732 661 245 378 913 906 658 266 324 793 680 446 524 254 404 617 283 513 572 705 959 83 634 138 346 14 455 265 449 333 650 639 569 326 746 647 45 53 559 78 924 562 542 912 664 315 914 480 132 753 900 26 766 123 203 667 392 577 807 140 321 795 441 700 268 840 16 320 133 288 381 605 163 81 120 643 79 211 38 173 126 981 421 593 636 98 422 423 614 762 582 666 554 409 574 595 124 747 171 87 169 653 679 843 160 30 400 767 896 928 696 738 809 509 736 207 874 434 690 194 511 73 486 336 96 837 937 10 660 272 499 488 903 386 270 576 717 543 271 18 395 403 469 105 185 52 545 633 114 968 253 612 628 748 209 147 655 750 852 425 864 67 296 602 318 161 651 725 372 406 438 780 711 71 939 579 877 722 42 919 80 885 986 714 677 199 841 754 791 861 591 744 960 37 183 965 892 432 379 63 212 94 362 8 686 692 764 246 190 549 922 177 915 936 820 49 858 390 84)

So yes, it seems that within a single run of a program, the order of (seq #{1 2 3}) can be relied upon, and can be considered pure. The language gives no guarantees though, and this property may not always exist, so really, I wouldn't rely on it. It's an implementation detail.

If you require a consistent ordering, it may be beneficial to have a vector along with the set to define the order. You could do something like:

(def pair [#{} []])

(defn add [p n]
  (-> p
      (update 0 conj n)
      (update 1 conj n)))

(-> pair
    (add 1)
    (add 2))

=> [#{1 2} [1 2]]

Reference the set when you want to do a membership test, and the vector when you need order. Of course, this requires twice as much memory as it otherwise would though, so this may not always be practical. Additions to both sets and vectors are essentially constant however, so additions will still be quick.