Types of parameters in functions that accept functions

Question

I am trying to learn Scala using SICP, but I am having a hard time with type definitions of functions and got stuck at SICP. Here a generalized expression is build to find the square root of a number (through fixed-point search or Newton's method) where instead of:

def sqrt_damp(x: Double) =
  fixed_point(average_damp(y => x / y))(1)

def sqrt_newton(x: Double) =
  fixed_point(newton_method(y => square(y) - x))(1)

Based on the functions:

def square(x: Double) = x * x           
def average(x: Double, y: Double) = (x + y) / 2                                             
def abs(x: Double) = if (x < 0) -x else x 

val tolerance = 0.00001                   
def fixed_point(f: Double => Double)(first_guess: Double) = {
  def close_enough(v1: Double, v2: Double): Boolean = abs(v1 - v2) < tolerance
  def attempt(guess: Double): Double = {
    val next = f(guess)
    if (close_enough(guess, next)) next else attempt(next)
  }
  attempt(first_guess)
}

def average_damp(f: Double => Double): Double => Double =
  x => average(x, f(x))

val dx = 0.00001                                
def deriv(g: Double => Double): Double => Double =
  x => (g(x + dx) - g(x)) / dx

def newton_transform(g: Double => Double): Double => Double =
  x => x - g(x) / deriv(g)(x)               

def newton_method(g: Double => Double)(guess: Double): Double =
    fixed_point(newton_transform(g))(guess)

The square functions can be generalized in the form:

(define (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))

Which I attempted to express as follows in Scala:

 def fixed_point_of_transform(g: Double => Double, transform: Double => Double)(guess: Double): Double =
   fixed_point(transform(g))(guess)

Yet the above does not compile and generates the error

type mismatch; found : Double => Double required: Double

Edit, the following works:

def fixed_point_of_transform(g: Double => Double, transform: (Double => Double) => (Double => Double))(guess: Double): Double =
  fixed_point(transform(g))(guess)

So now the previous functions can be defined as:

def sqrt_damp(x: Double) =
    fixed_point_of_transform(y => x / y, average_damp)(1)

def sqrt_newton(x: Double) =
    fixed_point_of_transform(y => square(y) - x, newton_method)(1)

radumanolescu · Accepted Answer · 2016-11-10 15:08:00Z

1

transform takes a Double and returns a Double. You cannot apply it to g, because g is a a function Double => Double. You can apply it to g(x), where x: Double. I think this is what you want: fixed_point((x: Double) => transform(g(x)))(guess)

edited Nov 10, 2016 at 15:08

answered Nov 10, 2016 at 15:01

radumanolescu

4,1912 gold badges35 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

nzn Over a year ago

I think I got it now thanks, so I should do transform: (Double => Double) => (Double => Double) instead

Collectives™ on Stack Overflow

Types of parameters in functions that accept functions

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related