Does Lisp have something like Haskell's takeWhile function?

Question

I'm new to Common Lisp. In Haskell, you can do a little something like this:

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

Is this possible in Lisp? Not necessarily with an infinite list, but with any list.

Agglutinogen

Answer 1

You could use LOOP:

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

If you really need it as a separate function:

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

And here we are:

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

But if we compare:

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

I think I would just stick with loop.

For infinite sequences, you could take a look at 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)

Condone

Answer 2

This should do...

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

However this "natural" implementation is not tail-recursive and could crash for big lists.

An explicit push-nreverse approach (a common pattern) could be

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

A recursive (but tail-recursive, therefore probably ok with most CL implementations) could IMO be the following:

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

Note that however it's not guaranteed that a common lisp implementation will handle tail-call optimizations.

Polished

Not a good idea. It is not even tail recursive. It will blow out the stack on any longer list... – Cherie

Thanks for accepting, but note that probably danlei answers is better... this is not even tail-recursive – Polished

@rainer joswig: I agree that loop is better – Polished

Reaccepted. It solved my immediate problem, but I see your point. – Agglutinogen

Answer 3

The CL-LAZY library implements lazy calling for Common Lisp and provides a take-while function that is laziness aware. You can install it with Quicklisp and try it out.

Chloric

Answer 4

Some languages provide a Haskell-style list API as 3rd party libraries, with or without support for infinite streams.

Some examples:

• Clojure's sequences: take-while
• Scala has something

Remember that takeWhile is relatively easy to implement over a sequence, and is given in Haskell as:

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

Toffee

While it doesn't nail down my direct question, this answer is very insightful. Thanks! – Agglutinogen

Answer 5

You can have a lazy evaluation in common lisp using closures (from Paul Graham's On 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))

Then, take-while becomes:

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

Woodall