Arc Forum | Of course, because Arc uses linked lists, this is actually considerably slower t...

Arc Forum

2 points by fallintothis 5143 days ago | link | parent

Of course, because Arc uses linked lists, this is actually considerably slower than linear iteration through the list, because every list access is multiplied by O(n).

True that. ;)

An interesting exercise nonetheless.

To this end, here are a few Arc tricks.

- Instead of

  (is (len stack) 1)

you can use

  (single stack)

which is defined as

  (def single (x) (and (acons x) (no (cdr x))))

I.e., a linked list has length 1 if it doesn't have a cdr. This makes (single stack) read nicely, but we already know stack is a linked list, so we could also just say

  (~cdr stack) ; == (no:cdr stack) == (no (cdr stack))

- Instead of

  (is needle (car stack))

you could say

  (caris stack needle)

which reads a little nicer, though the definition once more has an acons check:

  (def caris (x val) 
    (and (acons x) (is (car x) val)))

- Notice that the pattern

  (if a b nil)

is the same as

  (and a b)

which potentially reads more clearly:

  (def bsearch (stack needle (o f <)  (o offset 0))
    (if (single stack)
        (and (caris stack needle)
             offset)
        (let (fst lst) (split stack (round (/ (len stack) 2)))
          (if (f (last fst) needle)
              (bsearch lst needle f (+ offset (len fst)))
              (bsearch fst needle f offset)))))

- Since "offset is used internally to keep where we are in the whole list", we could make the parameter internal to an anonymous function, then call that function on the "external" arguments. Using afn (anaphoric fn; http://en.wikipedia.org/wiki/Anaphora_%28linguistics%29), we can recurse in the anonymous function using the name self. This winds up being simple, but kind of ugly.

  (def bsearch (stack needle (o f <))
    ((afn (stack offset)
       (if (single stack)
           (and (caris stack needle)
                offset)
           (let (fst lst) (split stack (round (/ (len stack) 2)))
             (if (f (last fst) needle)
                 (self lst (+ offset (len fst)))
                 (self fst offset)))))
     stack 0))

We wind up needing to supply the initial arguments to afn all the way at the bottom, wrapping the whole thing in another set of parentheses for the call. This prompted utlities like http://arclanguage.org/item?id=10055.

1 point by zck 5142 days ago | link

>- Notice that the pattern

  (if a b nil)

>is the same as

  (and a b)

For this, I prefer

  (when a b)

>This makes `(single stack)` read nicely, but we already know stack is a linked list, so we could also just say

  (~cdr stack) ; == (no:cdr stack) == (no (cdr stack))

I wouldn't want to go to this optimization until finding out that it would significantly increase performance, but that argument hinges on thinking it's slightly less readable than `(single stack)`.

-----

3 points by shader 5142 days ago | link

Note that you don't need the nil at the end of the if, so

  (if a b)

also works.

-----

1 point by dpkendal 5142 days ago | link

Either of these are neater than using `and`, which for clarity is better only used as a predicate, in my opinion.

Thanks fallintothis, zck, and shader for your improvements. I'm trying to take everyone's suggestions into account to make a new version, which I'll put in Anarki when I'm satisfied with it.

-----