Executes a function until it returns a nil, collecting its values into a list

Question

I got this idea from XKCD's Hofstadter comic; what's the best way to create a conditional loop in (any) Lisp dialect that executes a function until it returns NIL at which time it collects the returned values into a list.

For those who haven't seen the joke, it's goes that Douglas Hofstadter's “eight-word” autobiography consists of only six words: “I'm So Meta, Even This Acronym” containing continuation of the joke: (some odd meta-paraprosdokian?) “Is Meta” — the joke being that the autobiography is actually “I'm So Meta, Even This Acronym Is Meta”. But why not go deeper?

Assume the acronymizing function META that creates an acronym from a string and splits it into words, returns NIL if the string contains but one word:

(meta "I'm So Meta, Even This Acronym") ⇒ "Is Meta"
(meta (meta "I'm So Meta, Even This Acronym")) ⇒ "Im"
(meta (meta (meta "I'm So Meta, Even This Acronym"))) ⇒ NIL

(meta "GNU is Not UNIX") ⇒ "GNU"
(meta (meta "GNU is Not UNIX")) ⇒ NIL

Now I'm looking for how to implement a function so that:

(so-function #'meta "I'm So Meta, Even This Acronym") 
⇒ ("I'm So Meta, Even This Acronym" "Is Meta" "Im")
(so-function #'meta "GNU is Not Unix")
⇒ ("GNU is Not Unix" "GNU")

What's the best way of doing this?

Answer 1

This is easy. I don't want to write a solution, so instead I will -- but it'll be the crappy elisp version, which might lead to unexpected enlightenment if you'll follow through:

(defun so-function (f str)
  (let (x '())
    (while str (setq x (cons str x)) (setq str (funcall f str)))
    (reverse x)))

To try this out you'll need that meta, but I don't know how you'd decide where to put the spaces, so instead I'll fake it:

(defun meta (x)
  (cadr (assoc x '(("I'm So Meta, Even This Acronym" "Is Meta")
                   ("Is Meta" "Im")
                   ("GNU is Not UNIX" "GNU")))))

This makes the code that you want work. As for the enlightenment -- try to write it so instead of what you want, so-function will be a higher order function -- one that will work like this:

(funcall (so-function #'meta) "GNU is Not UNIX")

or, in Scheme:

((so-function meta) "GNU is Not UNIX")

The big hint here is that you can't do it in plain elisp (at least not without tricks from the cl library). To get full credit, avoid the mutations -- this will lead to the natural way you'd write it in Scheme, and might even look more readable than the setq version.

Answer 2

Threw this together and it seems to work:

(defun collect-until-null (function initial-value)
  "Collects INITIAL-VALUE and the results of repeatedly applying FUNCTION to
   INITIAL-VALUE into a list.  When the result is NIL, iteration stops."
  (if initial-value
      (cons initial-value
            (collect-until-null function (funcall function initial-value)))))

Using a slightly modified version of the meta Eli Barzilay posted,

(defun meta (x)
  (cadr (assoc x
               '(("I'm So Meta, Even This Acronym" "Is Meta")
                 ("Is Meta" "Im")
                 ("GNU is Not UNIX" "GNU"))
               :test #'equal))) ;strings with the same characters aren't EQL

I get the result you were looking for.

CL-USER> (collect-until-null #'meta "I'm So Meta, Even This Acronym")
("I'm So Meta, Even This Acronym" "Is Meta" "Im")

CL-USER> (collect-until-null #'meta "GNU is Not UNIX")
("GNU is Not UNIX" "GNU")

---

Edit: @Rainer Joswig pointed out that collect-until-null will exhaust the stack if given a sufficiently large sequence. Below is Rainer's iterative version without this problem.

(defun collect-until-null-iter (function initial-value)
  "Collects INITIAL-VALUE and the results of repeatedly applying FUNCTION to
   INITIAL-VALUE into a list.  When the result is NIL, iteration stops."
  (loop for result = initial-value then (funcall function result)
        while result collect result))