Arc Forumnew | comments | leaders | submitlogin
keep and rem at the same time ?
7 points by sacado 6103 days ago | 4 comments
Something I often run into : how can I split a list l in two sublists, one with all the elements of l passing a test, the other with elements not passing the test ? It can easily be done with keep and rem, both with the same test and on the same list, but is there a function or macro I missed doing the same thing in one pass ?


4 points by raymyers 6103 days ago | link

I don't think there is a library call for this. The way to go would probably be:

    (def keep-rem (test seq) (list keep.test.seq rem.test.seq))
However, if you really wanted to do it in one pass, you might do this:

    (def keep-rem (test seq)
      (let f (testify test)
        (if (alist seq)
            ((afn (s)
               (if (no s) (list nil nil)
                   (let (tokeep torem) (self (cdr s))
                        (if (f (car s))
                            (list (cons (car s) tokeep) torem)
                            (list tokeep (cons (car s) torem))))))
             seq)
            (coerce (keep-rem test (coerce seq 'cons)) 'string))))
Then we could kick it up a notch with some pattern matching.

    (require "lib/defpat.arc")
    (def keep-rem (test seq)
      (let f (testify test)
        (if (alist seq)
            ((p-m:afn
              (())       (list nil nil)
              ((x . xs)) (let (tokeep torem) (self xs)
                              (if (f x)
                                  (list (cons x tokeep) torem)
                                  (list tokeep (cons x torem)))))
             seq)
            (coerce (keep-rem test (coerce seq 'cons)) 'string))))
Bam!

-----

2 points by rkts 6103 days ago | link

This is a rare case where I think the tail-recursive solution is more readable:

  (def partition (f xs)
    (if (alist xs)
      (let f (testify f)
        ((afn (xs a b)
           (if (no xs)
             (list (rev a) (rev b))
             (f (car xs))
               (self (cdr xs) (cons (car xs) a) b)
               (self (cdr xs) a (cons (car xs) b))))
         xs nil nil))
      (map [coerce _ 'string] (partition f (coerce xs 'cons)))))
Also, how about generalizing accum to multiple lists?

  (mac accums (accfns . body)
    (let gaccs (map [uniq] accfns)
      `(withs ,(mappend (fn (gacc accfn)
                          (list gacc 'nil accfn `[push _ ,gacc]))
                        gaccs accfns)
         ,@body
         (list ,@(map [list 'rev _] gaccs)))))

  (def partition (f xs)
    (if (alist xs)
      (let f (testify f)
        (accums (a b) (each x xs ((if (f x) a b) x))))
      (map [coerce _ 'string] (partition f (coerce xs 'cons)))))

-----

3 points by almkglor 6103 days ago | link

True, although the final (rev a) (rev b) loses some of the speed benefit in the tail-recursion. If we didn't care about order (which happens quite often) we can drop the (rev ...) things. Otherwise, we can use a modulo-cons form, but this exceedingly complicated.

accums seems good... I suggest pushing it on nex-3's arc-wiki.

What I would like to see is a proper order-preserving accum. Here's a try at a "reasonably efficient" implementation:

  (mac accumf (accfn . body)
    " Collects or accumulates the values given to all calls to `accfn' within
      `body' and returns a list of those values.  The returned list
      is in the same order as calls to `accfn'.
      See also [[accum]] [[summing]] "
    (w/uniq (hd tl)
      `(let (,hd ,tl ,accfn) nil
            (= ,accfn
              (fn (s)
                (if ,hd
                    (do (= ,hd (cons s nil)) (= ,tl ,hd))
                    (do (= (cdr ,tl) (cons s nil)) (= ,tl (cdr ,tl))))))
            ,@body
            hd))))

-----

2 points by sacado 6103 days ago | link

Thanks for your answers ! I think that might be an interesting functionnality to add in the core functions. I used it a few times, in quite different contexts. Partitioning a list from a given criteria looks like a frequent action...

-----