A language has support for first class functions if it is possible
to use a function as a regular value, i.e. if it is possible to pass
a function to another function, or return it from a function.
In a language with first class functions, it is therefore possible
to define the concept of higher order function is: a function which accepts
in input or returns in output (or both) another function.
Various imperative languages have support for higher order functions:
all the scripting languages, the latest version of C#, Scala,
and a few others. Still, functional languages have a better support
and higher order functions are used in those language much more
that in imperative languages. This is especially true for languages
such as ML and Haskell, which support curried functions out of the
box: in such languages all functions are really unary functions (i.e. they
accept a single argument) and functions of n arguments are actually
unary functions returning closures. In Scheme this behavior can be
emulated with macros. Here is an example of how one
could define curried functions in Scheme:
(sub (curried-lambda () b b* ...)
#'(begin b b* ...))
(sub (curried-lambda (x x* ...) b b* ...)
#'(lambda (x) (curried-lambda (x* ...) b b* ...)))
(def-syntax (define-curried (f x ...) b b* ...)
#'(define f (curried-lambda (x ...) b b* ...)))
define-curried defines a function with (apparently) n arguments
as an unary function returning a closure, i.e. a function with (apparently)
n-1 arguments which in turns is an unary function returning a closure
with n-2 arguments and so on, until it returns an unary function.
For instance, the following add function
(define-curried (add x y) (+ x y))
apparently has two arguments, but actually it is an unary function
returning an unary closure:
> (add 1)
> ((add 1) 2)
You can see how the macro works by using syntax-expand:
> (syntax-expand (curried-lambda (x y) (+ x y)))
(lambda (x) (curried-lambda (y) (+ x y)))
The internal curried-lambda has a single argument in this case
and thus expands to a regular lambda function, but you can see that
in general you will have a tower of nested lambdas, which dept is equal
to the number of arguments.
Whereas it is possible define curried functions in Scheme, usually
this is not very convenient, unless you are trying to
emulate ML or Haskell idioms. Out of the box, Scheme supports
functions with multiple arguments in a traditional fashion, i.e.
the same as in Python: thus, the most convenient construct is not currying,
but partial application. The Pythonistas here will certainly think
of functools.partial, an utility which was added to the standard
library starting from Python 2.5. Schemers have something similar
(but of course better) in the form of SRFI-26, i.e. the cut and cute
macros by Al Petrofsky.
Instead of spending too many words, let me show an example of how
partial function application works both in Python and in Scheme.
Here is the Python version:
>>> from functools import partial
>>> from operator import add
>>> add1 = partial(add, 1)
and here is the Scheme version:
> (import (srfi-26)); assuming it is available in your implementation
> (define add1 (cut + 1 <>))
> (add1 2)
In Python, partial(add,1) returns an unary callable object that adds 1
to its argument; in Scheme, (cut+1<>) returns an unary function
that does the same. The Scheme version is better, since the
arguments of the resulting functions are immediately vas visible as
slots (i.e. the <> symbol). For instance
has two slots and therefore is a function of two arguments:
> (greetings "Michele" "Mario")
"hello Michele and Mario"
It is also possible to define a variable number of arguments
by using the rest-slot symbol <...>:
> (define greetings (cut string-append "hello " <> " and " <...>))
> (display (greetings "Michele" "Mario" "\n"))
hello Michele and Mario
We can even use a slot for the function: for instance, the higher order
function apply could be implemented as (cut<><...>).
Moreover, there is a cute macro which acts exactly as cut, with a single
difference: the arguments in cute are evalued only once (the e stands
for evalued), whereas cut is not safe against multiple
evaluation. In particular, if you define
A couple of commonly used higher order functions in Scheme and
other functional languages are fold-left and fold-right.
They entered in the R6RS standard, but they are also available from SRFI-1,
therefore you can leverage on them even if you are using an R5RS Scheme.
fold-left and fold-right will remind Pythonistas of reduce,
which is also a folding function. However, it is well known that Guido
dislikes it and nowadays reduce is no more a builtin (in Python 3.0);
it is still available in the functools module, though.
For some reason (probabily the order of the arguments which I cannot
remember) I cannot use reduce in Python, whereas I have less
problems with fold-left e fold-right in Scheme and other
fold-left and fold-right have a
nearly identical API: both allow to traverse a list by accumulating
values and by returning at the end the final accumulator.
For instance, if you want to sum the values of list, here is
an idiomatic solution in Scheme (another one is
> (fold-left + 0 '(1 2 3)); sum all elements starting from 0; fold-right works too
In general, the function in fold-left takes N + 1 arguments, where
N is the number of lists you are looping over (usually N = 1)
and the leftmost argument is the accumulator. The same is true for
fold-right, but then the rightmost argument is the accumulator.
Notice that fold-left is quite different from fold-right, since they
work in opposite order:
In the first case fold-left loops from left to right
(the element 1 is the first to be consed, the element 2 is the second
to be consed, and the element 3 is the last to be consed, so that
the final result is (cons3(cons2(cons1'()))) i.e. (321))
whereas in the second case fold-right loops from right to left.
In order to give an example of use, here is how you could
define a flattening procedure by using fold-right:
(define (flatten lst)
(lambda (x a)
(if (list? x) (append (flatten x) a) (cons x a))) '() lst))
You can check that it works with a few tests:
(test "flatten null"
(test "flatten plain"
(flatten '(a b c))
'(a b c))
(test "flatten nested"
(flatten '((a b) (c (d e) f)))
'(a b c d e f))
Here is another example, a function to remove duplicates from a list:
Notice the use of cut to define an unary function (cuteq?<>el)
which checks if its argument is equal - according to the provided equality
function - to a given element el. exists is one of the
list processing utilities standardized by the R6RS document.
Here is a test:
Having first class functions in a language means much more than having
map, filter or fold. Perhaps in the future I will add another episode
about advanced usage of functions, such a parsing combinators or formatting
combinators; for the moment what I said here should be enough, and
the next episode will be devoted to another typical feature of functional
languages: pattern matching.
Cute! It's fun to see examples of similar functions/techniques in different languages. And thanks for the little lesson on Python's functools.partial. My Python skills are way behind the times.
> For some reason (probabily the order of the arguments which I cannot remember) I cannot use reduce in Python, whereas I have less problems with fold-left e fold-right in Scheme and other functional languages.
Now I'm curious. Can you say more about your reduce problems?
> For some reason (probabily the order of the arguments > which I cannot remember) I cannot use reduce in Python, > whereas I have less problems with fold-left e fold-right > in Scheme and other functional languages. > > Now I'm curious. Can you say more about your > reduce problems?
map and filter in Python have signature map(function, sequence, ...), the same as in Scheme. reduce instead has a different signature: reduce(binary_op, sequence, seed) I would expect (as done consistently in Scheme) a signature reduce(function, seed, sequence, ...) so I get confused all the time. Also, the seed is optional in Python. Notice that I learned Scheme after Python, so it is not a matter of previous familiarity with a given syntax, it is a matter of (in)consistency.