| 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))
#<procedure: i>
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. |
