Higher Order Function Clarification

Question

I just started learning functional programming (using Scheme language). I read that a higher order function is the function which either takes in another function as argument or returns another function or both. So I am trying to convert the below code to a higher order function:

   ;; define two procedures - one for calculating square & one for finding double of a number
(define (square x) (* x x )) 
(define (double x) (+ x x ))
(square 5)
=> 25
(double  5)
=> 10

Now I came up with the below one:

;; Implementation 2:
   (define (applyToItself f x) (f x x ) )
   (define (square x) (applyToItself * x ))
   (define (double x) (applyToItself + x ))
   (square 5)
=> 25
   (double 5)
=> 10

I created a function applyToItself which takes a function and a value and returns the computed value by applying the incoming function on the incoming value. Now the square and double function just uses applyToItself with * and +.

Finally I came across another way of this implementation:

;;Implementation 3:
   (define (applyToItself f) (lambda(x) (f x x )) )
   (define square  (applyToItself * ))
   (define double  (applyToItself + ))

   (square 5)
=> 25
   (double 5)
=> 10

This applyToItself implementation now takes in just a function and returns another function rather than the computed value.

My questions are:

is there any significant difference or pros and cons between Implementation 2 and implementation 3?
is applyToItselfin Implementation 2 and implementation 3 both higher order functions?
which one is correct or better implementation?

Sylwester Sylwester · Accepted Answer · 2016-03-31T13:47:37

Very little difference. While it's not very simple to see it version 2 is a form of currying and the procedure that is returned has variables that normally wouldn't be in play anymore that because of the closure is captured by the lambda needs to exist as long as square and double exists.

Some compilers have an optimization technique which is called lambda lifting thus some compilers will actually rewrite version 3 to version 2 as a part of the compilation process making the end result identical.

Some-times when the procedure that generate the procedure does some initialization, like making a lookup, then this would only happen once in version 3 while in version 2 it will do the calculation every application.
Yes
v3 has most black boxing and thus a better abstraction but for simple examples like the ones you show I often go both ways where the usage doesn't dictate one or the other. Sometimes you need to do v3. Eg. square every element of a list using map

(map (applyToItself * ) '(1 2 3)) ; ==> (1 4 9)

Higher Order Function Clarification

1 Answers