Не-цикличный, не мутирующий способ выполнить цикл в Лиспе? - PullRequest
Новая
       10

Не-цикличный, не мутирующий способ выполнить цикл в Лиспе?

0 голосов
/ 19 февраля 2019

Я написал следующий цикл, используя 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)))

Это можно запустить просто так: 

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

Хотя это было легко иЯ просто хотел узнать, как написать это без всесильной конструкции loop, и придумал: 

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

Это кажется слишком запутанным, с reverse и аккумулятором.Есть ли более простой способ добиться того же эффекта, что и цикл, не прибегая к мутации и, возможно, не переполняя стек?

Ответы [ 3 ]

0 голосов
/ 19 февраля 2019

Вы можете избавиться от одного уровня отступа, введя вызов reverse внутрь.Также обратите внимание, что имя count-dates не очень хорошо, так как человек не считает даты, а отображает функцию с шагом в один день с сегодняшнего дня до stop-date. 

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

Другая конструкция итерации:старый DO: 

(defun count-dates (stop-date k &aux result)
  (do ((step
        (local-time:today)
        (local-time:timestamp- step 1 :day)))

      ((not (local-time:timestamp>= step stop-date))
       (reverse result))

    (push (funcall k step) result)))

Но это не лучше, чем LOOP.

Итерационная конструкция, которая не является стандартной, но такой же мощной, как LOOP и эстетически немного лучше ITERATE .

0 голосов
/ 19 февраля 2019

Вы также можете использовать пакет SERIES : 

(defpackage :so (:use :cl :series :local-time))
(in-package :so)

(let ((stop-date (timestamp- (today) 10 :day)))
  (scan-fn  ;; type of elements (could be T here)
            'timestamp
            ;; init function
            (lambda () (today))
            ;; step function
            (lambda (ts) (timestamp- ts 1 :day))
            ;; termination test
            (lambda (ts) (not (timestamp>= ts stop-date)))))

Вышеприведенный пример возвращает экземпляр объекта серии, представляющий собой ленивый (по запросу) поток значений, скомпилированныйэффективно.В REPL это отображается как #Z(...) (где точки являются элементами).Если вы хотите преобразовать его в список, вы можете позвонить collect: 

(collect *) ;; assuming * is the last returned value

Если вы хотите вместо него вектор: 

(collect 'vector **)

Что дает: 

#(@2019-02-19T01:00:00.000000+01:00 @2019-02-18T01:00:00.000000+01:00
  @2019-02-17T01:00:00.000000+01:00 @2019-02-16T01:00:00.000000+01:00
  @2019-02-15T01:00:00.000000+01:00 @2019-02-14T01:00:00.000000+01:00
  @2019-02-13T01:00:00.000000+01:00 @2019-02-12T01:00:00.000000+01:00
  @2019-02-11T01:00:00.000000+01:00 @2019-02-10T01:00:00.000000+01:00
  @2019-02-09T01:00:00.000000+01:00)

Также обратите внимание, что в случае, если collect лексически заключает в себе функцию scan-fn, он может напрямую выражать код в виде цикла.Например: 

(let ((stop-date (timestamp- (today) 10 :day)))
  (collect
      (scan-fn  ;; type of elements (could be T here)
       'timestamp
       ;; init function
       (lambda () (today))
       ;; step function
       (lambda (ts) (timestamp- ts 1 :day))
       ;; termination test
       (lambda (ts) (not (timestamp>= ts stop-date))))))

Форма collect расширена макросом как: 

(LET* (#:STATE-1062 #:ITEMS-1063 (#:LASTCONS-1060 (LIST NIL)) #:LST-1061)
  (DECLARE (TYPE CONS #:LASTCONS-1060)
           (TYPE LIST #:LST-1061))
  (LOCALLY
   (DECLARE (TYPE TIMESTAMP #:STATE-1062)
            (TYPE TIMESTAMP #:ITEMS-1063))
   (SETQ #:STATE-1062 ((LAMBDA () (TODAY))))
   (SETQ #:LST-1061 #:LASTCONS-1060)
   (TAGBODY
    #:LL-1064
     (IF ((LAMBDA (TS) (NOT (TIMESTAMP>= TS STOP-DATE))) #:STATE-1062)
         (GO SERIES::END))
     (SETQ #:ITEMS-1063 #:STATE-1062)
     (SETQ #:STATE-1062 ((LAMBDA (TS) (TIMESTAMP- TS 1 :DAY)) #:STATE-1062))
     (SETQ #:LASTCONS-1060
             (SETF (CDR #:LASTCONS-1060) (CONS #:ITEMS-1063 NIL)))
     (GO #:LL-1064)
    SERIES::END)
   (CDR #:LST-1061)))

Как упоминает Evhince, в кулинарной книге Common Lisp есть раздел о серии, см. https://lispcookbook.github.io/cl-cookbook/iteration.html

0 голосов
/ 19 февраля 2019

Нет в Common Lisp, нет: если вы хотите итеративную конструкцию, вам нужно использовать явно итеративную конструкцию: CL не обещает, что синтаксически-рекурсивные конструкции на самом деле итеративны.loop не единственная конструкция итерации, однако, и вы, конечно, можете написать свои собственные конструкции итерации и сбора результатов.

Действительно, нет никаких обещаний, что ваша вторая версия не будет переполнять стек в CL: большинство текущихРеализации будут компилировать хвостовые вызовы как итерацию, хотя могут и не обрабатывать это в интерпретируемом коде, но некоторые ограничены своими целями (например, JVM), чтобы они этого не делали.Существовали также основные исторические реализации нативного кода, которые этого не делали (например, Symbolics CL).

Существуют языки семейства Lisp, которые определяют в языке, что хвостовые вызовы являются итерацией, в частности Scheme, и вс такими языками ваша вторая версия будет в порядке.

Что касается вопроса о необходимости построения списков в обратном направлении, а затем наоборот: я думаю, что это неизбежное следствие того, как списки работают в Лиспсе: вы действительно можете собрать тольковсплывающих списков, добавляя их в начало, если вы не хотите изменять существующий список или прибегать к массовому копированию для каждого шага.

Конечно, вы можете скрыть мутацию списка, который вы создаете, засцены, так что вам никогда не нужно знать, что происходит, но это не значит, что это не является ни мутированием структуры, ни построением ее в обратном направлении, а затем наоборот.Так, например, у меня есть конструкция, которая выглядит следующим образом: 

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

, которая строит списки вперед, но делает это, сохраняя указатель хвоста и изменяя список, который строит.

...