## Help reduce nested lambdas

Discussion of Common Lisp

### Help reduce nested lambdas

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!
wvxvw

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

### Re: Help reduce nested lambdas

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

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

### Re: Help reduce nested lambdas

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...

nuntius

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

### Re: Help reduce nested lambdas

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?
wvxvw

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

### Re: Help reduce nested lambdas

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.
Ramarren

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

### Re: Help reduce nested lambdas

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 But he can use return-from to force map-product to exit.
gugamilare

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

### Re: Help reduce nested lambdas

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.
Ramarren

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

### Re: Help reduce nested lambdas

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.
wvxvw

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

### Re: Help reduce nested lambdas

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).
Ramarren

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

### Re: Help reduce nested lambdas

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

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