Help reduce nested lambdas

Discussion of Common Lisp
Post Reply
wvxvw
Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

Help reduce nested lambdas

Post by wvxvw » Fri Jan 27, 2012 4:14 am

Hi, I've got this function:

Code: Select all

(defun operation-associative-p (operation set)
  (not
   (find-if
    #'(lambda (x)
	(find-if
	 #'(lambda (y)
	     (find-if
	      #'(lambda (z)
		  (let ((a (funcall
			    operation x (funcall operation y z)))
			(b (funcall
			    operation (funcall operation x y) z)))
		    (if (eq a b)
			(format t "~a * (~a * ~a) = ~a <=> (~a * ~a) * ~a = ~a~&"
				x y z a x y z b)
			t))) set)) set)) set)))
And it looks like it must be possible to reduce it somehow to only define the top-level lambda once (basically it, and the next lambda are the same functions!) but I cannot think of a way to do it :)

This is rather a more general question, then particular to the problem of bruteforce proof of associativity :)
Thanks!

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Help reduce nested lambdas

Post by gugamilare » Fri Jan 27, 2012 5:34 pm

This is possible with alexandria's map-product. I don't think it is possible with standard Common Lisp only.

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Help reduce nested lambdas

Post by nuntius » Sat Jan 28, 2012 2:05 am

dolist is a valid approach (code is not tested)

Code: Select all

(defun operation-associative-p (operation set)
  (dolist (x set)
    (dolist (y set)
      (dolist (z set)
        (let ((a (funcall
                  operation x (funcall operation y z)))
              (b (funcall
                  operation (funcall operation x y) z)))
          (when (eq a b)
            (format t "~a * (~a * ~a) = ~a <=> (~a * ~a) * ~a = ~a~&"
                    x y z a x y z b)
            (return-from operation-associative-p t))))))
  nil)
P.S. the equality test probably shouldn't be eq...

wvxvw
Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

Re: Help reduce nested lambdas

Post by wvxvw » Sat Jan 28, 2012 5:01 am

gugamilare, thank you, I'll take a look.

nuntius, well, there may be many ways to do the same thing, I could've used mapcar for this, or loop etc. I used find-if because it's a function (not a macro), and I used eq because I knew beforehand that the list will only contain numbers and symbols. But when you do it with dolist, you get, same as in my code, 2 almost identical calls, and this is something I was trying to find a way to *optimize*. (I don't mean optimizing for speed, rather making it shorter). For example (* x x x), an optimized version would be (expt x 3).

EDIT: gugamilare, I checked out the Alexandria's code, but could find only map-combinations function, not map-product, is that what you meant?

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Help reduce nested lambdas

Post by ramarren » Sat Jan 28, 2012 5:45 am

wvxvw wrote:I used eq because I knew beforehand that the list will only contain numbers and symbols
EQ is not defined to work reliably on numbers. It compares pointer equality and some numbers, especially those that do not fit into machine word minus tags, might be multiply instantiated. There isn't really reason not to ever use EQL.
wvxvw wrote:EDIT: gugamilare, I checked out the Alexandria's code, but could find only map-combinations function, not map-product, is that what you meant?
What version of Alexandria did you look at? Version from quicklisp has map-product in lists.lisp.

EDIT: Of course, map-product doesn't exactly do what you want, since it doesn't short-curcuit when it finds the first counter-example. You can do something like this (minimally tested):

Code: Select all

(defun find-on-self-product (function list n)
  (if (zerop n)
      (funcall function)
      (find-if #'(lambda (x)
                   (find-on-self-product (alexandria:curry function x)
                                         list
                                         (1- n)))
               list)))

(defun operation-associative-p (operation set)
  (flet ((optest (x y z)
           (let ((a (funcall
                     operation x (funcall operation y z)))
                 (b (funcall
                     operation (funcall operation x y) z)))
             (if (eql a b)
                 (format t "~a * (~a * ~a) = ~a <=> (~a * ~a) * ~a = ~a~&"
                         x y z a x y z b)
                 t))))
    (not (find-on-self-product #'optest set 3))))
But I am not sure whether it actually simplifies anything. Also note that it uses alexandria:curry, but that is fairly trivial. In any case I would recommend extracting the test itself, having large block of code heavily indented is never good.

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Help reduce nested lambdas

Post by gugamilare » Sat Jan 28, 2012 7:19 am

Ramarren wrote:EDIT: Of course, map-product doesn't exactly do what you want, since it doesn't short-curcuit when it finds the first counter-example. You can do something like this (minimally tested):
Your solution looks cool :D But he can use return-from to force map-product to exit.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Help reduce nested lambdas

Post by ramarren » Sat Jan 28, 2012 7:40 am

gugamilare wrote:But he can use return-from to force map-product to exit.
True. I haven't really thought of that, because while I don't generally obsess about functional programming, I really dislike explicit returns, especially across call frames which would be necessary here.

wvxvw
Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

Re: Help reduce nested lambdas

Post by wvxvw » Sat Jan 28, 2012 8:46 am

Oh, I simply did git clone, so I thought I'd have the latest one?
Re' eq vs eql - I was meaning to say that's not really important b/c I am confident the input will not cause problems, but thank you anyway for pointing that out.
I'm a bit puzzled by your example, though it looks like what I was looking for: when n = 0, you are calling optest with no arguments, shouldn't it give an error? But I would need to see what alexandria:curry exactly does to really understand your code.

EDIT: oh, I see, currying changes the number of arguments, but is this how you do it when all arguments have been "accumulated", you call the curry w/o arguments?

Well, I didn't mean simplification as plain reduction of code surface, more as in example with multiplication vs rising to power. What if it wasn't a "cube" but more dimensions? Writing more and more nested functions which look very similar doesn't look like a good coding practice either.
Last edited by wvxvw on Sat Jan 28, 2012 9:06 am, edited 1 time in total.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Help reduce nested lambdas

Post by ramarren » Sat Jan 28, 2012 8:58 am

wvxvw wrote:Oh, I simply did git clone, so I thought I'd have the latest one?
It should be the latest one, and the repository linked from the page linked from cliki has map-product: at line 323.
wvxvw wrote:you are calling optest with no arguments
Curry is actually somewhat misnamed (see currying), since what the function actually does is partial application, that is, it returns the function of one less argument by fixing on of the arguments of the function given to it. This is a common technique in programming languages that put more emphasis on functional programming, such as Haskell.

What actually happens in the base case is that the function called has been constructed by fixing all arguments in the recursive case, and hence no longer requires arguments (n must be equal to function arity for this to work obviously).

wvxvw
Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

Re: Help reduce nested lambdas

Post by wvxvw » Sat Jan 28, 2012 9:12 am

I was looking at the wrong file - sequence.lisp, ok, now I see it.
Thanks again, you've been a great help so far!

Post Reply