Monday, October 13, 2008

Partial Application in Haskell and Scala

This is an attempt to squeeze out a blog post while I wait for my laundry to finish.

Functional languages are fun. Fun in ways that Java (and, for that matter, Ruby) are not. Take Haskell. In that language, we can take any operator and turn it into a function. Normally, we use the symbol + to represent addition. If we enclose it in parentheses, we instead have a function.

(+) :: (Num a) => a -> a -> a

In this case, (+) is a function of 2 number parameters, which returns a number. Now that we have a function, we can apply all of the standard Haskell magic to it. Since Haskell is automatically curried (no function really ever takes more than one parameter), we chain calls to fully evaluate our (+) function.

(+) 2 3 => 5

We can also partially apply this operator.

add5 :: Integer -> Integer
add5 = (+) 5
add5 3 => 8

In this case, we have created an alias for the partially bound + operator. Rather than jump through so many hoops, we could specify add5 more directly.

add5 = (5+)

Finally, a slightly more complicated example.

simple :: Integer -> Integer -> Integer -> Integer
simple x y z = x * (y + z)

simpler :: Integer -> Integer -> Integer
simpler = simple 2

simplest :: Integer
simplest = simpler 3 4 => 14

All functions are also values in Haskell.

easy = simple
easy 2 3 4 => 14

As you can see, in Haskell, we can turn any operator into a function. Functions are curried, and can be partially evaluated from the left. Functions are also values that can be assigned and passed around as needed.

Scala takes a different approach. In Scala, operators are actually methods on values. There is no global + operator. Instead, you invoke the + method on the left hand parameter.

5 + 3 //is the same as...

If you want to refer to a function as a value in Scala, you must "partially apply" it to zero parameters.

val output = println //will result in a compilation error
val output = println _
output "Oh Hai, World!"

The underscore is the Scala placeholder operator. If used as we did with println, it stands in for the whole argument list, effectively turning the function into a function value. It is also the mechanism by which we can partially apply a function.

def simple(x:Int, y:Int, z:Int) = x * (y + z)
val simpler = simple(2, _:Int, _:Int)
simpler(3, 4) => 14

The underscores, when used this way, compel the result of the expression to itself be a function that takes n parameters, where n is the number of placeholders. Sometimes, it is possible to infer the type of the missing parameters; other times, it isn't. It depends on how the parameters are used.

It is very important to notice that, unlike Haskell, it is very easy to bind only the parameter in the middle of this expression.

val sample = simple(_:Int, 3, _:Int)
sample(2, 4) => 14

By combining placeholder syntax with operators, it is possible to turn an operator into a function, even a function that takes its left operand as a parameter.

List(1, 2, 3).map(_ + 2) => List(3, 4, 5)
List(1, 2, 3).reduceLeft(_ + _) => 6

As you can see, Haskell and Scala have a lot in common. Haskell's syntax is a bit more concise (and its inference rules much better), but Scala's ability to bind any parameter is pretty handy, too. There's something both cluttered and clean about Haskell's use of underscores, especially when types aren't required. Of course, I'm not an expert (or, in fact, experienced at all) with either language, so please correct me if I got any of my facts wrong.

Looks like I failed. My laundry was done 30 minutes ago.


Marc said...

It seems a little awkward to distinguish between operators and functions in haskell; all operators are functions, its just the difference between infix and prefix notation. Notice that the programmer can turn any infix operator into prefix notation by adding parens:

(+) 2 3 => 5

The programmer can define his own operators as well, again by including the parens:

(*+) x y = x * y + x + y
2 *+ 3 => 11

Haskell even lets prefix functions be called using infix notation, using the backtick character:

sumSquares x y = x^2 + y^2
2 `sumSquares` 3 => 13

The scala underscore placeholder seems pretty neat, especially for making partial application clearer. In haskell, the most succinct way I know to bind the middle param from your example would be to write:

simple x y z = x * (y + z)
fancy = flip simple 3
fancy 2 7 => 20

But binding the last param seems even trickier. Without resorting to lambdas, the best I've got for now is:

fanciest = curry $ (flip $ uncurry simple) 10
fanciest 3 2 => 36

But, the lambda version doesn't hurt my brain trying to read it:
fanciest = \x y -> simple x y 10

stepancheg said...

_ in Scala is used to convert method to function value, not function to function value.