Toolchest: Shortcuts for higher-order functions
Introduction
There’s a balance that a programmer has to find. A good programmer finds the method of expression that best fits his/her need. When there’s a need for the fastest possible code, the programmer finds it. When there’s a need for readable code, he/she will make forgo clever solutions and opt for clarity. When power or expressiveness is required, he/she will use the tools at his/her disposal in harmonious combination.
To know this balance, one must inventory the different methods available. One must know each method’s strengths and weaknesses. And one must be able to see the problem in many ways.
I’m quite interested in the study of the art of programming. I know I try to better myself continually. I often try out different ways of expressing the same functions.
I would like to present some higher-order functions in different representations and analyse the pros and cons of using each type of form. There are some macros used below. I’ve stored the code for them. This post was inspired by (code) vs ‘(data).
(mapcar #'(lambda (x)
(* 2 x))
'(1 2 3))
Plus
- This is the standard, canonical form for representing one-use functions. Most everyone will understand it.
- It can represent any kind of function definable, except recursive functions.
Minus
- It is long-winded for what it does.
- With the same amount of writing, you might as well do a defun
(loop for x in '(1 2 3)
collect (* 2 x))
Plus
- Also a standard. Everyone will understand it.
- More succinct and direct than the map-lambda.
Minus
- It neglects the higher-order possibilities.
- It could be more simple and direct.
Interesting
- Since this is a simple example, it doesn’t demonstrate the power of the loop macro.
(mapcar #L(* 2 _) '(1 2 3))
Plus
- Shorter and more succinct.
- Can work on any form, even a macro. #L(if (evenp _) _ (* 2 _))
- Most lambdas are single-argument (think find-if, remove-if, mapcar of one list, etc)
- Recommended by Peter Norvig
Minus
- It’s not widely used, so it might be hard for someone to understand at first glance.
- Can only be used for functions of one argument.
Interesting
- Could someone write one that could figure out _1 _2 . . . _N variables?
(defun double (x) (* 2 x)) (mapcar #'double '(1 2 3))
Plus
- The DEFUN of course will be away from the MAPCAR form — the MAPCAR form is nice and clean.
- DOUBLE can be used elsewhere.
- Very readable
Minus
- Very long for one-off functions.
- Need a #’ or at minimum ‘
Interesting
- This is the kind of thing that results from refactoring code.
(mapcar (curry #'* 2) '(1 2 3))
Plus
- CURRY expresses this function perfectly.
Minus
- Not very common, so it’s not readable by all.
- #’ syntax gets in the way.
- I wouldn’t use it since the form is a bit clunky.
Interesting
- Curry is a mathematical idea.
;; Where #R expands to a CURRY form. (mapcar #R(* 2) '(1 2 3))
Plus
- No #’.
- (* 2) looks like a function call
- Very short
- Composable with COMPOSE macro below
- I would use this
Minus
- Not widely used — it makes it harder for others to understand it at first glance.
I would also like to analyze
(mapcar #'(lambda (x y)
(abs (/ x y)))
'(1 -2 3 -4)
'(2 -9 -8 2))
Compared to
(mapcar (compose #'abs #'/)
'(1 -2 3 -4)
'(2 -9 -8 2))
Plus
- COMPOSE expresses this function perfectly. Function composition is precisely what you want.
Minus
- Not very common, so it’s not readable by all at first glance.
- #’ syntax gets in the way.
- I wouldn’t use this, either
Interesting
- Function composition is also a mathematical idea.
;; #M expands to compose form
(mapcar #M(abs /)
'(1 -2 3 -4)
'(2 -9 -8 2))
Plus
- COMPOSE expresses this function perfectly.
- Smaller and simpler than the full COMPOSE form
- No #’
- I would use this.
- Composabe with CURRY macro above
Minus
- Not very common, so it’s not readable by all.
Popularity: 3% [?]
Filed under opinions |20 Responses to “Toolchest: Shortcuts for higher-order functions”
Leave a Reply
> Could someone write one that could figure out _1 _2 . . . _N variables?
Arnesi has a #L reader macro that does that:
(mapcar #L(+ !1 !2) ‘(1 2 3) ‘(4 5 6))
I had this thought about renaming |lambda| to |for| when thinking about language design. Seems to make much clearer code for me.
(mapcar #’(for (x)
(* 2 x))
‘(1 2 3))
I like your post. It made this idea pop up in my mind that after all a language (lisp) needs syntax. Syntax that would be crafted to make the style of programming the language promotes very succinct and easy.
Hi,
(mapcar (curry #’* 2) ‘(1 2 3))
If you define curry as a macro, you don’t need the #’ and it will look cleaner. Also, I don’t thionk curry is obscure these days with so many people talking about Haskell…
I don’t understand how one uses the form:
(mapcar #L(* 2 _) ‘(1 2 3))
in a standard CL. With both ABCL and SBCL I get errors about “no dispatch function defined for #\L”.
There is additional code required, right? Or am I being really dense?
–
“This is not a disentanglement from, but a progressive knotting-into.”
How about this, straight from srfi?
(defmacro cut (fn &rest expr)
(loop
with rest-sym
for i in expr
for sym = (when (and (symbolp i)
(string= “” i))
(gensym))
when (and (symbolp i) (string= “” i))
do (setf rest-sym (gensym)) (loop-finish)
collect (or sym i) into expr-list
nconc (if sym (list sym) nil) into lambda-list
finally (return
`(lambda (,@lambda-list
,@(if rest-sym (list ‘&rest rest-sym) nil))
,(if rest-sym
`(apply #’,fn ,@expr-list ,rest-sym)
`(,fn ,@expr-list))))))
The infix parameter (whose presence signals an error in the #L in the paste) could be used to designate how many variables should be present. Also, (lambda (..) …) is generated without a leading #’ , #nL(..) can be the car of a form. E.g.,
(set-dispatch-macro-character
#\# #\L #'(lambda (stream sub-character infix-parameter)
(let ((args (if (null infix-parameter)
(list (intern "_"))
(loop for i from 0 below infix-parameter
collect (intern
(concatenate
'string "_"
(write-to-string i)))))))
`(lambda ,args
,(read stream t nil t)))))
;; #2L can appear at the beginning of a form.
;; (#2L(+ _0 _1) 2 2) => 4
I could also imagine generating functions that can take any number of arguments, but that name the first n, e.g.,
#2L( ... )
=>
(lambda (_0 _1 &rest _rest)
...)
or the whole arglist could be taken and destructured:
#2L( ... )
=>
(lambda (&rest _args)
(destructuring-bind (_0 _1 &rest _rest) _args
...)
I may add this idiom to mine own toolkit.
FOR is not a good name, it promotes the view tha lambdas are only good for iterators and not “real” computation. It’s not true. They have many, many more uses, iterating is only one of them and probably not the most significant. If you want succint, you can just use one of the many #L syntaxes.
Besides, if you’re unfamiliar with lambda, it stands out and is very easy to look up. FOR would have neither of those qualities.
FOR seems to me the way a direct definition of a mathemacical function is formulated: FOR all x in..:f(x) = …
I could even imagine using it to define functions in general. Like lambda is used in scheme sometimes.
(defun double (for (x) (* 2 x)))
Regarding the “defun” approach, the definition of the function can also be a local definition, using LABELS or FLET.
Thanks for this post - it formalised a lot of the idioms i have been using - and informed me about other alternatives.
I’d just use (mapcar (lambda (x) (* x 2)) list). If that’s too “long-winded”, I suggest you give pretty-lambdas.el a try.
@Mark: There’s some extra code required. I linked to it in the introduction, but here it is again:
http://paste.lisp.org/display/52651
Here’s is another implementation of cut/cute based closely on the srfi-26 reference implementation: http://paste.lisp.org/display/52700
#L being CURRY asks for a RCURRY companion, but #R is already taken..
Ok, I messed up the letters in the previous comment, but the problem should be obvious by now — that specific choice of letters isn’t providing a terribly clear idea about what’s happening.
Here is a description and explanation of the CUT macro:
http://srfi.schemers.org/srfi-26/srfi-26.html
@_deepfire: Any suggestions for a choice of letters?
I don’t understand why anybody would choose ‘for’ if aiming for conciseness: It is neither particularly short nor descriptive (if three-letter names are necessary (it eludes me why that might be), ‘fun’ strikes me as a better compromise).
Why not use the Greek lambda character (λ) itself? Any useful editor or operating system should provide shortcuts to insert that character with at most two keystrokes.
But since I’ve never found it a problem to type out ‘lambda’, I prefer Emacs’ pretty-lambda mode: You type (lambda (x) …) and it displays as (λ (x) …) — the actual source code is not modified, only the way ‘lambda’ is displayed on screen. This works with all existing code, it doesn’t require any custom set-up other than a line or two in your .emacs, and it doesn’t confuse anybody else reading your code.
Why not:
(mapcar (* 2 _) ‘(1 2 3))
?
Lambda can indeed be used to represent recursive functions. That is the point of the Y combinator, after all. Although your point is still well taken for every day programming. The recursive representation of factorial using only lambdas - no side effects in the environment - is not the first way most people would think to do it. So when you say ‘cannot be used to represent recursive functions’, I agree if you mean ‘no sane person would use it to represent recursive in code other people would read’. But in an absolute sense, you CAN represent recursive functions using lambdas.