Scheme: Implementing n-argument compose using fold

Question

I'm trying to find the "best" implementation of a multi-argument "compose" in Scheme (I know it's a builtin in some implementations, but assume for the moment I am using one that doesn't have this).

For a 2-argument compose function I have this:

(define compose
  (lambda (f g)
    (lambda x
      (f (apply g x)))))

This has the advantage that if the right-most function needs additional arguments, these can still be passed through the combined function. This has the pleasing property that composing the identity function on top of something does not change the function.

For example:

(define identity
  (lambda (x) x))

(define list1
  (compose identity list))

(define list2
  (compose identity list1))

(list2 1 2 3)
> (1 2 3)

Now to do an "n-argument" compose I could do this:

(define compose-n
  (lambda args
    (foldr compose identity args)))

((compose-n car cdr cdr) '(1 2 3))
> 3

But this no longer preserves that nice "identity" property:

((compose-n identity list) 1 2 3)
> procedure identity: expects 1 argument, given 3: 1 2 3

The problem is that "initial" function used for the foldr command. It has built:

(compose identity (compose list identity))

So... I'm not sure the best way around this. "foldl" would seem to be the natural better alternative, because I want to it start with "identity" on the left not the right...

But a naive implementation:

(define compose-n
  (lambda args
    (foldl compose identity args)))

which works (have to reverse the order of function applications):

((compose-n cdr cdr car) '(1 2 3))
> 3

doesn't solve the problem because now I end up having to put the identity function on the left!

((compose-n cdr cdr car) '(1 2 3))
> procedure identity: expects 1 argument, given 3: 1 2 3

It's like, I need to use "foldr" but need some different "initial" value than the identity function... or a better identity function? Obviously I'm confused here!

I'd like to implement it without having to write an explicit tail-recursive "loop"... it seems there should be an elegant way to do this, I'm just stuck.

Answer 1

You might want to try this version (uses reduce from SRFI 1):

(define (compose . fns)
  (define (make-chain fn chain)
    (lambda args
      (call-with-values (lambda () (apply fn args)) chain)))
  (reduce make-chain values fns))

It's not rocket science: when I posted this on the #scheme IRC channel, Eli noted that this is the standard implementation of compose. :-) (As a bonus, it also worked well with your examples.)