In an earlier post, I showed a simple loop written in several programming languages. The loop had to sum the weights of each items in a list. Dmitry pointed out a much clearer loop in Lisp using the (loop …) construct.
(loop for item in item-list sum (weight item))
I then twiddled for the better part of an hour trying to find the clearest way to do weighted random choice with Lisp (loop …). This is the best that I have come up with:
(loop
with total = (loop for item in item-list sum (weight item))
with thresh = (random total)
for item in item-list
if (minusp (decf thresh (weight item)))
return item)
with total = (loop for item in item-list sum (weight item))
with thresh = (random total)
for item in item-list
if (minusp (decf thresh (weight item)))
return item)
The biggest pedagogical obstacle in the above is the (decf …) which decrements the variable in place by the given amount and returns the new value of the variable. What I really wanted to do was this:
(loop
with total = (loop for item in item-list sum (weight item))
for item in item-list
tracking item
as thresh downfrom (random total) by (weight item))
with total = (loop for item in item-list sum (weight item))
for item in item-list
tracking item
as thresh downfrom (random total) by (weight item))
That fails on multiple fronts, however.
- There is no tracking keyword in (loop …). I can sum or maximize or collect items, but I cannot keep track of the last one that I saw. I had hoped to use the finally keyword, but its value isn’t returned from the loop.
- Lisp requires that the decrement amount in the by of a downfrom be greater than zero. As such, I have to filter out any items that have zero weight. Feh. I can do that. I would rather not. But, I can do that.
- Lisp only evaluates the by expression once. It does not evaluate it each time through the loop.
I am still learning all of the ins and outs of (loop …). Today, I learned as many outs
as ins
. Feh.
Actually, there is a better looping construct for common lisp called iterate which is extensible and lets implement `tracking’ (IIUC, it maps to iterate’s previous clase:
) and other features.
With iterate, all code can be written as
(for item in items)
(for thresh first (random total) then (- thresh (weight item)))
(finding item such-that (<= thresh 0)))
or (by realising with for from–by clause with by being reevaluated:
`(for ,var first ,start then (+ ,var ,step)))
(iter (with total = (iter (for item in items) (sum item)))
(for item in items)
(for thresh from (random total) var-by (- (weight item)))
(finding item such-that (<= thresh 0)))
I’ve never really iterate before. The first I really looked at it was debugging the sqlite_next_stmt thing the other day. I will have to explore it in more detail sometime.