Type definitions and type mismatch in a higher order function

Question

I'm currently working through the video lectures from Martin Odersky's Coursera class, Functional Programming Principles in Scala. In lecture 2.1, he demonstrates composition of higher order functions using a base function, sum(). He implemented factorial without tail recursion, but I tried it with tail recursion because it's still just a line of code. As a consequence, I got a type mismatch where I assume Odersky didn't. In defining sum(), parameter f takes an Int and returns an Int. I know I can just get around this by adjusting my function*, but this has me wondering about how to design higher-order functions in general. Is there a way I can adjust or circumvent this type definition in order to allow functions that take a flexible number of arguments? Someone showed me a little Haskell once, and I'm wondering if Scala's function parameters can be typed in a similarly loose fashion... or perhaps there's a different solution more native to Scala. Please assume I just started playing with Scala yesterday and have limited computer science knowledge in your explanation, because that is exactly the case.

def sum(f: Int => Int, a: Int, b: Int): Int =
    if (a > b) 0 else f(a) + sum(f, a+1, b) 


//Factorial with tail recursion.  The one in the lesson DOES NOT use tail recursion.
//prev is an accumulator.
def fact(a: Int, prev:Int = 1): Int =
        if (a == 0) prev else fact(a-1, a * prev)


def sumFactorials(a: Int, b: Int): Int = sum(fact, a, b)

*I know that I could just fix this by nesting my current fact() within another function, like so:

def factorial(a: Int): Int ={
    def fact(n: Int, prev:Int = 1): Int =
            if (n == 0) prev else fact(n-1, n * prev)
    fact(a)
}

My impression from my aforementioned Haskell experience was that functional programming promotes functions taking only one argument to allow for currying. Anyway, it's a bit tangential to the actual question, but feel free to address this in the comments if I'm just butchering FP horribly with the spirit of my question.

Answer 1

I think there are a couple of things going on here.

First, I think what you're trying to do with the fact function (use a function with a default value as though its type actually had one fewer parameters) is not possible. An (Int,Int) => Int is still an (Int,Int) => Int even if the second Int defaults to 1. You can't pass it as an Int => Int. I can see where you might think you could, though.

Second, your fact and factorial functions are not equivalent. The factorial function uses the original value of 'a' over and over no matter how many times you recurse. The fact function, uses a decrementing 'a' in each call.

Based on your 'fixed' factorial function, the function effectively takes three parameters: the original a, the decrementing n, and the multiplying prev. The below code is equivalent.

def sum(f: (Int,Int,Int) => Int, a: Int, b: Int): Int = 
    if (a > b) 0 else f(a,a,1) + sum(f, a+1, b) 

def fact(a: Int, n: Int, prev:Int): Int = 
    if (n == 0) prev else fact(a, n-1, a * prev)

def sumFactorials(a: Int, b: Int): Int = sum(fact, a, b)

You also can't write sum as:

def sum(f: (Int, Int) => Int, a: Int, b: Int): Int =
    if (a > b) 0 else f(a) + sum(f, a+1, b) 

The passed in function f might have a default parameter and it might not, so it wouldn't be safe for the compiler to allow the f(a) call.

I think default parameters are implemented more like "syntactic sugar", as they say, attached to the actual function rather than like function currying. You can do this with currying, but you have to explicitly declare the curried function. Assuming that you want to use the logic from fact (and not factorial), you can do it like so:

def sum(f: Int => Int, a: Int, b: Int): Int =
    if (a > b) 0 else f(a) + sum(f, a+1, b) 

def fact(prev:Int = 1)(a: Int): Int =
        if (a == 0) prev else fact(a * prev)(a-1)

def sumFactorials(a: Int, b: Int): Int = sum(fact(1), a, b)

Note that we had to switch the position of fact's parameters.