LispBlog

[gusl]

Given a test and a list, BIPART divides the list in two: the ones which pass the test, and the ones which don't.

;;;I want to implement such a bipart function functionally: no PUSHs, and no LOOPS

;;using 'select' and 'not-p' from my personal LISP library, it's easy to come up with:

(defun bipart (test l)
  (list (select test l) (select (not-p test) l)))
;;PROBLEM: inefficient: will do each test twice

;;ok, let me try something else:

(defun bipart (test l yeses noes)
  (cond ((null l) (list yeses noes))
	((funcall test (car l))
	 (bipart test (cdr l) (cons (car l) yeses) noes))
	(T (bipart test (cdr l) yeses (cons (car l) noes)))))

;;I thought I had it until the tests showed that the list comes back backwards. The reason is that the 'cons' is inside the recursive call. (couldn't we use a backwards CONS?)
;;Calling a reverse function would be inefficient. So can we bring it out, as in the following code?

(defun bipart-yes (test l) ;;;i.e. the same as 'select'
  (cond ((null l) nil)
	((funcall test (car l))
	 (cons (car l) (bipart test (cdr l))))
	(T (bipart test (cdr l)))))

;;this one is the right way around. Can we apply it to the general bipart?
;;the problem is that 'bipart' keeps two lists, so it's more complex:

(defun bipart (test l)
  (cond ((null l) (list nil nil))
	((funcall test (car l))
	 (list
	  (cons (car l) (first (bipart test (cdr l))))
	  (second (bipart test (cdr l)))))
	(T
	 (list
	  (first (bipart test (cdr l)))
	  (cons (car l) (second (bipart test (cdr l))))))))

;;;PROBLEM: we're going in and out of the pair, and unless some smart optimization is going on, it's going to be inefficient.

;;We clean it up a bit, with a 'let':

(defun bipart (test l)
  (if (null l) (list nil nil)
      (let ((bip (bipart test (cdr l))))
	(if (funcall test (car l))
	    (list (cons (car l) (first bip)) (second bip))
	    (list (first bip) (cons (car l) (second bip)))))))

;;Clean it up even more, with an 'flet' this time:

(defun bipart (test l)
  (if (null l) (list nil nil)
      (let ((bip (bipart test (cdr l))))
	(flet ((app #'(lambda (x) (cons (car l) x))))
	  (list
	   (if (funcall test (car l)) (app (first bip)) (first bip))
	   (if (funcall test (car l)) (second bip) (app (second bip)))))))

;;it's still bad that we are calling the if with the same condition twice, so we

(defun bipart (test l)
  (if (null l) (list nil nil)
      (let ((bip (bipart test (cdr l))) ((t (funcall test (car l)))))
	(flet ((app #'(lambda (x) (cons (car l) x))))
	  (list (if t (app (first bip)) (first bip))
		(if t (second bip) (app (second bip))))))))

;;ok, we've abbreviated the condition, but the code "if t" is still redundant


Recursive functions often have similarly redundant code. Should we start using higher-level code, or meta-programming in such cases?

Comments

partition

[r6.livejournal.com]

Why not do what Haskell does?

-- partition takes a predicate and a list and returns a pair of lists:
-- those elements of the argument list that do and do not satisfy the
-- predicate, respectively; i.e.,
-- partition p xs == (filter p xs, filter (not . p) xs).
partition               :: (a -> Bool) -> [a] -> ([a],[a])
partition p xs          =  foldr select ([],[]) xs
                           where select x (ts,fs) | p x       = (x:ts,fs)
                                                  | otherwise = (ts, x:fs)

Re: partition

[gustavolacerda.livejournal.com]

Interesting, thanks. I don't know Haskell, unfortunately.

Let me guess: you're defining 'select' on the fly.

foldr ([],[]) xs

applies select iteratively for each element of xs starting out with ([],[]). I don't know of a similar function in Lisp (or any language, for that matter).

x:ts   is the same as (cons x ts)

It's interesting that you didn't have to type 'x' or 'select', since 'partition' is typed.

Btw, I think 'insert' would be a better name for 'select'.

Re: partition

[r6.livejournal.com]

foldr, right fold, is a fundamental list operation. It must exist in lisp. You are right about the cons notation.

Actually you don’t have to type anything at all. partition is typed for both documentation, and preventing errors.

Re: partition

[gustavolacerda.livejournal.com]

Doesn't your Haskell code invert the order of the elements? My Lisp code below does.

Re: partition

[r6.livejournal.com]

You need to flip around your function call and recursive call in your implementation of foldr. What you’ve got there is foldl.

Re: partition

[gustavolacerda.livejournal.com]

So foldl is tail-recusive but foldr is not?

That's not very symmetrical, IMHO!

Re: partition

[r6.livejournal.com]

That’s the way it is. Tail-recursion isn’t preserved under this symmetry. In this case there is no point in being tail-recursive because your output is O(n) anyways.

Re: partition

[gustavolacerda.livejournal.com]

Ok. In this case, the growth in the size of the recursively-passed argument in FOLDL breaks even with the growth of the stack in FOLDR.

Re: partition

[tiedyedave]

It's because cons, and thus the construction of lists, is inherently asymmetric . If it weren't, append could be guaranteed to be a constant time operation.

There's definitely an argument to be made for a "heavier" list implementation: doubly linked with two head pointers. Then cons is symmetric (append is constant time), and reverse is also constant time (just swap the head pointers), and it would require only n+1 more pointers for an n element list. However, this would have to be natively implemented and use opaque primitive operations. The advantage of the list construct of Haskell and friends is that it's directly expressible as a datatype; you can "do it yourself" if you really want to, and it requires no notion of pointers or memory traversal.

Re: partition

[tiedyedave]

Edit: Swap the direction of traversal, not the head pointers, my bad. This entails an extra direction bit.

Re: partition

[gustavolacerda.livejournal.com]

Ok, I just implemented

foldr

and

bipart

in Lisp.

(defun foldr (fn initial lst)
       (if (null lst) initial
           (foldr fn (funcall fn (car lst) initial) (cdr lst))))

(defun bipart (fn l)
   (foldr #'(lambda (el lst) (if (funcall fn el) (list (cons el (car lst)) (cadr lst)) (list (car lst) (cons el (cadr lst))))) (list nil nil) l))

Haskell is handier than Lisp with its pattern-matching, since you can write (ts,fs) to represent any pair (two element list, right?).

... although fare has written a "famous" pattern-matcher. I'd be curious to see how he would do this.

Re: partition

[tiedyedave]

pair (two element list, right?)

Actually, pairs are not two-element lists in Haskell (or any ML-like language), which pinpoints an interesting distinction between Haskell/ML-family and Lisp. In ML-like languages, lists must be homogeneous in type: [1,2,3] is a legal list, whereas [1, "one", (fn f => (fn x => f x))] is not. Tuples can be heterogeneous (2, "two"), but their length (2), and type (int * string), must be known statically.

[gustavolacerda.livejournal.com]

What's the generalization of Haskell pair into a list of any size?

Sum Types

[r6.livejournal.com]

There is none. However there are sum types (and lists of sum types) which solve all the problems you may worry about.

Re: Sum Types

[gustavolacerda.livejournal.com]

I'm thinking of a type like "thing" which could serve as an envelope for any type. A list of things could represent any Lisp list, namely by each element having the type it needs... but I don't know if Haskell has subtyping.

Re: Sum Types

[r6.livejournal.com]

Haskell has no sub-typing. The problem is, what could you do with a list of arbitary things?

Re: partition

[gustavolacerda.livejournal.com]

ah, ok, "tuples". Can you do all the normal list operations on tuples? Can you define a polymorphic function, i.e. working for both lists and tuples?

Re: partition

[r6.livejournal.com]

Nope.

Re: partition

[(Anonymous)]

Generally, no - but providing something like this:

import Control.Arrow

instance Functor ((,) a) where
    fmap = second

You could do polymorphic functions working on both types, but behaving differently - i.e.

fmap :: (a -> b) -> (c,a) -> (c,b)

[darius.livejournal.com]

I think your FLET syntax is wrong -- at least I've never seen it written that way.

I'd like to complain about the "l" too -- looks like a 1.

How I would write it:

;; warning: untested
(define bipart (f xs)
  "Return two lists: the XS for which F is true, and those for
  which it's false, preserving the original list order in both."
  (if (null xs) 
      (values '() '())
      (let ((head (car xs)))
        (multiple-value-bind (true-tail false-tail) (bipart (cdr xs))
          (if (f head)
              (values (cons head true-tail) false-tail)
              (values true-tail (cons head false-tail)))))))

[gustavolacerda.livejournal.com]

yeah, I just wrote it as if it were a 'let'... as I warned, it was never tested.

[(Anonymous)]

Please consider consulting the CLHS (http://www.lispworks.com/documentation/HyperSpec/Front/index.htm) before you reinvent the flat tire:

select = remove-if-not (http://www.lispworks.com/documentation/HyperSpec/Body/f_rm_rm.htm#remove-if-not)

not-p = complement (http://www.lispworks.com/documentation/HyperSpec/Body/f_comple.htm)

foldl/foldr = reduce (http://www.lispworks.com/documentation/HyperSpec/Body/f_reduce.htm#reduce)

-- Sebastian "What-if-I-don't-want-to-sign-my-name?" Stern

[gustavolacerda.livejournal.com]

Good to know about the CLHS, though I'm not sure if I'd easily find foldl/foldr. Btw, to use 'reduce' you need to reverse the order of the arguments, for example if you want to pass #'cons.

Re: 'not-p', I also have an 'and-p', 'or-p' and 'implies-p'. Unless all of these are conveniently named in Lisp, I think my standard is worthy of existence.

Re: select vs remove-if-not
remove-if-not is a terrible name, because I'm not mutating anything. It's also too long.


>"What-if-I-don't-want-to-sign-my-name?"
You won't be notified of my reply, and if it takes me days to get around to it, I'll have no idea who it is, and I'll probably think that it's not worth responding to. This is the reason I invited you to join LJ... you don't even have to login if you use a cookie. You could also read my dark secrets that way.

[(Anonymous)]

Btw, to use 'reduce' you need to reverse the order of the arguments, for example if you want to pass #'cons.

I think you need the :from-end t option.

Re: 'not-p', I also have an 'and-p', 'or-p' and 'implies-p'. Unless all of these are conveniently named in Lisp, I think my standard is worthy of existence.

Maybe a character macro would be more convenient. Something like (!and ... ...).

You won't be notified of my reply

Which notification do you mean?

[gustavolacerda.livejournal.com]

(1) :from-end determines the order in which the list elements get used, not the order of arguments in the two-argument function. :from-end determines whether it's FOLDL or FOLDR.

(2) I'd like to learn about that.

(3) The link to this that I send to your email. Do you have a bot to watch this page for you? Anyway, a reply to an anonymous comment is quite likely to never be read by anyone.

[gustavolacerda.livejournal.com]

oh, I think :from-end *both* determines (1) whether it's FOLDL or FOLDR *and* (2) the order in which elements get .

How would you write a REVERSE using REDUCE and #'cons?

reduce

[(Anonymous)]

(reduce #'foo '(1 2 3) :initial-value nil)
is
(foo (foo (foo nil 1) 2) 3)

(reduce #'foo '(1 2 3) :from-end t :initial-value nil)
is
(foo 1 (foo 2 (foo 3 nil)))

Also, I would write bipart like this, but that may just be me:

(defun bipart (test list)
  (loop for elem in list
        when (funcall test elem)
          collect elem into passed
        else
          collect elem into failed
        finally (return (values passed failed))))

[(Anonymous)]

(reduce #'(lambda (a b) (cons b a)) '(1 2 3) :initial-value nil) is probably the easiest way to do it.

[xach.livejournal.com]

Calling nreverse is not very inefficient. Here's a possible implementation of bipart:

   (defun bipart (test list)
     (let (passed failed)
       (dolist (i list (values (nreverse passed) (nreverse failed)))
         (if (funcall test i)
             (push i passed)
             (push i failed)))))

[gustavolacerda.livejournal.com]

Hm.. Could one change this into a functional program?

If we're passing a simply-linked list, nreverse will be just as bad as reverse, right?

[xach.livejournal.com]

NREVERSE may be significantly faster than REVERSE.