From: marisal
Subject: Elegant solution asked
Date: Wed, 05 Mar 1997 00:00:00 +0000
Message-ID: <331DF5AD.128B@wrq.com>
Very often I need a function to map a 2 argument function over a list and
a fixed argument. For example, if we call such function map1:
(map1 #'list 'z '(a b c)) should return: '((z a) (z b) (z c))

Can anyone suggest an elegant solution for this. The best I could come up
with was:

(defun map1 (function fixed-argument list)
(mapcar (lambda (element) (funcall fn fixed-argument element)) list))

This works fine, but I have the gut feeling that there must be a
better/simpler way. Any ideas?
Please reply to: ········@epo.e-mail.com

From: Erik Naggum
Subject: Re: Elegant solution asked
Date: Wed, 05 Mar 1997 00:00:00 +0000
Message-ID: <3066591221451362@naggum.no>
* ·······@wrq.com
| Very often I need a function to map a 2 argument function over a list and
| a fixed argument. For example, if we call such function map1:
| (map1 #'list 'z '(a b c)) should return: '((z a) (z b) (z c))

recently, I had the same need, and used a circular list like this:

(defun repeatingly (&rest args)
(let ((list (copy-list args)))
(nconc list list)))

(mapcar #'list (repeatingly 'z) '(a b c))
=> ((z a) (z b) (z c))

this was modeled after the constantly' function, but I don't know how good
style this is.

#\Erik
--
if you think big enough, you never have to do it
From: Francis Leboutte
Subject: Re: Elegant solution asked
Date: Thu, 06 Mar 1997 00:00:00 +0000
Message-ID: <331e791a.4404553@news.glo.be>
Erik Naggum <····@naggum.no> wrote:

>* ·······@wrq.com
>| Very often I need a function to map a 2 argument function over a list and
>| a fixed argument. For example, if we call such function map1:
>| (map1 #'list 'z '(a b c)) should return: '((z a) (z b) (z c))
>
>recently, I had the same need, and used a circular list like this:
>
>    (defun repeatingly (&rest args)
>      (let ((list (copy-list args)))
>	(nconc list list)))
>
>    (mapcar #'list (repeatingly 'z) '(a b c))
> => ((z a) (z b) (z c))
>
>this was modeled after the constantly' function, but I don't know how good
>style this is.

Maybe you'll prefer this:

USER<10> (defun circular (list)
(let ((new-list (copy-list list)))
(rplacd (last new-list) new-list)
new-list))
CIRCULAR-LIST
USER<11>  (mapcar #'list (circular '(z)) '(a b c))
((Z A) (Z B) (Z C))

Francis
--
Francis Leboutte, Algorithme, Rue de la Charrette 141, 4130 Tilff, Belgium
····@glo.be      http://user.glo.be/~algo     t&fax: +32-(0)4-3883528
From: Erik Naggum
Subject: Re: Elegant solution asked
Date: Thu, 06 Mar 1997 00:00:00 +0000
Message-ID: <3066630268497107@naggum.no>
* Francis Leboutte
| Maybe you'll prefer this:
|
| USER<10> (defun circular (list)
|            (let ((new-list (copy-list list)))
|               (rplacd (last new-list) new-list)
|               new-list))
| CIRCULAR-LIST
| USER<11>  (mapcar #'list (circular '(z)) '(a b c))
| ((Z A) (Z B) (Z C))

I thought repeatingly' (or repeatedly', which I'm told is better a name)
was neat, because it provides a means to let a mapping function map
repeatedly over the object(s) that were the functions' arguments.  calling
it circular' or circular-list' says what it is, but not what it means;
there is no abstraction of purpose in sending it a list of the arguments,
quoted or otherwise.  actually, I think using a circular list with a
mapping function is a little "dangerous" unless there are other arguments
that have finite length, and it is also somewhat counter-intuitive to send
a circular list to a mapping function in the first place.  all of this led
me to discard the implementation-like name (which I used at first, too),
and then to use a more functionally abstract name.

I would like to hear opinions on whether this is good style, be it called
by a name that reflects the implementation or the purpose.

#\Erik
--
if you think big enough, you never have to do it
From: Barry Margolin
Subject: Re: Elegant solution asked
Date: Thu, 06 Mar 1997 00:00:00 +0000
Message-ID: <5fnss2$hc@pasilla.bbnplanet.com> In article <················@naggum.no>, Erik Naggum <····@naggum.no> wrote: >I thought repeatingly' (or repeatedly', which I'm told is better a name) >was neat, because it provides a means to let a mapping function map >repeatedly over the object(s) that were the functions' arguments. calling >it circular' or circular-list' says what it is, but not what it means; >there is no abstraction of purpose in sending it a list of the arguments, >quoted or otherwise. actually, I think using a circular list with a >mapping function is a little "dangerous" unless there are other arguments >that have finite length, and it is also somewhat counter-intuitive to send >a circular list to a mapping function in the first place. all of this led >me to discard the implementation-like name (which I used at first, too), >and then to use a more functionally abstract name. Your arguments for the name assume that the only purpose of creating a circular list is to pass it to a mapping function. Unless you plan on creating multiple functions, each named after the abstract "purpose" of the circular list, CIRCULAR-LIST seems like a more appropriate name. It is nicely analogous to LIST and VECTOR. >I would like to hear opinions on whether this is good style, be it called >by a name that reflects the implementation or the purpose. If you don't like the idea of passing circular lists to a mapping function in your application code (I agree, it's somewhat confusing), you could write an intermediate function: (defun map-with-constant (mapping-function function constant &rest lists) (apply mapping-function function (circular-list constant) lists)) This can then be used as (map-with-constant #'mapcar #'cons 1 '(1 2 3)) => ((1 . 1) (1 . 2) (1 . 3)). Only the author of this function needs to be aware of the way that mapping functions deal with circular lists, rather than bothering the application programmers with this trivia. -- Barry Margolin BBN Corporation, Cambridge, MA ······@bbnplanet.com (BBN customers, call (800) 632-7638 option 1 for support) From: Jason Trenouth Subject: Re: Elegant solution asked Date: Thu, 06 Mar 1997 00:00:00 +0000 Message-ID: <333fc1d0.268080729@newshost> On Wed, 05 Mar 1997 21:37:33 -0100, marisal <·······@wrq.com> wrote: > Very often I need a function to map a 2 argument function over a list and > a fixed argument. For example, if we call such function map1: > (map1 #'list 'z '(a b c)) should return: '((z a) (z b) (z c)) > > Can anyone suggest an elegant solution for this. The best I could come up > with was: > > (defun map1 (function fixed-argument list) > (mapcar (lambda (element) (funcall fn fixed-argument element)) list)) > > This works fine, but I have the gut feeling that there must be a > better/simpler way. Any ideas? You want CURRY, which could be defined as follows: (defun curry (fn &rest curried-args) #'(lambda (&rest args) (apply fn (append curried-args args)))) Then you can just do: (mapcar (curry 'list 'z) '(a b c)) => ((z a) (z b) (z c)) CURRY is named after its inventor (in case you wondered) and is standard practice in (other) functional programming languages. For example, the Dylan language has built-in functions CURRY and RCURRY. __Jason From: William D Clinger Subject: Re: Elegant solution asked Date: Thu, 06 Mar 1997 00:00:00 +0000 Message-ID: <331F5AF0.8CA@ccs.neu.edu> Currying is named after Haskell Curry, but it seems to have been invented by Schoenfinkel. The definition of CURRY that was given in Common Lisp isn't quite the same as the definition normally used in lambda calculus, which in Scheme would be more like (define (curry f) ; assumes f takes two arguments (lambda (x) (lambda (y) (f x y)))) Then MAP1 can be defined (still in Scheme) by (define (map1 f fixed-argument list) (map ((curry f) fixed-argument) list)) Erik Naggum wrote: > I would like to hear opinions on whether this is good style, be it called > by a name that reflects the implementation or the purpose. I thought Naggum's solution was cute, although I have a stylistic prejudice against solutions that use even local side effects (NCONC) or rely on the fact that MAPCAR has to test all of its arguments. There isn't much difference in their efficiency, although it should be slightly faster for the closures created by the original version of MAP1 or by the curried version above to fetch F and X from their local environment than it would be to perform the extra CONSP, CAR, and CDR operations that are required (inside MAPCAR) by Naggum's version. Some implementations have paid more attention to optimizing MAPCAR than closures, of course, so your mileage may vary. Will From: Rainer Joswig Subject: Re: Elegant solution asked Date: Sat, 08 Mar 1997 00:00:00 +0000 Message-ID: <joswig-ya023180000803971113260001@news.lavielle.com> In article <··················@newshost>, ·····@harlequin.co.uk (Jason Trenouth) wrote: > (defun curry (fn &rest curried-args) > #'(lambda (&rest args) > (apply fn (append curried-args args)))) > CURRY is named after its inventor (in case you wondered) and is standard See also: M. Sch�nfinkel, �ber die Bausteine der Mathematischen Logik, Math. Ann., 92, 1924 > practice in (other) functional programming languages. For example, the Dylan > language has built-in functions CURRY and RCURRY. Does it help to have this in the language itself?!? -- http://www.lavielle.com/~joswig/ From: Jason Trenouth Subject: Re: Elegant solution asked Date: Tue, 11 Mar 1997 00:00:00 +0000 Message-ID: <334256c6.101009213@newshost> On Sat, 08 Mar 1997 11:13:26 +0100, in comp.lang.lisp you wrote: > In article <··················@newshost>, ·····@harlequin.co.uk (Jason > Trenouth) wrote: > > > (defun curry (fn &rest curried-args) > > #'(lambda (&rest args) > > (apply fn (append curried-args args)))) > > > > CURRY is named after its inventor (in case you wondered) and is standard > > See also: M. Sch�nfinkel, �ber die Bausteine der Mathematischen Logik, > Math. Ann., 92, 1924 Also Frege in 1893 according to a functional programming FAQ: <URL:http://www.cs.nott.ac.uk/Department/Staff/mpj/faq.html> > > practice in (other) functional programming languages. For example, the Dylan > > language has built-in functions CURRY and RCURRY. > > Does it help to have this in the language itself?!? Dylan has several built-in function-composing functions: COMPOSE COMPLEMENT DISJOIN CONJOIN CURRY & RCURRY ALWAYS I can't vouch for the Dylan language designers or our own Dylan compiler wizards, but the fact that they are built-in to Dylan probably serves pedagogical, standardization, and efficiency purposes. Eg On the efficiency front I can imagine that a sufficiently smart compiler would be able to avoid calling the general implementation of CURRY given above. __Jason From: Bernhard Pfahringer Subject: Curry (was Re: Elegant solution asked) Date: Tue, 11 Mar 1997 00:00:00 +0000 Message-ID: <5g29tf$gf4@saturn.cs.waikato.ac.nz>
In article <··················@newshost>,
Jason Trenouth <·····@harlequin.co.uk> wrote:
> ...
>You want CURRY, which could be defined as follows:
>
>(defun curry (fn &rest curried-args)
>  #'(lambda (&rest args)
>      (apply fn (append curried-args args))))
> ...

for safety you may want to copy the rest-list:

(defun curry (fn &rest curried-args)
(setq curried-args (copy-list curried-args))
#'(lambda (&rest args)
(apply fn (append curried-args args))))

and for efficiency (if you call the curried function a lot) use:

(defun curry (fn &rest curry-args)
(compile nil
(lambda (&rest other-args)
(apply ',fn
,@(loop for x in curry-args collect (list 'quote x))
other-args))))

should cons less in for most CL implementations

Bernhard

PS: (loop for x in list collect (funcall fn constant x)) would
also be an alternative answer for the original question
--
-------------- rm - the ultimate in lossy compression ----------------
Bernhard Pfahringer
···············@cs.waikato.ac.nz http://www.ai.univie.ac.at/~bernhard
From: Lyman S. Taylor
Subject: Re: Curry (was Re: Elegant solution asked)
Date: Tue, 11 Mar 1997 00:00:00 +0000
Message-ID: <5g4a50$v8@pravda.cc.gatech.edu> In article <··········@saturn.cs.waikato.ac.nz>, Bernhard Pfahringer <········@saturn.cs.waikato.ac.nz> wrote: >In article <··················@newshost>, .... > >for safety you may want to copy the rest-list: > >(defun curry (fn &rest curried-args) > (setq curried-args (copy-list curried-args)) > #'(lambda (&rest args) > (apply fn (append curried-args args)))) Unless args is NIL, the append above will effectively "copy" curried-args. ( and may do so regardless but that's probably implementation dependant. I think the standard allows append may return a result that is "eq" with either arg if the other arg is NIL. Otherwise the first argument is duplicated. Substitute nconc for append above and yes there may be some safety problems.) Also if curried-args is in "danger", why isn't args? > >and for efficiency (if you call the curried function a lot) use: > >(defun curry (fn &rest curry-args) > (compile nil > (lambda (&rest other-args) > (apply ',fn > ,@(loop for x in curry-args collect (list 'quote x)) > other-args)))) Errr, you can quote functions?? ? (defun tester2 ( &rest curry-args ) (loop for x in curry-args collect (list 'quote x ))) TESTER2 ? (tester2 1 2 3 ) ('1 '2 '3) ? (tester2 #'car '(1 2 )) ('#<Compiled-function CAR #x65846> '(1 2)) ? (funcall (first *) (second *)) > Error: '#<Compiled-function CAR #x65846> can't be FUNCALLed or APPLYed. > While executing: CCL::TOPLEVEL-EVAL > Type Command-. to abort. See the RestartsI menu item for further choices. 1 > Aborted ? -- Lyman S. Taylor "Any sufficiently advanced technology is (·····@cc.gatech.edu) indistinguishable from a rigged demo. " -- paraphrased Arthur C. Clarke seen somewhere on the USENET From: Lyman S. Taylor Subject: Re: Curry (was Re: Elegant solution asked) Date: Tue, 11 Mar 1997 00:00:00 +0000 Message-ID: <5g4bn3$1j6@pravda.cc.gatech.edu>
In article <··········@saturn.cs.waikato.ac.nz>,
Bernhard Pfahringer <········@saturn.cs.waikato.ac.nz> wrote:
>In article <··················@newshost>,
....
>
>for safety you may want to copy the rest-list:
>
>(defun curry (fn &rest curried-args)
>  (setq curried-args (copy-list curried-args))
>  #'(lambda (&rest args)
>      (apply fn (append curried-args args))))

Unless args is NIL, the append above will effectively "copy" curried-args.
( and may do so regardless but that's probably implementation dependant.
I think the standard allows append may return a result that is "eq" with
either arg if the other arg is NIL. Otherwise the first argument is
duplicated.  Substitute nconc for append above and yes there may be some
safety problems.) Also if curried-args is in "danger", why isn't args?

--

Lyman S. Taylor          "Any sufficiently advanced technology is
(·····@cc.gatech.edu)   indistinguishable from a rigged demo. "
-- paraphrased Arthur C. Clarke
seen somewhere on the USENET
From: Jason Trenouth
Subject: Re: Curry (was Re: Elegant solution asked)
Date: Wed, 12 Mar 1997 00:00:00 +0000
Message-ID: <3326a5e1.186796018@newshost>
On 11 Mar 1997 13:44:31 +1300, ········@saturn.cs.waikato.ac.nz (Bernhard
Pfahringer) wrote:

> In article <··················@newshost>,
> Jason Trenouth <·····@harlequin.co.uk> wrote:
> > ...
> >You want CURRY, which could be defined as follows:
> >
> >(defun curry (fn &rest curried-args)
> >  #'(lambda (&rest args)
> >      (apply fn (append curried-args args))))
> > ...
>
> for safety you may want to copy the rest-list:
>
> (defun curry (fn &rest curried-args)
>   (setq curried-args (copy-list curried-args))
>   #'(lambda (&rest args)
>       (apply fn (append curried-args args))))

APPEND is already copies the list.

> and for efficiency (if you call the curried function a lot) use:
>
> (defun curry (fn &rest curry-args)
>   (compile nil
> 	   (lambda (&rest other-args)
> 	      (apply ',fn
> 		     ,@(loop for x in curry-args collect (list 'quote x))
> 		     other-args))))
>
> should cons less in for most CL implementations

A simpler approach would be to make CURRY a macro instead:

(defmacro curry (fn &rest curried-args)
#'(lambda (&rest args)
(apply ,fn ,@curried-args args)))

__Jason
From: Erik Naggum
Subject: Re: Curry (was Re: Elegant solution asked)
Date: Wed, 12 Mar 1997 00:00:00 +0000
Message-ID: <3067167916417343@naggum.no>
* Jason Trenouth
| > (defun curry (fn &rest curried-args)
| >   (setq curried-args (copy-list curried-args))
| >   #'(lambda (&rest args)
| >       (apply fn (append curried-args args))))
|
| APPEND is already copies the list.

append' would copy curried-args, but not args.  I believe this was the
issue, since you take pains to copy the first argument list (as I believe I
did first in this discussion and everybody just copied).

I thought it was necessary to copy the rest list, as I recall having read
that the trivial definition of list' would not be conforming:

(defun list (&rest args)
args)

however, I was in error.  there is no mention of stack-allocating rest
lists in ANSI X3.226, except under the dynamic-extent' declaration, with
which it may be requested specially.  under apply', we find the following:

When the function receives its arguments via &rest, it is permissible
(but not required) for the implementation to bind the rest parameter to
an object that shares structure with the last argument to apply.
Because a function can neither detect whether it was called via apply
nor whether (if so) the last argument to apply was a constant,
conforming programs must neither rely on the list structure of a rest
list to be freshly consed, nor modify that list structure.

the X3J13 issue REST-LIST-ALLOCATION contains a lot of discussion, see
<URL:http://www.harlequin.com/books/HyperSpec/Issues/iss297-writeup.html>.
CLtL2 includes the following about this issue (taken from the published TeX
sources).

\begin{new}
X3J13 voted in January 1989
\issue{REST-LIST-ALLOCATION}
to clarify that if a function has a {\it rest} parameter and is called
using \cd{apply}, then the list to which the {\it rest} parameter is
bound is permitted, but not required, to share top-level list structure
with the list that was the last argument to \cd{apply}.  Programmers
should be careful about performing side effects on the top-level list
structure of a {\it rest} parameter.

This was the result of a rather long discussion within X3J13 and the
wider Lisp community.  To set it in its historical context, I must
remark that in Lisp Machine Lisp the list to which a {\it rest}
parameter was bound had only dynamic extent; this in conjunction with
the technique of cdr-coding'' permitted a clever stack-allocation
technique with very low overhead.  However, the early designers of
Common Lisp, after a great deal of debate, concluded that it was
dangerous for cons cells to have dynamic extent; as an example, the
obvious'' definition of the function \cd{list}
\begin{lisp}
(defun list (\&rest x) x)
\end{lisp}
could fail catastrophically.  Therefore the first edition simply
implied that the list for a {\it rest} parameter, like all other lists,
would have indefinite extent.  This still left open the flip side of
the question, namely, Is the list for a {\it rest} parameter guaranteed
fresh?  This is the question addressed by the X3J13 vote.  If it is
always freshly consed, then it is permissible to destroy it, for
example by giving it to \cd{nconc}.  However, the requirement always to
cons fresh lists could impose an unacceptable overhead in many
implementations.  The clarification approved by X3J13 specifies that
the programmer may not rely on the list being fresh; if the function
was called using \cd{apply}, there is no way to know where the list
came from.
\end{new}

the index to issues lists this as having been voted MAY-SHARE, that is:

(defvar *my-list* '(a b c))
(defun foo (&rest x) (eq x *my-list*))
(apply #'foo *my-list*) => implementation-dependent

in any case, it seems that the need to copy the top-level list structure of
the rest list is not necessary unless the list structure will be modified,
which we don't.  for reference, this is the function definition from Paul
Graham's ANSI Common Lisp.  his Dylan function buildrs go like this (from
figure 6.2, page 110),

(defun compose (&rest fns)
(destructuring-bind (fn1 . rest) (reverse fns)
#'(lambda (&rest args)
(reduce #'(lambda (v f) (funcall f v))
rest
:initial-value (apply fn1 args)))))

(defun disjoin (fn &rest fns)
(if (null fns)
fn
(let ((disj (apply #'disjoin fns)))
#'(lambda (&rest args)
(or (apply fn args) (apply disj args))))))

(defun conjoin (fn &rest fns)
(if (null fns)
fn
(let ((conj (apply #'conjoin fns)))
#'(lambda (&rest args)
(and (apply fn args) (apply conj args))))))

(defun curry (fn &rest args)
#'(lambda (&rest args2)
(apply fn (append args args2))))

(defun rcurry (fn &rest args)
#'(lambda (&rest args2)
(apply fn (append args2 args))))

(defun always (x) #'(lambda (&rest args) x))

#\Erik
--
how to beat Microsoft, death, and poverty: in July 1994, there were more
references to my name (3039) in gopherspace than to Microsoft (2557), death
(2530), and poverty (2410).  (http://veronica.sonoma.edu:8001/top1000.html)
From: Tom Kramer
Subject: Re: Elegant solution asked
Date: Tue, 11 Mar 1997 00:00:00 +0000
Message-ID: <5g3pcl\$f7b3@news.nist.gov>
In article ····@wrq.com, marisal <·······@wrq.com> () writes:
> Very often I need a function to map a 2 argument function over a list and
> a fixed argument. For example, if we call such function map1:
> (map1 #'list 'z '(a b c)) should return: '((z a) (z b) (z c))
>
> Can anyone suggest an elegant solution for this. The best I could come up
> with was:
>
> (defun map1 (function fixed-argument list)
>     (mapcar (lambda (element) (funcall fn fixed-argument element)) list))
>
> This works fine, but I have the gut feeling that there must be a
> better/simpler way. Any ideas?
> Thanks in advance.
(mapcar #'(lambda (x) fixed-argument) list) list))