Выполняет функцию, пока не возвращает ноль, собирая ее значения в список - PullRequest
Новая
       51

Выполняет функцию, пока не возвращает ноль, собирая ее значения в список

9 голосов
/ 28 июня 2011

Я получил эту идею от комикса Хофстадтера XKCD ; Каков наилучший способ создания условного цикла в (любом) диалекте Лисп, который выполняет функцию до тех пор, пока не вернет NIL, и тогда он соберет возвращенные значения в список.

Для тех, кто не видел шутку, получается, что автобиография Дугласа Хофштадтера «из восьми слов» состоит всего из шести слов: «Я такой мета, даже эта аббревиатура», содержащая продолжение шутки: meta-paraprosdokian?) «Is Meta» - шутка в том, что автобиография - это «Me So Meta, даже эта аббревиатура Meta». Но почему бы не пойти глубже?

Предположим, что функция сокращения META создает аббревиатуру из строки и разбивает ее на слова, возвращает NIL, если строка содержит только одно слово: 

(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

Теперь я ищу, как реализовать функцию, чтобы: 

(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")

Какой лучший способ сделать это?

Ответы [ 2 ]

3 голосов
/ 28 июня 2011

Это легко. Я не хочу писать решение, поэтому вместо этого я сделаю - но это будет дрянная версия elisp, которая может привести к неожиданному просветлению, если вы выполните: 

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

Чтобы попробовать это, вам понадобится meta, но я не знаю, как вы решите, где поставить пробелы, поэтому вместо этого я подделаю: 

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

Это делает код, который вы хотите работать. Что касается просветления - попробуйте написать его так, чтобы вместо того, что вы хотите, so-function будет функцией более высокого порядка - той, которая будет работать так: 

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

или, на схеме: 

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

Большой намек здесь заключается в том, что вы не можете сделать это обычным образом (по крайней мере, без трюков из библиотеки cl). Чтобы получить полную оценку, избегайте мутаций - это приведет к тому, что вы напишите это в Scheme естественным образом, и даже может выглядеть более читабельным, чем версия setq.

1 голос
/ 28 июня 2011

Скинул это вместе, и, похоже, это сработало: 

(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)))))

Используя слегка измененную версию meta Eli Barzilay, 

(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

Я получил результат, которым вы былиищу. 

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")

Редактировать : @Rainer Joswig указал, что collect-until-null исчерпает стек, если дан достаточно большой последовательности.Ниже приведена итерационная версия Райнера без этой проблемы. 

(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))
...