compose many functions

Hi,

I am teaching myself scheme (using scheme48 and the "Scheme and Art of Progr
amming" 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 lookin
g 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

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.

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

Anton van Straaten <anton@appsolutions.com> wrote:
> However, once you've figured that out, you'll find it will help to structu
re
> 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 helpe
r
> 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 initia
l, 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

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

Anton van Straaten <anton@appsolutions.com> wrote:
> I don't know if it was your intent, but compfunc-h is tail-recursive, whic
h
> is very clever and can often be desirable.  However, it also complicates t
he
> 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 w
ith at the moment. :)

> Remember that the basic "shape" of what you want to do is to apply the fir
st
> function to (the result of applying the second function to (the result of
> applying the third function ...)).  You can achieve that very naturally wi
th
> 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

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 wha
t 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

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)

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

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

> Languages like C and Java have too few parentheses and braces, so they ten
d
> 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) % (Frequenc
y)) << 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);});});});
}