Non-loop, non-mutating way to accomplish a loop in Lisp?

  • A+
Category:Languages

I wrote the following loop using local-time:

(defun count-dates (stop-date k)   (loop for step = (local-time:today)         then (local-time:timestamp- step 1 :day)         while (local-time:timestamp>= step stop-date)         collect (funcall k step))) 

It can be run simply like this:

(count-dates (local-time:encode-timestamp 0 0 0 0 1 1 2019) #'princ) 

While this was easy and straightforward, I wanted to know how to write it without the all-powerful loop construct, and came up with:

(defun count-dates2 (stop-date k)   (reverse (labels ((f (acc step)                       (if (local-time:timestamp>= step stop-date)                           (f (cons (funcall k step) acc)                              (local-time:timestamp- step 1 :day))                           acc)))              (f '() (local-time:today))))) 

This seems overly convoluted, with reverse and an accumulator. Is there an easier way to accomplish the same effect as the loop without resorting to mutation and without possibly overflowing the stack?

 


Not in Common Lisp, no: if you want an iterative construct you need to use an explicitly iterative construct: CL makes no promise that syntactically-recursive constructs are in fact iterative. loop is not the only iteration construct however, and you can of course write your own iteration & result-collection constructs.

Indeed there's no promise that your second version will not overflow the stack in CL: most current implementations will compile tail calls as iteration although may not handle this in interpreted code, but some are constrained by their targets (the JVM for instance) not to do this. There have also been major historical native-code implementations which did not (the Symbolics CL for instance).

There are Lisp-family languages which do specify in the language that tail calls are iteration, notably Scheme, & in such languages your second version would be fine.

As for the question about needing to build lists backwards & then reverse them: I think this is an inevitable consequence of the way lists work in Lisps: you can really only build up lists by adding things to the start of them if you are not happy to mutate the existing list or resort to wholesale copying for each step.

Of course you can hide the mutation of the list you are constructing behind the scenes, so that you never need to know what's going on, but that doesn't mean it's not either mutating the structure or building it backwards & then reversing. So, for instance, I have a construct which looks like:

(collecting   ...   (collect ...)   ...) 

which builds lists forwards, but it's doing this by keeping a tail pointer and mutating the list it's building.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: