Есть ли в Lisp что-то вроде функции takeWhile на Haskell?

Question

Я новичок в Common Lisp.В Haskell вы можете сделать что-то вроде этого:

Prelude> takeWhile (<= 10) [k | k <- [1..]]
[1,2,3,4,5,6,7,8,9,10]

Возможно ли это в Лиспе?Не обязательно с бесконечным списком, но с любым списком.

Answer 1

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

(setq *l1* (loop for x from 1 to 100 collect x))
(loop for x in *l1* while (<= x 10) collect x)

Если вам действительно нужна отдельная функция:

(defun take-while (pred list)
  (loop for x in list
        while (funcall pred x)
        collect x))

А вот и мы:

T1> (take-while (lambda (x) (<= x 10)) *l1*)
(1 2 3 4 5 6 7 8 9 10)

Но если мы сравним:

(loop for x in *l1* while (<= x 10) collect x)
(take-while (lambda (x) (<= x 10)) *l1*)

Думаю, я бы просто придерживался петли.

Для бесконечных последовательностей вы можете взглянуть на Series :

T1> (setq *print-length* 20)
20
T1> (setq *l1* (scan-range :from 1))
#Z(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...)
T1> (until-if (lambda (x) (> x 10)) *l1*)
#Z(1 2 3 4 5 6 7 8 9 10)

Answer 2

Библиотека CL-LAZY реализует ленивый вызов Common Lisp и предоставляет функцию take-while, которая учитывает лень. Вы можете установить его с Quicklisp и попробовать.

Answer 3

Это должно сделать ...

(defun take-while (list test)
  (and list (funcall test (car list))
       (cons (car list) (take-while (cdr list) test))))

(take-while '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15) (lambda (x) (< x 10)))
--> (1 2 3 4 5 6 7 8 9)

Однако эта "естественная" реализация не является хвостовой рекурсивной и может привести к сбою для больших списков.

Явный подход push-nreverse (aобщий шаблон) может быть

(defun take-while (list test)
  (do ((res nil))
      ((or (null list) (not (funcall test (car list))))
         (nreverse res))
    (push (car list) res)
    (setf list (cdr list))))

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

(defun take-while (list test)
  (labels ((rec (res x)
             (if (and x (funcall test (car x)))
                 (rec (cons (car x) res) (cdr x))
                 (nreverse res))))
    (rec nil list)))

Обратите внимание, что, однако, не гарантируется, что обычная реализация lisp будет обрабатывать оптимизацию хвостового вызова.

Answer 4

Некоторые языки предоставляют API списков в стиле Haskell в виде сторонних библиотек с поддержкой бесконечных потоков или без них.

Некоторые примеры:

• Последовательности Clojure: Take-while
• Scala имеет что-то

Помните, что takeWhile относительно легко реализовать в последовательности и задан в Haskell как:

takeWhile _ []          =  []
takeWhile p (x:xs)
            | p x       =  x : takeWhile p xs
            | otherwise =  []

Answer 5

Вы можете получить ленивую оценку в обычном lisp, используя замыкания (из Paul Graham's Lisp ):

(defun lazy-right-fold (comb &optional base)
  "Lazy right fold on lists."
  (labels ((rec (lst)
             (if (null lst)
                 base
                 (funcall comb
                          (car lst)
                          #'(lambda () (rec (cdr lst)))))))
    #'rec))

Затем, приём становится:

(defun take-while (pred lst)
  (lazy-right-fold #'(lambda (x f) (
                       (if (test x)
                           (cons x (funcall f))
                           (funcall f)))
                   nil))