Scheme - compose many functions

Author

compose many functions

Ognen Duzlevski

2004-12-15, 4:00 pm

Hi,

I am teaching myself scheme (using scheme48 and the "Scheme and Art of Programming" book).

I have the following composition function:

; define a procedure that composes three functions on one input variable
(define compose3
(lambda (f g h)
(lambda (x)
(f (g (h x)))
)
)
)

This functions works OK, now I try to generalize to any number of functions.
I tried first just to see if it will work on the first two using car and cdr and it does:

(define mytest
(lambda arg
(lambda (x)
(else ((car arg) ((car (cdr arg)) x)))
)
)
)

(define add1 (lambda (x) (+ x 1)))
(define sub3 (lambda (x) (- x 3)))
(define mul2 (lambda (x) (* x 2)))
(define div4 (lambda (x) (/ x 4)))

> ,load ex73.scm
> ((mytest add1 sub3 mul2 div4) 10)
8

However, I am stuck in generalizing this to any number of functions passed. Basically, I can recurse
back on mytest above and test for (null? arg) as a base condition, but what do I return? Can anyone
offer any hints?

This is not a homework, I am out of school for some time and I am not looking for someone to solve my
problem by giving me ready-to-run code. I am trying to teach myself so hints would be more welcome :)
Or good explanation of what I am not getting :)

Thanks,
Ognen

P.S. Scheme rules, I love it every day more and more

Cláudio F. Gil

2004-12-15, 4:00 pm

Ognen Duzlevski wrote:
>8

Well, didn't understood the example since I was expecting 3 as result of
(add1 (sub3 (mul2 (div4 10)))).

> However, I am stuck in generalizing this to any number of functions
> passed. Basically, I can recurse back on mytest above and test for (null?
> arg) as a base condition, but what do I return? Can anyone offer any
> hints?

You could use the identity function in the basic case.
It would look like

> (define (mytest . arg)
____(cond_((null?_arg)
___________(lambda_(x)_x))
__________(else_
___________(lambda_(x)
_____________((car_arg)_((apply_mytest
________________________________(cdr_arg
))
_________________________x))))))

> ((mytest add1 sub3 mul2 div4) 10)
3

Try searching Google(tm) for "Curry"
http://www.google.com/search?q=curry+scheme.

Anton van Straaten

2004-12-15, 4:00 pm

Ognen Duzlevski wrote:
> However, I am stuck in generalizing this to any number of functions
passed.
> Basically, I can recurse back on mytest above and test for (null? arg) as
a
> base condition, but what do I return? Can anyone offer any hints?

The logic of base cases in recursive functions tends to be deceptively
simple. In this case, to figure out what the base case should be, ask
yourself what ((mytest) x) should return.

However, once you've figured that out, you'll find it will help to structure
the procedure in such a way that returning the desired value makes sense
(IOW, a bottom-up design). To make it easier to think about this, define a
helper procedure within mytest to perform the actual recursion. The helper
procedure will allow you to use whatever arguments and return value seems
most appropriate, without affecting the signature of the outer procedure.
You can always optimize this helper procedure away later if it seems
appropriate (or possible!)

Anton

Ognen Duzlevski

2004-12-15, 4:00 pm

Anton van Straaten <anton@appsolutions.com> wrote:
> However, once you've figured that out, you'll find it will help to structure
> the procedure in such a way that returning the desired value makes sense
> (IOW, a bottom-up design). To make it easier to think about this, define a
> helper procedure within mytest to perform the actual recursion. The helper
> procedure will allow you to use whatever arguments and return value seems
> most appropriate, without affecting the signature of the outer procedure.
> You can always optimize this helper procedure away later if it seems
> appropriate (or possible!)

Hi Anton,
thank you very much for the pointers. I hope they helped. Below is my initial, unoptimized solution:

(define compfunc
(lambda arg
(lambda (x)
(letrec
((compfunc-h
(lambda (fns lastres)
(cond
((null? fns) lastres)
(else (compfunc-h (cdr fns) ((car fns) lastres)))
)
)
))
(compfunc-h (reverse arg) x))
)
)
)

