Topic: Divide List

[Lee Mac]

Is there a quick way to split a list into two lists such that all the elements in the first satisfy a certain criteria (or predicate function) and the second list contains all the elements that fail this criteria.

Obviously there are the functions vl-remove-if and vl-remove-if-not, but this means using these one after the other on the same list, and is quite repetitive. So I wondered if there was a function to perform this task in one operation.

As an example to clarify my intentions:

Before:

Code: [Select]

(1 2 3 4 5 6 7 8 9)
Test Function:

Code: [Select]

(zerop (rem x 3))
Return:

Code: [Select]

((3 6 9) (1 2 4 5 7 8))

Thanks,

Lee

[CAB]

Code: [Select]

(mapcar '(lambda(x)
           (if (zerop (rem x 3))
             (setq l1 (cons x l1))
             (setq l2 (cons x l2))))
        '(1 2 3 4 5 6 7 8 9))

[Lee Mac]

Nice solution CAB - can't believe I hadn't thought of something like that 

[CAB]

There will be days like that. 
Tomorrow may be mine. 

[Joe Burke]

I think foreach would be more approrpriate in this case.

[Lee Mac]

I think foreach would be more approrpriate in this case.

Good Suggestion - I always miss the simple option.   

[gile]

Hi,

Someyhing like this ?

Code: [Select]

(defun divideList (lst fun / l1 l2)
  (foreach ele (reverse lst)
    (if ((eval fun) ele)
      (setq l1 (cons ele l1))
      (setq l2 (cons ele l2))
    )
  )
  (list l1 l2)
)
(divideList '(1 2 3 4 5 6 7 8 9) '(lambda (x) (zerop (rem x 3)))) -> ((3 6 9) (1 2 4 5 7 8 ))
(divideList '(3 -9 2 6 -8 -4) 'minusp) -> ((-9 -8 -4) (3 2 6))

[Lee Mac]

Perfect Gile 

[MP]

Code: [Select]

[color=green];; You're scaring me Gile! We coded nearly the exact same
;; thing, including reversing the list at the point of iteration:[/color]

(defun _SubDivide ( lst foo / a b )
    (foreach item (reverse lst)
        (if (foo item)
            (setq a (cons item a))
            (setq b (cons item b))
        )
    )
    (list a b)
)

Code: [Select]

[color=green];; The performance difference surprised me ...[/color]

(BenchMark
   '(
        (_SubDivide
           '(1 2 3 4 5 6 7 8 9)
            (lambda (x) (zerop (rem x 3)))
        )
        (DivideList
           '(1 2 3 4 5 6 7 8 9)
           '(lambda (x) (zerop (rem x 3)))
        )
    )
)

[color=green];; (_SUBDIVIDE (QUOTE (1 2 3 4 5 6 7 8 ...).....1545 / 6.17 <fastest>
;; (DIVIDELIST (QUOTE (1 2 3 4 5 6 7 8 ...).....9532 / 1.00 <slowest>
;;
;; !![/color]

[Lee Mac]

Michael, what is this indicating?

Code: [Select]

1545 / 6.17


[gile]

MP,
During a challenge on a French web site, we had the similar benchmark results with ElpanovEvgeniy. He used the following trick to avoid evaluating 'eval' at each iteration and keep the quoted form in the function calling.
I forgot to implement it

Code: [Select]

(defun divideList (lst fun / l1 l2)
(setq fun (eval fun))
  (foreach ele (reverse lst)
    (if (fun ele)
      (setq l1 (cons ele l1))
      (setq l2 (cons ele l2))
    )
  )
  (list l1 l2)
)

[MP]

Michael, what is this indicating?

Code: [Select]

1545 / 6.17

Elapsed milliseconds / relative speed for 16384 iteration(s)

[MP]

MP,
During a challenge on a French web site, we had the similar benchmark results with ElpanovEvgeniy. He used the following trick to avoid evaluating 'eval' at each iteration and keep the quoted form in the function calling.

I've done the same, and posted somewhere here at the swamp if I'm not mistaken, I'll see if I can find it. You have an excellent memory Gile, tho Evgeniy's (and yours) code tends to be that way.

[MP]

I've done the same, and posted somewhere here at the swamp if I'm not mistaken, I'll see if I can find it.

See this post. Check the foop argument, which is a "foo predicate" function. If it's a list it's assumed to be passed in the quoted form '(lambda (x) ...) and a "pre" eval is performed, otherwise it's assumed to be passed in unquoted form (lambda (x) ...) and left as is. I generally use the latter form for my code because it's more concise and assumed it would perform better; didn't realize how much better until today.

[Lee Mac]

Michael, could the speed not be improved by adding a simple:

Code: [Select]

(DivideList
           '(1 2 3 4 5 6 7 8 9)
           [color=red](function[/color] (lambda (x) (zerop (rem x 3))))
        )
    )