CODEWITHSUNDEEP
functionschemer5rs
Roman Sosnovsky
Roman Sosnovsky

Reputation: 21

Scheme function that return composition of functions

How to realize a function that takes as input an any number of procedures with one argument and returns another function is the composition of these procedures in Scheme.

For example:

(define (f x) (* x 2))
(define (g x) (* x 3))
(define (h x) (- x))

((comp-func f g h) 1) => -6
((comp-func f g) 1)   => 6
((comp-func h) 1)     => -1
((comp-func) 1)       => 1

Upvotes: 1

Views: 5949

Answers (4)

Robert Nowak
Robert Nowak

Reputation: 293

No need for any intermediate define or let or set or what ever.

We stay pure functional and need no variables.

(define (comp-func . procs)
  (lambda (arg)
    (if (null? procs)
      arg
      ((car procs) ((apply comp-func (cdr procs)) arg)))))

Upvotes: 0

PieterT2000
PieterT2000

Reputation: 388

In addition to @Kevin's nice recursive solution, I would like to add that there's no need to use set!. Inside comp-func you can simply return a lambda function that calls comp-rec with the list of procedures as the extra argument.

(define (comp-func . procs)
  (define (comp-rec arg procs)
    (if (null? procs)
        arg
        ((car procs) (comp-rec arg (cdr procs)))))
  (lambda (arg) (comp-rec arg procs )))

Upvotes: 1

Joshua Taylor
Joshua Taylor

Reputation: 85913

As written, the question is ambiguous, because we can't tell in which order you're composing the functions. That is, we can't tell whether ((comp-func f g h) 1) computes (f (g (h 1))) or (h (g (f 1))), since both would work out to -6 in this case.

That said, this problem can be solved by a (left to right) fold a.k.a. reduction; once you know how to compose two functions, you can reduce that binary composition over a list of functions.

First, composing two functions is easy:

(define (compose2 f g)
  ;; Returns a function that computes (g (f x)).
  (lambda (x)
    (g (f x))))

Now, to reduce (a.k.a. fold left to right) a function f over a list (x1 x2 ... xn) with an initial value i means computing

(f ... (f (f (f i x1) x2) x3 ...) xn)

(by definition). Composing a list of functions (f1 f2 f3 f4) is then just folding the compose2 function with an initial value that is the identity function.

(define (identity x)
  x)

(define (compose . functions)
  (reduce compose2 identity functions))

reduce is a built-in function that does the (left to right) folding.

I'll use some functions where the order matters, so that we can see the difference in results:

(define (f x) (* x x))
(define (g x) (+ x 3))

(display ((compose f g) 3))
;=> 12 == (g (f 3)) == (3^2)+3

(display ((compose g f) 3))
;=> 36 == (f (g 3)) == (3+3)^2

Upvotes: 7

KeV
KeV

Reputation: 2891

A clean solution would be 

(define (comp-func . procs)
  (define (comp-rec arg procs)
    (if (null? procs)
        arg
        ((car procs) (comp-rec arg (cdr procs)))))

  comp-rec)

However with this solution you need to call it like this ((comp-func f g h) 1 (list f g h)).

Here is a solution that will work if you call it like in your examples, however it is a bit uglier because we need to use set! to change procs argument.

(define (comp-func . procs)
  (define (comp-rec arg)
    (if (null? procs)
        arg
        (let ((proc (car procs))
              (rest (cdr procs)))
          (set! procs rest)
          (proc (comp-rec arg)))))

  comp-rec)

Upvotes: 2

Related Questions