Puzzler 6

Arg Arrgh!

Scala's concise syntax and rich set of functional primitives allow you to write powerful one-liners. The complexity of these statements can, however, make it difficult to understand the overall intention, at which point declaring a suitably named helper method is often a good idea.

For instance, assume you need to determine the result of applying a simple "generator" function, f, to an initial value, arg, multiple times. This can be achieved neatly using fold—a natural choice for recursive computations:

  // n applications of f to arg: f(f(...f(arg)))
  val result = (1 to n).foldLeft(arg) { (acc, _) => f(acc) }

This is certainly a concise solution to your problem, but figuring out what exactly this line does will generally require more than a quick glance.

You might attempt to make this line easier to understand by extracting it into a helper function, of which we'll consider a version with a single parameter list, applyNMulti, and a curried version, applyNCurried. You could then apply these helper functions to two generator functions: a simple one, nextInt, which applies only to Ints, and a more generic version, nextNumber, which uses the typeclass pattern[1] to handle all numeric types.

What is the result of executing the following code in the REPL?

  def applyNMulti[T](n: Int)(arg: T, f: T => T) =
    (1 to n).foldLeft(arg) { (acc, _) => f(acc) }
  
  def applyNCurried[T](n: Int)(arg: T)(f: T => T) =
    (1 to n).foldLeft(arg) { (acc, _) => f(acc) }
  
  def nextInt(n: Int) = n * n + 1
  
  def nextNumber[N](n: N)(implicit numericOps: Numeric[N]) =
    numericOps.plus(numericOps.times(n, n), numericOps.one)
  
  println(applyNMulti(3)(2, nextInt))
  println(applyNCurried(3)(2)(nextInt))
  println(applyNMulti(3)(2.0, nextNumber))
  println(applyNCurried(3)(2.0)(nextNumber))

Possibilities

1. The first, second, and fourth statements print:

     677
     677
     677.0
   

   and the third fails to compile.

2. The first and second statements print:

     677
     677
   

   and the third and fourth fail to compile.

3. The first, second, and third statements print:

     677
     677
     677.0
   

   and the fourth fails to compile.

4. Prints:

     677
     677
     677.0
     677.0
   

Explanation

Using the simple nextInt generator function works fine, so what could go wrong in the generic case? The required numeric operations for Double are in scope, as you can verify:

  scala> val doubleOps = implicitly[Numeric[Double]]
  doubleOps: Numeric[Double] = 
    scala.math.Numeric$DoubleIsFractional$@7c54c0ca

Perhaps the compiler simply does not like our generic version? Surely, though, both the third and fourth statements should then fail?

As it happens, this is not quite the case. Only the application of the uncurried version to the generic function, nextNumber, troubles the compiler, so the correct answer is number 1:

  scala> println(applyNMulti(3)(2, nextInt))
  677
  
  scala> println(applyNCurried(3)(2)(nextInt))
  677
  
  scala> println(applyNMulti(3)(2.0, nextNumber))
  <console>:10: error: could not find implicit value for 
    parameter numericOps: Numeric[N]
                  println(applyNMulti(3)(2.0, nextNumber))
                                              ^
  
  scala> println(applyNCurried(3)(2.0)(nextNumber))
  677.0

What is the compiler complaining about? The error message implies that the compiler is not looking for implicit evidence of type Numeric[Double], as you might expect, but for a Numeric[N]...?

Isn't N bound to Double by the use of 2.0 as the first argument, though? Yes, it is, but the key point here is that this does not help the compiler. The compiler attempts to satisfy the type requirements for each parameter in a parameter list individually, and is therefore not able to use information about a generic type provided by other arguments in the same parameter list.

In this case, the fact that the generic type N is bound to a specific type, Double, is not available when the compiler searches for the appropriate numericOps. This is true even though the parameter that binds N appears before nextNumber in the parameter list!

In the curried case, on the other hand, N has been bound to Double as part of the evaluation of the previous parameter list, as opposed to an earlier parameter in the same list. The partially applied function to which nextNumber is applied indeed expects a Double, as demonstrated by its type signature:

  scala> applyNCurried(3)(2.0) _
  res9: (Double => Double) => Double = <function1>

Because the compiler knows that N is bound to Double when nextNumber is processed, it can find the appropriate implicit Numeric[Double] value in scope, allowing this variant to execute successfully.

Incidentally, this "type information propagation" is one of the reasons why so many of Scala's standard functions have curried definitions.

Discussion

You can make the uncurried variant succeed by explicitly specifying the type:

  scala> println(applyNMulti(3)(2.0, nextNumber[Double]))
  677.0
  
  scala> println(applyNMulti[Double](3)(2.0, nextNumber))
  677.0

This feels unnecessary, though, since the argument, 2.0, carries the type information. It is also not a practical solution if the initial value is passed as a variable rather than specified as a constant, since a change of the variable's type (e.g., from Double to Float) will cause a compiler error that you should be able to avoid:

  val firstVal = 2.0
  
  scala> println(applyNMulti(3)(firstVal, nextNumber[Double]))
  677.0
  
  // refactored to use a Float
  val firstVal = 2.0f

  scala> println(applyNMulti(3)(firstVal, nextNumber[Double]))
  <console>:11: error: type mismatch;
   found   : Double => Double
   required: AnyVal => AnyVal
     println(applyNMulti(3)(firstVal, nextNumber[Double]))
                                                ^

Also, note that the typeclass pattern involving Numeric is not fundamental to this problem: any type constraint, such as a type bound, can cause the same behavior. As before, the curried version works as expected:

  def nextAnyVal[N <: AnyVal](n: N) = n
  
  scala> applyNCurried(3)(2.0)(nextAnyVal)
  res21: Double = 2.0
  
  scala> applyNMulti(3)(2.0, nextAnyVal)
  <console>:10: error: type mismatch;
   found   : Nothing => Nothing
   required: Double => Double
                applyNMulti(3)(2.0, nextAnyVal)
                                    ^

Information about a type parameter is available only to subsequent parameter lists in a curried invocation, not to other parameters in the same list. When defining methods with parameters whose type constraints can only be satisfied if the type bindings for earlier parameters of the same method are known, use curried method definitions rather than single parameter lists.

---

Footnotes for Chapter 6:

[1] Sobral, "Implicit tricks -- the Type Class pattern." [Sob10]