Is it ugly or what? :-)

Ognen

Anton van Straaten

2004-12-15, 8:57 pm

Ognen Duzlevski wrote:
> Is it ugly or what? :-)

It'll look prettier if you follow the Scheme convention of closing
parentheses on the same line as the code they belong to:

(define compfunc
(lambda arg
(lambda (x)
(letrec
((compfunc-h
(lambda (fns lastres)
(cond
((null? fns) lastres)
(else (compfunc-h (cdr fns) ((car fns) lastres))) ))))
(compfunc-h (reverse arg) x) ))))

(Languages like C and Java have too few parentheses and braces, so they tend
to be very proud of the ones they do have, and often show them off by
putting them on their own lines. Scheme, being rich with parentheses,
doesn't need to boast about them. ;)

I included spaces above to indicate the beginning of a set of closing parens
which are associated with a prior line; that can be helpful when you're
getting started, although if you're using a paren-sensitive editor and
correct indentation, it shouldn't be necessary.

Another possibility for prettifying is that instead of letrec for this
purpose, some people prefer to use either "inner define" or "named let",
which can be a little more concise. This is a purely subjective stylistic
point.

I don't know if it was your intent, but compfunc-h is tail-recursive, which
is very clever and can often be desirable. However, it also complicates the
logic slightly. If you didn't intentionally design it that way, it might be
worth trying the more direct solution also, as an exercise.

Remember that the basic "shape" of what you want to do is to apply the first
function to (the result of applying the second function to (the result of
applying the third function ...)). You can achieve that very naturally with
recursion, without requiring the use of "lastres". The definition of
compfunc-h will then look something like this:

(lambda (fns)
(cond
((null? fns) x)
(else ...)))

The result will be a bit simpler than your current solution, and therefore
arguably prettier.

Anton

Ognen Duzlevski

2004-12-15, 8:57 pm

Anton van Straaten <anton@appsolutions.com> wrote:
> I don't know if it was your intent, but compfunc-h is tail-recursive, which
> is very clever and can often be desirable. However, it also complicates the
> logic slightly. If you didn't intentionally design it that way, it might be
> worth trying the more direct solution also, as an exercise.

Yeah, it wasn't my intent really, it was the only solution I could come up with at the moment. :)

> Remember that the basic "shape" of what you want to do is to apply the first
> function to (the result of applying the second function to (the result of
> applying the third function ...)). You can achieve that very naturally with
> recursion, without requiring the use of "lastres". The definition of
> compfunc-h will then look something like this:

> (lambda (fns)
> (cond
> ((null? fns) x)
> (else ...)))

What you mean is:

(define compfunc
(lambda arg
(lambda (x)
(letrec
((compfunc-h
(lambda (fns)
(cond
((null? fns) x)
(else ((car fns) (compfunc-h (cdr fns)))) ))))
(compfunc-h arg)))))

I think the above should work.

Thank you very much for holding my hand, I think my brain is wrapping around this finally. And the more it is, the more
I love it! :)

Ognen

Ray Dillinger

2004-12-16, 3:57 am

Ognen Duzlevski wrote:

> I have the following composition function:
> <snip>
>
> However, I am stuck in generalizing this to any number of functions passed. Basically, I can recurse
> back on mytest above and test for (null? arg) as a base condition, but what do I return? Can anyone
> offer any hints?

I can offer you a couple.

(define foo (lambda . arglist)
....)

will create a function that gets as many arguments as you pass it,
all made into a nice list.

(reverse! liszt)

will take a list and reverse it.

This gives you a list starting with the basic argument and then
giving the functions to compose in reverse order. That's a pretty
easy recursion to write. It goes like this.

(define bar (lambda (val funcs)
(if (null? funcs) val
(bar (apply (car funcs) val) (cdr funcs))))

So, using "inner define" to create a helper function, compose
becomes simply:

(define compose (lambda . args)
(define bar (lambda (val funcs)
(if (null? funcs) val
(bar (apply (car funcs) val) (cdr funcs))))
(apply bar (reverse! args))))

Bear

Arjun Guha

2004-12-16, 3:57 am

What you're essentially doing is chaining a bunch of functions together
with the compose operation. This is often generalized as a fold
function (see the SRFI-1 document). Here is my version, which is
slightly different from the SRFI:

> ;; foldl:: forall a b. (a -> b -> a) a [b] -> a
> (define (foldl fn init lst)
> (if (null? lst)
> init
> (foldl fn (fn init (car lst)) (cdr lst))))

foldl applies init and (car lst) to the function to generate a new
init, and then recurses. If we were to use this to make a general
composition function, the obvious choice for fn is a simple binary
composition function:

> ;; compose-bin:: forall a b c. (b -> c) -> (a -> b) -> (a -> c)
> (define (compose-bin f g)
> (lambda (x)
> (f (g x))))

Now, we can define a variable-arity composition function using foldl
and compose-bin:

> ;; compose:: forall a. (a -> a) -> (a -> a) ... -> (a -> a)
> (define compose
> (lambda args
> (foldl compose-bin (car args) (cdr args))))

Examples:

> ((compose (lambda (x) (* x 20 )) (lambda (x) (- x 10))) 10)
0
> ((compose (lambda (x) (- x 10)) (lambda (x) (* x 20 ))) 10)
190
> ((compose cdr car cdr cdr cdr) '(1 2 3 (5 6 7)))
(6 7)

Ognen Duzlevski

2004-12-16, 3:57 am

Thanks to all who spent their time to give me some help with my question!
Ognen

Joe Marshall

2004-12-16, 4:08 pm

"Anton van Straaten" <anton@appsolutions.com> writes:

> Languages like C and Java have too few parentheses and braces, so they tend
> to be very proud of the ones they do have, and often show them off by
> putting them on their own lines.

Oh? I find that C and Java have *far too many* parentheses and braces
when you attempt to write something that is relatively straightforward
for a Scheme program.

Six open parens in a row:

#define KSCONVERT_PERFORMANCE_TIME(Frequency, PerformanceTime) \
((((ULONGLONG)(ULONG)(PerformanceTime).HighPart * NANOSECONDS / (Frequency)) << 32) + \
((((((ULONGLONG)(ULONG)(PerformanceTime)
.HighPart * NANOSECONDS) % (Frequency)) << 32) + \
((ULONGLONG)(PerformanceTime).LowPart * NANOSECONDS)) / (Frequency)))

Six close parens in a row in a two line macro!

#define StreamFromFOURCC(fcc) ((WORD) ((FromHex(LOBYTE(LOWORD(fcc))) << 4) + \
(FromHex(HIBYTE(LOWORD(fcc))))))

Closures (anonymous inner classes) in Java. Be sure to use the right
flavor of closing delimiter and add just enough (but not too many)
semicolons.

List square_list (List L) {
return L.map (new lambda () {
Object funcall (Object x) {
int xval = (Integer)x.intValue();
return new Integer (xval * xval);}});
}

Continuation-passing-style in C#:

delegate int onearg (int x);

int cpstak (int x, int y, int z, onearg receiver)
{
return ! (y < x)
? receiver (z)
: cpstak (x - 1, y, z,
delegate (int r0) {
return
cpstak (y - 1, z, x,
delegate (int r1) {
return
cpstak (z - 1, x, y,
delegate (int r2) {
return
cpstak (r0, r1, r2,
receiver);});});});
}

Eric J. Wingler

2004-12-16, 4:08 pm

