Order of computation in curried functions

Hello, I started with Haskell few days ago. I use the GHC and ghci to load modules.

I read that curried functions are the general way of writing functions.
I currently try to figure out what the order of evaluation is in some functions I tried to implement.

For example:

I want a function that calculates the product of three Float values.

calc :: Float -> (Float -> (Float -> Float))

calc f1 f2 f3 = f1 * f2 * f3

The second line is the definition, and it says that the function calc needs three arguments to calculate the product and then it states what to do with those arguments.
But what is the meaning and use of the first line? If I understand it correctly, it says that in total four Float values are returned one after another?Does it start at the right most position returning f3 of type float, then returning f2*f3 of type float, then returning f1*f2*f3 of type float and then returning the result of the multiplication of type float? Or is it the other way around? And is this some kind of recursion?

Since I am a beginner I would appreciate some helpful answers.

insertcat

The first line is called a type signature. It tells you (and the compiler) how your function can be evaluated or composed with other functions. The arrow (->) is right-associative, meaning that the type of calc you gave is the same as Float -> Float -> Float -> Float. But let’s stick to the version with parentheses, it’s easier to see what’s going on!

Currying is not the only nice thing about Haskell functions: they can also be applied partially. If you had Float values f1 and f2, could you write down the type signatures for calc f1 and calc f1 f2?

I thought for a while about your question.
Because :type calc is calc :: Float -> Float -> Float -> Float
:type calc f1 and type calc f1 f2 must be
calc f1 :: Float -> Float -> Float
calc f1 f2 :: Float -> Float.

Then :type calc f1 f2 f3 is calc f1 f2 f3 :: Float.
And the definition means that the function finally returns the result
f1*f2*f3.

I have never programmed in a functional language, so it is still unusual to me.

2 Likes

That’s correct, it’s awesome you figured it out and understood. It’s actually not about functional languages but about math. Specifically, something called lambda calculus (by Alonzo Church, predating even computers!).

calc is a function takes a Float as input, and returns a function (which takes a Float and returns a function which takes a Float and returns a Float).

calc f1 is a function that takes a Float and returns a function (which takes a Float and returns a Float).

calc f1 f2 is a function that takes a Float and returns a Float.

The second line is the definition, and it says that the function calc needs three arguments to calculate the product and then it states what to do with those arguments.

Right, so your “normal intention” is to write a function like:

calc :: (Float, Float, Float) -> Float

And you could write it this way if you wanted. Even this way, the function calc actually takes ONLY ONE argument, not three! It takes “only one thing” that happens to be a 3-tuple.

If you had written it that way, the only way to use the function would be:

Prelude> calc (1, 2, 3)
6.0

and it would be illegal to use it with fewer numbers:

*Main> calc 1

<interactive>:5:6: error:
    • No instance for (Num (Float, Float, Float))
        arising from the literal ‘1’
    • In the first argument of ‘calc’, namely ‘1’
      In the expression: calc 1
      In an equation for ‘it’: it = calc 1

This way, we don’t get the “bonus functions” like calc f1 or calc f1 f2. So we lose the convenience of partial application. There might be situations where we want to use the same function (multiplying numbers) on fewer arguments, so we would have to write separate functions to do that.

So if you write it in a curried way, you write ONE definition, and Haskell figures out 3 functions out of that for you!

And, if you write it in a curried form, it still takes ONLY ONE argument! So whether you define the function in a “tupled” way or in a “curried” way, it always takes one argument!

If we wanted to define the partially applied functions ourselves, we would have to use the lambdas, and the definition would look like this:

calc = (\f1 -> (\f2 -> (\f3 -> f1*f2*f3)))

So with currying, there is not necessarily a “special, new, different order of computation” going on. Because there are many different strategies for computing lambda expressions. I’m not sure how Haskell evaluates them. (Probably it does optimizations and chooses different strategies based on different situations.)

My advice would be to let go of your “imperative thinking” about evaluation (like “OK this first, then this, then this, then this”) and to try thinking in a more mathematical way (meaning, in terms of functions). You can trust Haskell that it computes things in a good way.

These ideas come from mathematics. Functions with these kind of type signatures (higher order functions that consume functions as input and/or return functions as output) and partial application of them are used all over mathematics.

For example we can consider a (differentiable) function from the real numbers to the real numbers:

f: R -> R

Then we can consider, for example, a “differential operator” D that consumes such a function as input, and returns its derivative as output:

D: (R -> R) -> (R -> R)

Or we could consider a function that measures some notion of “distance” between two functions (not two points, but two functions)

d(f, g) := limsup { |f(x) - g(x)|  |  x in R }

The signature of d is ((R -> R) x (R -> R)) -> R, that is, it takes a pair of real-to-real functions, and returns a real number.

But we could do a partial application of only one argument if we wanted. Holding the first argument fixed. This would give us a new distance function d_f that measures “distance from f” rather than “distance between two functions”:

d_f (g) := d(f, g)

Then d_f has signature (R -> R) -> R.

So you can go nuts with this kind of thing. And they do. Because mathematicians need higher and higher levels of abstraction for their theories. It’s all down to mathematics. Functional languages simply make a greater effort to bring mathematical theory into code, compared to other languages, that’s all. For example Curry (whom “currying” is named after) was a mathematician/logician.

Moral of the story: study math and logic! Everything else follows from that.

1 Like

It’s because of currying, in haskell you can somehow return functions and that is how you do “multiple parameters” by default.

So in normal languages, you would do something analogous to:
calc :: (a: Float, b: Float, c: Float) -> Float
and you clearly deliver the intent of using 3 parameters.

but haskell goes on to simply
calc :: Float -> (Float -> (Float -> Float))
just so that you could partially apply to one direction more easily.
For instance, you could put calc f1 f2 to a function which requires Float -> Float, like in map (calc 1.1 4.2) [0.5, 2.1, 3.0].

Honestly, mathematics point does not stand because in mathematics we do something like
f : Float * Float * Float -> Float or f : Float^3 -> Float all the time.
Manual “currying” is used when we need Float -> Float, like:
f_(x,y) (z) := f (x, y, z) then do differentiation or something.

So, this is likely some piece from PL researcher’s wild experiments.

1 Like

I found it easiest to wrap my head around this and the differences by starting with this principle:

“a function is a mapping from one type(set) to another” - written f :: a -> b

So there is no function with multiple arguments - your function takes one (yeah you can argue this in math but stick with me please).

So the obvious solution for most of us (both from math-education and programming) is to change the “input” to the function - so if you want a function with multiple arguments (a,b,c) -> d you can do this with tuples (products in math).

But - as often - there is a dual solution where you change the output of the function and this seems to be more tricky at first as most of us are used thinking in terms of points (elements of a set) as some primitive value and don’t include “functions” as points.
Turns out the solution is to have functions return other functions so a -> (b -> c) - it’s a function that given an a will return you a function b -> c.
In programming world you need closures to get the a into scope in what you return but once you have that you are fine.

IMHO it’s a nice exercise to implement curry :: ((a,b) -> c) -> (a -> b -> c) and uncurry :: (a -> b -> c) -> ((a,b) -> c) to see that those are more or less interchangeable (I guess the real benefit of this exercise is to get used to working with functions as arguments and results to other functions though)

1 Like

Thank you very much. Your explanation helped me a lot. I’ll probably study it later in detail when I continue to write code in Haskell.