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

While it would have been nice for the "empty" list to devolve to the identity function, surrendering this appears to result in the following, which isn't too bad:

(define compose-n
  (lambda (first . rest)
    (foldl compose first rest)))

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

((compose-n list identity identity) 1 2 3)

Answer 2

The issue here is that you're trying to mix procedures of different arity. You probably want to curry list and then do this:

(((compose-n (curry list) identity) 1) 2 3)

But that's not really very satisfying.

You might consider an n-ary identity function:

(define id-n
  (lambda xs xs))

Then you can create a compose procedure specifically for composing n-ary functions:

(define compose-nary
  (lambda (f g)
    (lambda x
      (flatten (f (g x))))))

Composing an arbitrary number of n-ary functions with:

(define compose-n-nary
  (lambda args
    (foldr compose-nary id-n args)))

Which works:

> ((compose-n-nary id-n list) 1 2 3)
(1 2 3)

EDIT: It helps to think in terms of types. Let's invent a type notation for our purposes. We'll denote the type of pairs as (A . B), and the type of lists as [*], with the convention that [*] is equivalent to (A . [*]) where A is the type of the car of the list (i.e. a list is a pair of an atom and a list). Let's further denote functions as (A => B) meaning "takes an A and returns a B". The => and . both associate to the right, so (A . B . C) equals (A . (B . C)).

Now then... given that, here's the type of list (read :: as "has type"):

list :: (A . B) => (A . B)

And here's identity:

identity :: A => A

There's a difference in kind. list's type is constructed from two elements (i.e. list's type has kind * => * => *) while identity's type is constructed from one type (identity's type has kind * => *).

Composition has this type:

compose :: ((A => B).(C => A)) => C => B

See what happens when you apply compose to list and identity. A unifies with the domain of the list function, so it must be a pair (or the empty list, but we'll gloss over that). C unifies with the domain of the identity function, so it must be an atom. The composition of the two then, must be a function that takes an atom C and yields a list B. This isn't a problem if we only give this function atoms, but if we give it lists, it will choke because it only expects one argument.

Here's how curry helps:

curry :: ((A . B) => C) => A => B => C

Apply curry to list and you can see what happens. The input to list unifies with (A . B). The resulting function takes an atom (the car) and returns a function. That function in turn takes the remainder of the list (the cdr of type B), and finally yields the list.

Importantly, the curried list function is of the same kind as identity, so they can be composed without issue. This works the other way as well. If you create an identity function that takes pairs, it can be composed with the regular list function.

Answer 3

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.)

Answer 4

The OP mentioned (in a comment to my answer) that his implementation of Scheme does not have call-with-values. Here's a way to fake it (if you can ensure that the <values> symbol is never otherwise used in your program: you can replace it with (void), (if #f #f), or whatever you like that's not used, and that's supported by your implementation):

(define (values . items)
  (cons '<values> items))

(define (call-with-values source sink)
  (let ((val (source)))
    (if (and (pair? val) (eq? (car val) '<values>))
        (apply sink (cdr val))
      (sink val))))

What this does is that it fakes a multi-value object with a list that's headed by the <values> symbol. At the call-with-values site, it checks to see if this symbol is there, and if not, it treats it as a single value.

If the leftmost function in your chain can possibly return a multi-value, your calling code has to be prepared to unpack the <values>-headed list. (Of course, if your implementation doesn't have multiple values, this probably won't be of much concern to you.)