"Ognen Duzlevski" <maketo@norge.freeshell.org> wrote in message
news:cppic1$pl9$1@chessie.cirr.com...
> Hi,
>
> I am teaching myself scheme (using scheme48 and the "Scheme and Art of
Programming" book).
>
> I have the following composition function:
>
> ; define a procedure that composes three functions on one input variable
> (define compose3
> (lambda (f g h)
> (lambda (x)
> (f (g (h x)))
> )
> )
> )
>
> This functions works OK, now I try to generalize to any number of
functions.
> I tried first just to see if it will work on the first two using car and
cdr and it does:
>
> [stuff deleted]

This got me to thinking about something I read awhile back in SICP about
abstracting programs that have essentially the same code. The program

(define repeat-ops (lambda (op ls init)
(if (null? ls)
init
(op (car ls)(repeat-ops op (cdr ls) init)))))

repeats a binary operation "op" on a list of values "ls" with "init"
specified as the initial/default value. So

(repeat-ops + '(1 2 3 4 5 6) 0)

returns the value of 1+2+3+4+5+6,

(repeat-ops * '(1 2 3 4 5 6) 1)

returns the value of 1*2*3*4*5*6, and

(repeat-ops (lambda (x y) (+ x (/ 1 y))) '(1 2 3 4 5 6) 1)

returns the value of the continued fraction 1 + 1/(2 + 1/(3 + 1/(4 + 1/(5 +
1/(6 + 1))))). I tried to use this program to get a repeated composition of
functions, but my efforts failed. Here are two attempts:

((repeat-ops ( lambda (x y)( lambda (z) (x (y z)))) '(sin cos sin)
( lambda (x) x)) 0)

(repeat-ops ( lambda (x y)(x y)) '(sin cos sin) 0)

Both of these attempts produced the following message:
procedure application: expected procedure, given: sin; arguments were:
0

I'm not sure how to interpret this. It expects a procedure, but is given
sin. Isn't sin a procedure? 0 is a valid argument, isn't it?

________________________________
Eric J. Wingler (wingler@math.ysu.edu)
Dept. of Mathematics and Statistics
Youngstown State University
One University Plaza
Youngstown, OH 44555-0001
330-941-1817

Jussi Piitulainen

2004-12-16, 4:08 pm

Eric J. Wingler writes:

> (repeat-ops ( lambda (x y)(x y)) '(sin cos sin) 0)
....
> I'm not sure how to interpret this. It expects a procedure, but is
> given sin. Isn't sin a procedure? 0 is a valid argument, isn't it?

Put both of these to a Scheme interpreter and watch:

'(sin cos sin)
(list sin cos sin)

Eric J. Wingler

2004-12-16, 4:08 pm

Xref: number1.nntp.dca.giganews.com comp.lang.scheme:55373

"Jussi Piitulainen" <jpiitula@ling.helsinki.fi> wrote in message
news:qotbrcup4nv.fsf@venus.ling.helsinki.fi...
> Eric J. Wingler writes:
>
> ...
>
> Put both of these to a Scheme interpreter and watch:
>
> '(sin cos sin)
> (list sin cos sin)

Thanks, that works much better. I need to brush up on this subtle point.

________________________________
Eric J. Wingler (wingler@math.ysu.edu)
Dept. of Mathematics and Statistics
Youngstown State University
One University Plaza
Youngstown, OH 44555-0001
330-941-1817

Bruce Lewis

2004-12-16, 4:08 pm

"Eric J. Wingler" <wingler@math.ysu.edu> writes:

> (repeat-ops ( lambda (x y)(x y)) '(sin cos sin) 0)
>
> Both of these attempts produced the following message:
> procedure application: expected procedure, given: sin; arguments were:
> 0

You specified a list of symbols.
'(sin cos sin) is (quote (sin cos sin)).

You want (list sin cos sin) to construct a list of procedures instead.

--

http://ourdoings.com/ Let your digital photos organize themselves.
Sign up today for a 7-day free trial.

lin8080

2004-12-18, 12:52 pm

Joe Marshall schrieb:

(snip (snip))

Who copy from whom?

lin

Szymon

2004-12-18, 8:57 pm

"Arjun Guha" <arjun.guha@gmail.com> writes:

Hi.

Btw,
[color=darkred]

instead of: (compose (lambda (x) (* x 20 )) (lambda (x) (- x 10)))

(o (* <> 20) (- <> 10))

Is this good idea? (I know about srfi-26)

Regards, Szymon.

Sponsored Links