Home > Archive > Scheme > November 2005 > "function producing" functions
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
"function producing" functions
|
|
| caytupu 2005-11-15, 7:03 pm |
| Hi. Iam a first year computer science student. Can someone please
explain me how this piece of code works or what it means?
Our teacher wanted to define a general function for things like double,
triple etc..
So he defined n-ple by using a function producing function.
;; n-ple number -> function
;; create a function whose value is the product of its parameter with n
(define n-ple
(lambda (n)
(lambda (x)
(* x n))))
I just can't see how it works.
| |
| Ray Dillinger 2005-11-15, 9:58 pm |
| caytupu wrote:
> Hi. Iam a first year computer science student. Can someone please
> explain me how this piece of code works or what it means?
>
> Our teacher wanted to define a general function for things like double,
> triple etc..
> So he defined n-ple by using a function producing function.
>
> ;; n-ple number -> function
> ;; create a function whose value is the product of its parameter with n
> (define n-ple
> (lambda (n)
> (lambda (x)
> (* x n))))
>
> I just can't see how it works.
Well, this looks like a classic generalization; you start
with functions like
(define x2 (lambda (n) (* 2 n))) ;; take one arg, return its doubling
(define x3 (lambda (n) (* 3 n))) ;; ditto, return its tripling
(define x4 (lambda (n) (* 4 n))) ;; ditto, return its quadrupling
(define x5 (lambda (n) (* 5 n))) ;; ditto, return its quintupling
and it's really looking like you have a redundant pattern here,
right? The only difference between these functions is the number
that gets plugged in. So, if you want to generalize, you just
create a function that takes an argument to plug in, and returns
functions like this when it's called. And that is the function
your teacher defined.
(define multiplier (lambda (x) ;; take one arg and call it x
(lambda (n) (* x n)))) ;; Return a function that takes
;; one arg n and returns the product
;; of n and x
Now you have the situation where
(define x2 (lambda (n) (* 2 n)))
and
(define x2 (multiplier 2))
are equivalent; They both bind x2 to a function of one
parameter that returns the doubling of that parameter.
The difference is that the first uses (lambda ...) the
native function-creating function, and the second uses
(multiplier ...), a special-purpose function-creating
function that you've defined.
The double use of lambda may be confusing you; if so,
here's another way of writing multiplier that makes
returning a function slightly more explicit by first
defining a "local variable" within multiplier to hold
its value.
(define multiplier (lambda (x)
(define subfunction (lambda (n)
(* x n)))
subfunction))
This creates a function named subfunction, within the
scope of multiplier. So every time multiplier is called,
subfunction acquires a definition depending on the
parameter x that's passed to multiplier.
And then instead of doing anything else, we just return
the value of subfunction.
Remember that lambda expressions return values. Defining
something to return the result of evaluating a lambda
expression is no different in principle from defining it
to return the result of evaluating an addition expression.
The only difference is that an addition expression returns
a number and a lambda expression returns a function.
Multiplier, the way your teacher defined it, used a lambda
expression directly; it wasn't bound to any variable, so
it was a "function without a name" in the same way that
the result of an addition expression where you don't hold
it in a variable is a "number without a name."
(define add2 (lambda (x) (+ 2 x)))
isn't very mysterious, is it? We're returning the result
of evaluating an addition expression, which we didn't bother
to allocate a local variable to hold. Well, the function
(multiplier) is the same, except it's returning the result of
evaluating a lambda expression that _it_ didn't allocate a
local variable to hold.
These "anonymous functions" are a way to do some
very  things.
In order to "get it," you need to get used to the idea
that a function is just a value, like 3 or "foo" or #t
or any other value. And a named function is just a
variable whose value happens to be a function instead of
a value of some other type.
Bear
| |
| Pascal Bourguignon 2005-11-16, 7:59 am |
| "caytupu" <tylose@gmail.com> writes:
> Hi. Iam a first year computer science student. Can someone please
> explain me how this piece of code works or what it means?
>
> Our teacher wanted to define a general function for things like double,
> triple etc..
> So he defined n-ple by using a function producing function.
>
> ;; n-ple number -> function
> ;; create a function whose value is the product of its parameter with n
> (define n-ple
> (lambda (n)
> (lambda (x)
> (* x n))))
>
> I just can't see how it works.
Perhaps with the classical mathematical notation:
n-ple : R ----> Rē
n |---> f_n : R ----> R
x |---> x*n
n-ple is a funtion that takes a number n, and returns a function f_n.
This function f_n takes a number x and returns x*n.
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
| |
| Jussi Piitulainen 2005-11-16, 7:59 am |
| Pascal Bourguignon writes:
> caytupu writes:
>
>
> Perhaps with the classical mathematical notation:
>
> n-ple : R ----> Rē
> n |---> f_n : R ----> R
> x |---> x*n
>
> n-ple is a funtion that takes a number n, and returns a function
> f_n. This function f_n takes a number x and returns x*n.
The type is actually C --> (C --> C). With R --> (R * R), the value
should be a pair of numbers, not a function. (And Scheme does complex
numbers.)
A barred arrow notation that exactly matches the actual lambda
expression would be n |-> (x |-> x * n).
Here's something concrete for caytupu to contemplate, possibly a bit
ahead of time:
(define mean (lambda (xs) (/ (apply + xs) (length xs))))
(define diff (lambda (m) (lambda (x) (- x m))))
(let ((xs '(1 2 3 3 3 4 5))) (map (diff (mean xs)) xs))
| |
| Pascal Bourguignon 2005-11-16, 7:59 am |
| Jussi Piitulainen <jpiitula@ling.helsinki.fi> writes:
> Pascal Bourguignon writes:
>
>
> The type is actually C --> (C --> C). With R --> (R * R), the value
> should be a pair of numbers, not a function. (And Scheme does complex
> numbers.)
You're right, I meant 2^R, not R^2.
> A barred arrow notation that exactly matches the actual lambda
> expression would be n |-> (x |-> x * n).
>
> Here's something concrete for caytupu to contemplate, possibly a bit
> ahead of time:
>
> (define mean (lambda (xs) (/ (apply + xs) (length xs))))
> (define diff (lambda (m) (lambda (x) (- x m))))
> (let ((xs '(1 2 3 3 3 4 5))) (map (diff (mean xs)) xs))
--
"Indentation! -- I will show you how to indent when I indent your skull!"
| |
| Charles Hoffman 2005-11-16, 7:59 am |
| caytupu wrote:
> Hi. Iam a first year computer science student. Can someone please
> explain me how this piece of code works or what it means?
>
> Our teacher wanted to define a general function for things like double,
> triple etc..
> So he defined n-ple by using a function producing function.
>
> ;; n-ple number -> function
> ;; create a function whose value is the product of its parameter with n
> (define n-ple
> (lambda (n)
> (lambda (x)
> (* x n))))
>
> I just can't see how it works.
>
Might help to see how you'd use it... For example, since this function
returns a function as output, you could assign a name to that returned
function so you can use it by that name afterward:
> (define double (n-ple 2))
> (define triple (n-ple 3))
> (triple 5)
15
> (double 36)
72
> (triple (double 4))
24
While this would be the most common thing way you'd use a
function-producing-function, you can also use the returned function in
place, (though in this case it just becomes a longer way to multiply two
numbers ;-) ):
> ((n-ple 4) 7)
28
> (= ((n-ple 4) 7) (* 4 7))
#t
This is a simple example of a thing called "currying." Currying is when
you take a multiple-argument function and vales to be used as _some_ of
its arguments, and use this to create a function that is the same
function but now with those arguments already filled in and still
requiring only the rest of them. In this case, we've taken a
two-argument function * (actually * is n-ary but we tend to think of it
as two arguments and use it the most that way ;) ) and a value for one
argument n, and made from them a function that takes one argument and
puts it in the * function with the n already filled in ahead-of-time.
--ch--
| |
| Jussi Piitulainen 2005-11-16, 7:59 am |
| Pascal Bourguignon writes:
> Jussi Piitulainen writes:
>
> You're right, I meant 2^R, not R^2.
Don't you still mean R^R, as an alternative notation to R --> R? I've
seen 2 identified with the set of truth values and 2^B identified with
the power set of B, and more generally A^B identified with the set of
functions from A to B, which is what we have here with A = B. Hm. Was
I, too, too quick in interpreting R^2 as R * R?
(And R --> R^R mixes the two notations, which I find funny, but I'm
easily amused.)
| |
| Lauri Alanko 2005-11-17, 3:57 am |
| In article <qotr79gg0ug.fsf@venus.ling.helsinki.fi>,
Jussi Piitulainen <jpiitula@ling.helsinki.fi> wrote:
> Don't you still mean R^R, as an alternative notation to R --> R? I've
> seen 2 identified with the set of truth values and 2^B identified with
> the power set of B, and more generally A^B identified with the set of
> functions from A to B,
No, A^B is the set of functions from B to A. Similarly, like you said,
2^B represents the powerset of B: 2^B is B->2 (or B->Bool), the set of
characteristic functions of subsets of B.
The correspondence between A->B and B^A is maybe easier to see if you
think of A->B as a shorthand for "Pi(x in A).B", i.e. a non-dependent
product.
Lauri
| |
| Jussi Piitulainen 2005-11-17, 3:57 am |
| Lauri Alanko writes:
> Jussi Piitulainen wrote:
>
> No, A^B is the set of functions from B to A. Similarly, like you
> said, 2^B represents the powerset of B: 2^B is B->2 (or B->Bool),
> the set of characteristic functions of subsets of B.
Oops, thank you. I would have noticed my mistake if I had tried to
rewrite 2^B as 2 --> B, which is obviously wrong. But I didn't.
Happily, R^R is the same either way.
> The correspondence between A->B and B^A is maybe easier to see if
> you think of A->B as a shorthand for "Pi(x in A).B", i.e. a
> non-dependent product.
I don't know what non-dependent means here, but otherwise, yes, it's
just like a vector in R^n can be identified with a function from
{1,...,n} to R.
| |
| Bruce Lewis 2005-11-17, 7:58 am |
| "caytupu" <tylose@gmail.com> writes:
> Hi. Iam a first year computer science student. Can someone please
> explain me how this piece of code works or what it means?
>
> Our teacher wanted to define a general function for things like double,
> triple etc..
> So he defined n-ple by using a function producing function.
>
> ;; n-ple number -> function
> ;; create a function whose value is the product of its parameter with n
> (define n-ple
> (lambda (n)
> (lambda (x)
> (* x n))))
>
> I just can't see how it works.
Knowing how it works requires knowing the pronunciation. I assume you
already know how "define" is pronounced. You prounounce
"(lambda (x) y)" as "a function consuming x, producing y". You
pronounce "*" as "the product of".
The function above is pronounced
define n-ple as
a function consuming n, producing
a function consuming x, producing
the product of x and n.
Now does the description of n-ple as a function-producing function make
sense?
|
|
|
|
|