Graham's "ANSI Common Lisp" has the following as an exercise:
Define a function that takes one argument, a number, and returns the
greatest argument passed to it so far.
I was not able to implement this in a single function. The closest I've
come is 1 function and 1 global special variable, like so:
(defvar *max-fn2* (let ((max))
#'(lambda (n)
(cond ((null max) (setf max n))
((> n max) (setf max n))
(t max)))))
(defun max-so-far2 (n)
(funcall *max-fn2* n))
Any hints or clues would be much appreciated.
Of course, if using a global special variable were okay, then something
like the following would be much simpler:
(defparameter *m* nil)
(defun max-so-far (n)
(cond ((null *m*) (setf *m* n))
((> n *m*) (setf *m* n))
(t *m*)))
But this seems too simple, so I'm sure I must be missing some way of
doing it with a single top-level function.
Solved it.
(let ((max))
(defun max-so-far (n)
(cond ((null max) (setf max n))
((> n max) (setf max n))
(t max))))
I was trying to have the function refer to a lexical variable from
outside its scope, but it had not occurred to me that the let could be
used at the top level.
j.k. schrieb:
> Slightly simpler:
>
> (let ((max))
> (defun max-so-far (n)
> (if (or (null max) (> n max))
> (setf max n)
> max)))
>
> CL-USER> (mapcar #'max-so-far '(1 0 2 0 3))
> (1 1 2 2 3)
>
You could already give the starting number in the let, thus saving the
(null max). From my "style feeling", I would prefer using a 'when' for
the side-effect and return max afterwards, so it is more easy to see
that max is always returned, independent of whether or not it changed.
(let ((max most-negative-fixnum))
(defun max-so-far (n)
(when (> n max)
(setf max n))
max))
Greetings, Benjamin
······@web.de wrote:
> You could already give the starting number in the let, thus saving the
> (null max). From my "style feeling", I would prefer using a 'when' for
> the side-effect and return max afterwards, so it is more easy to see
> that max is always returned, independent of whether or not it changed.
>
> (let ((max most-negative-fixnum))
> (defun max-so-far (n)
> (when (> n max)
> (setf max n))
> max))
>
> Greetings, Benjamin
Your version is easy to grasp with one glance, whereas I find myself
skipping back once or twice when looking at my version. Definitely an
improvement.
Thanks,
Joseph
"j.k." <·········@gmail.com> writes:
> ······@web.de wrote:
>> You could already give the starting number in the let, thus saving the
>> (null max). From my "style feeling", I would prefer using a 'when' for
>> the side-effect and return max afterwards, so it is more easy to see
>> that max is always returned, independent of whether or not it changed.
>>
>> (let ((max most-negative-fixnum))
>> (defun max-so-far (n)
>> (when (> n max)
>> (setf max n))
>> max))
>>
>> Greetings, Benjamin
>
> Your version is easy to grasp with one glance, whereas I find myself
> skipping back once or twice when looking at my version. Definitely an
> improvement.
[25]> (let ((max most-negative-fixnum))
(defun max-so-far (n)
(when (> n max)
(setf max n))
max))
MAX-SO-FAR
[26]> (max-so-far -100000000)
-16777216
[27]>
Also, you specified a number, so:
[27]> (max-so-far #C(1 1))
*** - >: #C(1 1) is not a real number
You should define the "max" for complex numbers...
--
__Pascal Bourguignon__ http://www.informatimago.com/
ADVISORY: There is an extremely small but nonzero chance that,
through a process known as "tunneling," this product may
spontaneously disappear from its present location and reappear at
any random place in the universe, including your neighbor's
domicile. The manufacturer will not be responsible for any damages
or inconveniences that may result.
Pascal Bourguignon wrote:
> [25]> (let ((max most-negative-fixnum))
> (defun max-so-far (n)
> (when (> n max)
> (setf max n))
> max))
>
> MAX-SO-FAR
> [26]> (max-so-far -100000000)
> -16777216
> [27]>
Right, if your numbers could happen to be that small, you should use
the null-version
> Also, you specified a number, so:
>
> [27]> (max-so-far #C(1 1))
>
> *** - >: #C(1 1) is not a real number
>
> You should define the "max" for complex numbers...
No, for complex numbers there exists no order-relation and thus no #'>:
CL(4): (> #C(1 1) #C(1 0))
Error: `#C(1 1)' is not of the expected type `REAL'
[condition type: TYPE-ERROR]
So a direct max-fn makes no sense - instead, what you really propose is
a max-abs-so-far function, e.g
(let ((max-abs 0)
(biggest-num))
(defun max-abs-so-far (num)
(let ((abs (abs num)))
(when (> abs max-abs)
(setf max-abs abs
biggest-num num))
biggest-num))))
Regards,
Benjamin
·······@web.de" <······@web.de> writes:
>> Also, you specified a number, so:
>>
>> [27]> (max-so-far #C(1 1))
>>
>> *** - >: #C(1 1) is not a real number
>>
>> You should define the "max" for complex numbers...
>
> No, for complex numbers there exists no order-relation and thus no #'>:
What about this:
(defun complex-< (a b)
(or (< (imagpart a) (imagpart b))
(and (= (imagpart a) (imagpart b))
(< (realpart a) (realpart b)))))
Is this not an order relation on the complex?
It's even compatible with < on the reals!
(It may has some unfortunate properties, but at least it's a total order).
> CL(4): (> #C(1 1) #C(1 0))
> Error: `#C(1 1)' is not of the expected type `REAL'
> [condition type: TYPE-ERROR]
>
> So a direct max-fn makes no sense - instead, what you really propose is
> a max-abs-so-far function, e.g
>
> (let ((max-abs 0)
> (biggest-num))
> (defun max-abs-so-far (num)
> (let ((abs (abs num)))
> (when (> abs max-abs)
> (setf max-abs abs
> biggest-num num))
> biggest-num))))
If that's what you need.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"What is this talk of "release"? Klingons do not make software
"releases". Our software "escapes" leaving a bloody trail of
designers and quality assurance people in its wake."
Pascal Bourguignon wrote:
> What about this:
>
> (defun complex-< (a b)
> (or (< (imagpart a) (imagpart b))
> (and (= (imagpart a) (imagpart b))
> (< (realpart a) (realpart b)))))
>
> Is this not an order relation on the complex?
> It's even compatible with < on the reals!
No, it is very different as opposed to the complex, the reals are an
ordered field. So you shouldn't give your order the name "<".
>
>
> (It may has some unfortunate properties, but at least it's a total order).
Okay, I should've written more precisely...
>
>
>
> If that's what you need.
>
If you need different ones, make it a higher-order function...
> > (let ((max most-negative-fixnum))
> > (defun max-so-far (n)
> > (when (> n max)
> > (setf max n))
> > max))
"j.k." <·········@gmail.com> writes:
> Your version is easy to grasp with one glance, whereas I find myself
> skipping back once or twice when looking at my version. Definitely
> an improvement.
I think it's important to note that most-negative-fixnum is to be
regarded as a completely arbitrary number in this context, and is
likely to cause unexpected behavior unless the user of max-so-far is
aware of this detail. I think the init-with-nil scheme is much to
prefer in general, e.g.
(let (max)
(defun max-so-far (x)
(setf max (max x (or max x)))))
even if you /can/ avoid the "extra" check if you really want:
(defun max-so-far (x)
(let ((max x))
(defun max-so-far (x)
(setf max (max x max))))
x)
but this version has unwanted properties such as the fact that
(mapcar #'max-so-far ...)
is not equivalent to
(mapcar 'max-so-far ...)
Extra credits if you can explain which usage is "correct" and why.. :)
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld wrote:
> <snip/>
> even if you /can/ avoid the "extra" check if you really want:
>
> (defun max-so-far (x)
> (let ((max x))
> (defun max-so-far (x)
> (setf max (max x max))))
> x)
>
> but this version has unwanted properties such as the fact that
>
> (mapcar #'max-so-far ...)
>
> is not equivalent to
>
> (mapcar 'max-so-far ...)
>
> Extra credits if you can explain which usage is "correct" and why.. :)
>
> --
> Frode Vatvedt Fjeld
Wow, very strange:
CL-USER> (mapcar #'max-so-far '(0 1 0 2))
STYLE-WARNING: redefining MAX-SO-FAR in DEFUN
STYLE-WARNING: redefining MAX-SO-FAR in DEFUN
STYLE-WARNING: redefining MAX-SO-FAR in DEFUN
STYLE-WARNING: redefining MAX-SO-FAR in DEFUN
(0 1 0 2)
CL-USER> (mapcar 'max-so-far '(0 1 0 2))
(2 2 2 2)
CL-USER>
<recompile/>
CL-USER> (mapcar 'max-so-far '(0 1 0 2))
STYLE-WARNING: redefining MAX-SO-FAR in DEFUN
STYLE-WARNING: redefining MAX-SO-FAR in DEFUN
STYLE-WARNING: redefining MAX-SO-FAR in DEFUN
STYLE-WARNING: redefining MAX-SO-FAR in DEFUN
(0 1 0 2)
CL-USER> (mapcar #'max-so-far '(0 1 0 2))
(2 2 2 2)
CL-USER>
It appears to me that they are behaving in the same--albeit very
strange--way: after recompile, the first mapcar, regardless of which it
is, does not work, but the global function seems to have been updated
after the mapcar completes, so that whichever mapcar version is
performed next, it will succeed. I cannot see any difference in
behavior between the two.
Okay, after much hair pulling, and finally looking in the hyperspec,
specifically trying to see if mapcar's "if function is a symbol, it is
coerced to a function as if by symbol-function" + symbol-function's
"symbol-function cannot access the value of a lexical function name
produced by flet or labels; it can access only the global function
value" could have something to do with why they should be different, I
decided to try the function in clisp instead of sbcl (which I usually
use exclusively).
Lo and behold. The #' version behaves the same in clisp (still doesn't
work), but the ' version behaves correctly. Is this the behavior you
had in mind?
I'm guessing that the ' version works because the symbol-function is
called once per list element, and thus gets the updated function,
whereas the #' version does not use symbol-function, so doesn't rebind
the function internally and get the updated version between list
elements.
I'm grasphing at straws, and this doesn't totally make sense to me. Any
explanation would be greatly appreciated.
"j.k." <·········@gmail.com> writes:
> Frode Vatvedt Fjeld wrote:
>> <snip/>
>> even if you /can/ avoid the "extra" check if you really want:
>>
>> (defun max-so-far (x)
>> (let ((max x))
>> (defun max-so-far (x)
>> (setf max (max x max))))
>> x)
>>
>> but this version has unwanted properties such as the fact that
>>
>> (mapcar #'max-so-far ...)
>>
>> is not equivalent to
>>
>> (mapcar 'max-so-far ...)
>>
>> Extra credits if you can explain which usage is "correct" and why.. :)
> [...]
The "strange" results from sbcl are probably due to the
non-reinitialization of x; here is what I get with clisp:
[114]> (mapcar (function max-so-far) '(2 3 0 1))
(2 3 0 1)
[115]> (mapcar (quote max-so-far) '(2 3 0 1))
(2 3 3 3)
[116]> (mapcar (function max-so-far) '(2 3 0 1))
(3 3 3 3)
[117]> (mapcar (quote max-so-far) '(2 3 0 1))
(3 3 3 3)
> Okay, after much hair pulling, and finally looking in the hyperspec,
> specifically trying to see if mapcar's "if function is a symbol, it is
> coerced to a function as if by symbol-function" + symbol-function's
> "symbol-function cannot access the value of a lexical function name
> produced by flet or labels; it can access only the global function
> value" could have something to do with why they should be different, I
> decided to try the function in clisp instead of sbcl (which I usually
> use exclusively).
>
> Lo and behold. The #' version behaves the same in clisp (still doesn't
> work), but the ' version behaves correctly. Is this the behavior you
> had in mind?
>
> I'm guessing that the ' version works because the symbol-function is
> called once per list element, and thus gets the updated function,
> whereas the #' version does not use symbol-function, so doesn't rebind
> the function internally and get the updated version between list
> elements.
>
> I'm grasphing at straws, and this doesn't totally make sense to me. Any
> explanation would be greatly appreciated.
You've got it.
When passing (quote max-so-far) to mapcar, you let it apply the
function refered indirectly by the symbol-function slot of the symbol
max-so-far. So max-so-far works, (but redefines the functions everytime).
When passing (function max-so-far) to mapcar, you're passing the first
function definition, and while you're modifying the symbol-function
slot of the symbol max-so-far everytime, mapcar keep calling that very
same first function you gave it.
Note that AFAIK, nothing prevents MAPCAR to be implemented as:
(defun mapcar (function &rest lists)
(when (symbolp function) (setf function (symbol-function function)))
...)
In which case max-so-far would never work as you intended.
If you want to have one function the first time, and another the other
times, you could do it like this:
[171]> (let (worker)
(setf worker (lambda (x)
(setf worker (let ((max x))
(lambda (x)
(setf max (max x max)))))
x))
(defun max-so-far (x)
(funcall worker x)))
MAX-SO-FAR
[172]> (mapcar (function max-so-far) '(1 2 3 4 5 4 3 2 1))
(1 2 3 4 5 5 5 5 5)
--
__Pascal Bourguignon__ http://www.informatimago.com/
HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.
······@web.de wrote:
>
> You could already give the starting number in the let, thus saving the
> (null max).
You couldn't: there is no lowest possible real in CL (there may be an
implementation-dependent one, but even if there is you probably don't
want to wire it into code as it's likely to use a lot of storage).
--tim
······@web.de wrote:
> j.k. schrieb:
>
>>Slightly simpler:
>>
>>(let ((max))
>> (defun max-so-far (n)
>> (if (or (null max) (> n max))
>> (setf max n)
>> max)))
>>
>>CL-USER> (mapcar #'max-so-far '(1 0 2 0 3))
>>(1 1 2 2 3)
>>
>
>
> You could already give the starting number in the let, thus saving the
> (null max). From my "style feeling", I would prefer using a 'when' for
> the side-effect and return max afterwards, so it is more easy to see
> that max is always returned, independent of whether or not it changed.
>
> (let ((max most-negative-fixnum))
> (defun max-so-far (n)
> (when (> n max)
> (setf max n))
> max))
Two Deep Style Thoughts:
(1) If you had seen the movie 2010, you would know what happens when we
ask computers to lie. :) If max-so-far has never been called before, the
maximum value so far is not most-negative-fixnum or any other number.
What if the caller is taking the return value from max-so-far and, iff
it is not null, doing a computation off the delta? Boom, there goes
another satellite on approaach to Mars.
(2) "Saving the (null max)" has value iff all other things are equal.
But in this case it obscures the specification. One has to stare at the
"when" approach to work backwards to what is really going on. In this
trivial example (with the spec in the function name <g>) the obfuscation
is, well, obfuscated, but in real code buried within some larger
expression it could lead to someone including the original author making
a change and missing the subtleties. Boom, there goes another Ariane. :)
ken
·······@web.de" <······@web.de> writes:
> You could already give the starting number in the let, thus saving the
> (null max).
What if the function should also work with integers smaller than
most-negative-fixnum?
> (let ((max most-negative-fixnum))
> (defun max-so-far (n)
> (when (> n max)
> (setf max n))
> max))
Here's another variation:
(let ((max most-negative-fixnum))
(defun max-so-far (n)
(setf max (max max n))))
j.k. wrote:
> Slightly simpler:
>
> (let ((max))
> (defun max-so-far (n)
> (if (or (null max) (> n max))
> (setf max n)
> max)))
>
> CL-USER> (mapcar #'max-so-far '(1 0 2 0 3))
> (1 1 2 2 3)
>
Oh come on. You're taking the easy way out. Why not work this baby?
(defun max-so-far (n)
(labels ((f (x)
(setf n (max x n))
n))
(setf (symbol-function 'max-so-far) #'(lambda (x) (f x))))
n)
(defun max-so-far (n)
(labels ((f (x y)
(let ((max (max x y)))
(setf (symbol-function 'max-so-far)
#'(lambda (x) (f x max)))
max)))
(f n n)))
Of course, these don't work with your MAPCAR example above, so maybe
you're best off sticking with your solution. It's too late at night for
me to try coming up with a Y-combinator version...
Aloha,
David Sletten
(I hope you see that these are just absurd ways to take advantage of
closures--as you did in a sensible way.)
David Sletten wrote:
> Oh come on. You're taking the easy way out. Why not work this baby?
>
> ...snip...
>
> (I hope you see that these are just absurd ways to take advantage of
> closures--as you did in a sensible way.)
Actually, my original attempts to get something working with only 1
top-level defun (not inside a let) were even stranger, but they had the
unfortunate property of not working in any shape or form, mapcar or
otherwise.
"j.k." <·········@gmail.com> wrote in message ·····························@j33g2000cwa.googlegroups.com...
>
> Define a function that takes one argument, a number, and returns the
> greatest argument passed to it so far.
>
> Any hints or clues would be much appreciated.
Think 'closure'.
--
Geoff
Thanks for the hint, Geoff. You must have posted at just about the time
that I finally figured it out.
I knew it had to be a closure of some sort, but the missing piece was
that I hadn't realized I could use a let at the top-level for the
closure. I was stuck in the frame of mind that a closure is something
that another function returns and I bind to a variable and then use via
funcall.
Is that correct :
(defun greater (x)
(let ((n '(0)))
(when (> x (car n)) (rplaca n x))
(car n)))
From: Bill Atkins
Subject: Re: ANSI Common Lisp: Chp. 6, #6
Date:
Message-ID: <87d5gz8moh.fsf@rpi.edu>
·············@free.fr writes:
> Is that correct :
>
> (defun greater (x)
> (let ((n '(0)))
> (when (> x (car n)) (rplaca n x))
> (car n)))
Why are you using a list?
From: Bill Atkins
Subject: Re: ANSI Common Lisp: Chp. 6, #6
Date:
Message-ID: <874q2b8mi3.fsf@rpi.edu>
Bill Atkins <············@rpi.edu> writes:
> ·············@free.fr writes:
>
>> Is that correct :
>>
>> (defun greater (x)
>> (let ((n '(0)))
>> (when (> x (car n)) (rplaca n x))
>> (car n)))
>
> Why are you using a list?
Also, no.....it's not correct. It's not saving state between calls,
and its comparison behavior is wrong. Every time you call this
function with an X greater than 0, it will return that number. If X
is 0 or lower, it will return 0.
No,
On Allegro CL, I get :
CG-USER : (greater 5)
5
CG-USER : (greater 2)
5
CG-USER : (greater 10)
10
CG-USER : (greater -5)
10
I use a list because I can do rplaca.
From: Bill Atkins
Subject: Re: ANSI Common Lisp: Chp. 6, #6
Date:
Message-ID: <87u0ab775g.fsf@rpi.edu>
·············@free.fr writes:
> No,
> On Allegro CL, I get :
> CG-USER : (greater 5)
> 5
> CG-USER : (greater 2)
> 5
> CG-USER : (greater 10)
> 10
> CG-USER : (greater -5)
> 10
> I use a list because I can do rplaca.
Oh, good heavens. Yes - this works because you're modifying a
constant, but this is not behavior you should rely on. The
appropriate solution is a closure (or even a global variable) holding
an integer. Your code worked more out of chance than out of design.
Try using the constant '(0) somewhere else in that function (or,
what's worse, somewhere else in that file). You'll find its value
isn't what you expect.
Bill
"Bill Atkins" <············@rpi.edu> wrote in message
···················@rpi.edu...
> Bill Atkins <············@rpi.edu> writes:
>
>> ·············@free.fr writes:
>>
>>> Is that correct :
>>>
>>> (defun greater (x)
>>> (let ((n '(0)))
>>> (when (> x (car n)) (rplaca n x))
>>> (car n)))
>>
>> Why are you using a list?
>
> Also, no.....it's not correct. It's not saving state between calls,
> and its comparison behavior is wrong. Every time you call this
> function with an X greater than 0, it will return that number. If X
> is 0 or lower, it will return 0.
This function works, at least in LispWorks, but for the wrong reason I
think. A constant, i.e. a quoted list *is being modified*!!!!! I wish I
had a dollar, (or a euro), for every time I've read here not to do this. The
compiler has embedded the '(0) in the compiled code itself, so the function
carries the latest maximum value inside it like a cancer.
Carl Taylor
Well, I'm just newbie in Lisp, and I haven't read all the posts here.
I'll remember your advise.
But I thought it was quite funny, a funtion that modifies its own code
!
Joël