Arc Forum | The first assignment has no confusion.I think insort should modify the list, not...

Arc Forum

new | comments | leaders | submit

2 points by dram 3989 days ago | link | parent

The first assignment has no confusion.

I think insort should modify the list, not merely assign a new list.

Some demo code:

  (def insort1 (test elt seq)
    (if (no seq)
         (list elt)
        (test elt (car seq))
         (with (first (car seq) rest (cdr seq))
          (scar seq elt)
          (scdr seq (cons first rest)))
        (no (cdr seq))
          (scdr seq (list elt))
        (insort1 test elt (cdr seq))))
  
  (mac insort (test elt seq)
    `(do (insort1 ,test ,elt ,seq) ,seq))

3 points by fallintothis 3988 days ago | link

Your version doesn't quite work as-is:

  arc> (= y (= x '(1 3 5)))
  (1 3 5)
  arc> (insort < 2 x)
  (1 2 3 5)
  arc> x
  (1 2 3 5)
  arc> y
  (1 2 3 5)
  arc> (insort < 0 x)
  (0 1 2 3 5)
  arc> x
  (0 1 2 3 5)
  arc> y
  (0 1 2 3 5)
  arc> (insort < 6 x)
  (0 1 2 3 5 6)
  arc> x
  (0 1 2 3 5 6)
  arc> y
  (0 1 2 3 5 6)
  arc> (= y (= x nil))
  nil
  arc> (insort < 1 x)
  nil
  arc> x
  nil
  arc> y
  nil

Here's a version I wrote for my own edification (basically, a more complicated version of yours):

  (def destructive-cons (elt seq)
    ; Note: (push elt seq) won't work, because push is a macro on the "place",
    ; and seq isn't the proper "place" to mutate (push will just mutate the local
    ; binding of seq).  This function will actually mutate the cons cell being
    ; pointed at by seq.
    (let (first . rest) seq
      (scar seq elt)
      (scdr seq (cons first rest)))
    seq)

  (def insorter (test elt seq)
    (if (no seq)
         (list elt)
        (test elt (car seq))
         (destructive-cons elt seq)
        (do1 seq
             ((afn (prev cell)
                (if (or (no cell) (test elt (car cell)))
                    (scdr prev (cons elt cell))
                    (self cell (cdr cell))))
              seq (cdr seq)))))

  (mac insorted (test elt seq)
    `(zap [insorter ,test ,elt _] ,seq))

Writing it made me realize the issues with making a "truly destructive" insort:

  arc> (= y (= x '(1 3 5)))
  (1 3 5)
  arc> (insorted < 2 x)
  (1 2 3 5)
  arc> x
  (1 2 3 5)
  arc> y
  (1 2 3 5)
  arc> (insorted < 0 x)
  (0 1 2 3 5)
  arc> x
  (0 1 2 3 5)
  arc> y
  (0 1 2 3 5)
  arc> (insorted < 6 x)
  (0 1 2 3 5 6)
  arc> x
  (0 1 2 3 5 6)
  arc> y
  (0 1 2 3 5 6)
  arc> (= y (= x nil))
  nil
  arc> (insorted < 1 x)
  (1)
  arc> x
  (1)
  arc> y
  nil

No matter how you try, there's still the edge case with nil, on which you can't scar/scdr.

  arc> (= x nil)
  nil
  arc> (scar x 1)
  Error: "set-car!: expected argument of type <pair>; given nil"
  arc> (scdr x '(2))
  Error: "set-cdr!: expected argument of type <pair>; given nil"

So it appears Arc's model of "places" can't really handle references/aliases that well. Indeed, push, swap, rotate, pop, pushnew, pull, togglemem, and the like are "broken", too, if we expect them to modify the _content_ of their arguments instead of simply where the arguments point. E.g.,

  arc> (= y (= x '(a b c)))
  (a b c)
  arc> (= z (= w '(1 2 3)))
  (1 2 3)
  arc> (swap x w)
  (a b c)
  arc> x
  (1 2 3)
  arc> y
  (a b c)
  arc> z
  (1 2 3)
  arc> w
  (a b c)

In a way, I can see that being the right behavior for swap, but not for insort. I suppose it's at least somewhat consistent: just alter your expectations of "destructive" operators, since they'll all (near as I can tell) just modify where their input "places" are pointing. Not that I'm ready to write off the issue that way, it's just I don't have a solution and think it gets complicated depending on the operators in question. :)

-----

2 points by dram 3988 days ago | link

Good catch.

About the nil problem, maybe we should nil terminate list this way: (1 2 nil), instead of (1 2 . nil). just a joke. :)

Anyway, mutable pair is just a mess, I feel I have some understanding why Racket get rid of set-car! and set-cdr!.

-----

1 point by akkartik 3988 days ago | link

"..just alter your expectations of destructive operators.."

Yeah, I agree with this. I weakly think (without evidence) that arc's destructive ops are more functional, and it encourages a better style to not constantly make assumptions about precisely which cons cells go where.

On the other hand, a set of 'alias-friendly' functions could coexist with the existing primitives.

Hmm, I wonder if the notion of boxes would help build alias-friendly operations.

-----