SearchYC.com

Following up on http://arclanguage.org/item?id=8723, I've made a library, lib/iter.arc, that provides iterator utilities. Basic usage:

Iterators are constructed with 'iter, and are traversed with 'ieach.

  arc> (= i (iter 1 2 3 4 5))
  #

  arc> (ieach x i pr.x)
  12345nil

(Note that since 'iter is a macro, it can't be passed to 'apply. Use 'listiter instead.)

Mapping, filtering, etc. work as you expect:

  arc> (ieach x (ikeep odd i) pr.x)
  135nil

Unlike their cousins in mainstream languages, these iterators are immutable: they can be traversed multiple times in sequence or (theoretically) in parallel without problems. They also support all the operations that lists support. Therefore, the only difference between iterators and lists is their performance characteristics. A list consumes linear space and has the same lookup time regardless of its contents; an iterator consumes constant space but repeats whatever computation produced its contents every time it is accessed.

As an iterator undergoes transformations using 'imap, 'ikeep and so on, lookups gradually get slower. This can make reasoning about performance a little subtle. A good rule of thumb is to build sequences as far as you can with iterators, and then convert them to lists (or another concrete data structure) just before you access them. You can also use 'ifreeze, which converts an iterator to a list and then returns an iterator over that list.

If you're wondering what iterators are good for, let's take a simple factorial function:

  (def fact (n) (foldl * 1 (range 1 n)))

This is nice and clear, but not very efficient. We might be tempted to rewrite it in an imperative style:

  (def fact (n)
    (let i 1
      (for j 1 n (= i (* i j)))
      i))

This is efficient, but not very pretty.

Iterators let us combine the efficiency of the imperative version with the prettiness of the list version. All we need to do is replace 'foldl and 'range with their iterator counterparts:

  (def fact (n) (ifoldl * 1 (irange 1 n)))

Inlining the 'ifoldl and 'irange functions produces something nearly identical to the imperative code above.

For a somewhat more realistic example, let's take the problem of comparing two trees, represented as nested lists, to see if they have the same leaves in the same order. A naive solution is

  (def same-leaves (xs ys) (iso flat.xs flat.ys))

This works ok if xs and ys are mostly equal, but if they differ on, say, the first leaf, then we waste a lot of computation in 'flat.

We can solve this by making an iterator over the leaves of each tree, and then testing the iterators for equality:

  (def leaves (x) (if alist.x (imappend leaves listiter.x) iter.x))

  (def same-leaves (xs ys) (iare leaves.xs leaves.ys))

'iare compares the contents of two iterators using 'is. Unlike 'iso, it doesn't descend nested iterators. If you want different behavior, you can easily write your own comparison utility.

Sadly, Arc's call/cc, used by 'iare, seems to be so slow that the speed benefit of this example is mostly theoretical. The iterator version is only really faster when the trees have hundreds of leaves. Fortunately, the majority of utilities don't depend on call/cc.

Even more annoying (to me) is that this means o can't be a variable in a destructuring bind:

  arc> (let (x) '(blah) x)
  blah

  arc> (let (o) '(blah) o)
  Error: "cadar: expects argument of type ; given ((o))"

No: parameter lists in Arc are destructuring.

Bug:

  (def other (side) (case side 'l 'r 'r 'l))

should be

  (def other (side) (case side l 'r r 'l))

This was causing bst-rem to behave incorrectly when removing a node with two children.

I guess I should clarify this a bit. In other languages (e.g. OCaml), it's conventional for each data structure to provide an iterator and a fold/reduce function. In Arc, the convention seems to be to provide iterators but not folds. The above code shows that it's sufficient only to have iterators, and a left fold can be automatically derived.

Alternatively, we could have data structures provide a left fold and automatically derive an iterator:

  (def giter (fold)
    (fn (f xs)
      (fold (fn (y . args) (apply f args) nil) xs nil)))

Thus, (giter:greduce f) == f, and (greduce:giter g) == g.

I translated into Arc a little program I wrote a few months ago to compare the distribution of characters in Qwerty vs. Dvorak by hands, fingers, etc. It currently outputs text; the next step of course is to output HTML.

http://benstoker.com/code/lytcmp.arc

http://benstoker.com/code/lcex.txt

Getting the program to work was a bitch as there doesn't seem to be any debugging support at all. Nevertheless, I'm extremely pleased with the language itself.

The utility at the beginning reflects the only serious issue I ran into: objs don't seem to be able refer to themselves. I had to write a new obj macro that binds the current object to 'this'.

Also, although it's not a serious problem, I'd love to be able to refer to obj fields with a simpler syntax, e.g. x.foo instead of (x 'foo). In particular, that quote before the field name is kind of a wart.

  (n-of n (readb stream))

You've reinvented reduce.

  (reduce (fn (y x) (if odd.x x y)) xs nil)

  (reduce (fn (y x) (if (and odd.x (or no.y (> x y))) x y)) xs nil)

Probably because it's incorrect. You should have (edits1 e) at the end there.