Explaining a currying implementation in Haskell

Question

I'm a Scala programmer learning Haskell with "Haskell Programming from First Principles" to give more coherence to the functional concept I'm using in Scala.

I understand the concept of currying pretty well. Implemented it in Scala well.

I do not understand however, the implementation of currying and uncurry provided by the author:

curry f a b = f (a, b) 
:t curry 
-- curry :: ((t1, t2) -> t) -> t1 -> t2 -> t 

:t fst 
-- fst :: (a, b) -> a 
:t curry fst 
-- curry fst :: t -> b -> t

uncurry f (a, b) = f a b 
:t uncurry 
-- uncurry :: (t1 -> t2 -> t) -> (t1, t2) -> t  

(Page 134).

What is happening here?

In the first case, is it because of applying f (a, b) that we infer that f was actually ((t1, t2) -> t) but then what exactly turns it in t1 -> t2 -> t

I don't understand the inference and the overall curry/uncurry process.

Edit 1

From all the response given so far, i do get it now. I guess I am trying now to get the smart of Haskell.

Taking the curry example:

If I write the equivalent of how one would solve that in Scala, in Haskell:

myCurry :: ((a,b) -> c) -> a ->b -> c 
myCurry f = \a -> \b -> f(a,b)

For reference, the Scala equivalent:

def curry[A,B,C](f: (A, B) => C): A => (B => C) = a => b => f(a, b)

Obviously this is not the idiomatic way to solve that in Haskell. I am interested in what's wrong with that solution from an Haskell point of view, so I can start getting a better sense of the of what makes the Haskell Type System so revered.

So far the only difference I see is that the idiomatic Haskell solution has a bit more inference going on and rely on the partial application of curry. The Scala solution require to be more explicit manual.

Not sure going through some mental gymnastics as such to understand something that simple, is that useful. But why not.

Edit 2

Actually found the way to do the same in Scala albeit minus the generic type all the way.

def fst[A, B](a: A, b:B): A = a
//fst: fst[A,B](val a: A,val b: B) => A

fst[Int, Int] _
//res0: (Int, Int) => Int

def sCurry[A,B,C](f: (A, B) => C) (a: A) (b: B) = f(a,b)
//sCurry: sCurry[A,B,C](val f: (A, B) => C)(val a: A)(val b: B) => C

sCurry[Int, Int, Int] _
//((Int, Int) => Int) => (Int => (Int => Int))

val s = sCurry(fst[Int, Int]) _
//s: Int => (Int => Int)

s (4) (2)
//res1: Int = 4

Answer 1

We can start one variable at a time:

curry f a b = f (a, b)

a and b are unrestricted values (apart from being arguments to the f function), which means we can give them types, let's say a and b (very creative naming, I know).

So, the current signature is looking like (abusing notation):

curry :: (type of f) -> a -> b -> (type of f (a, b))

Since f is called on (a, b) on the right hand side, we can assume that it's a function that takes a tuple (a, b) and returns some value, let's say c. So, f is (a, b) -> c, so f (a, b) is one level applied, or just c. So, the signature of the function is:

curry :: ((a, b) -> c) -> a -> b -> c

Now, we can try to make sense of this signature. I find it easier to understand when parenthesized as this equivalent expression:

curry :: ((a, b) -> c) -> (a -> b -> c)

You pass in a function that takes a tuple and returns a value, and curry returns a function that takes in two values and returns a value. Essentially, you're unpacking the arguments: going from a function that takes in a single tuple containing 2 values, to a function that takes in the 2 values.

Looking at this in the context of curry fst, fst is \(a, b) -> a. So, curry would unpack the arguments, making it \a b -> a. This is basically the definition of const, returning the first argument and ignoring the second.

Now we can look at uncurry. Using the same reasoning as before, we can say that the argument a has type a, and the argument b has type b, and since f is called on a then b, it must have some type a -> b -> c. So, the type signature looks like:

uncurry :: (a -> b -> c) -> (a, b) -> c

Or, parenthesized as before:

uncurry :: (a -> b -> c) -> ((a, b) -> c)

As the name suggests, this is the opposite of curry. It takes in a function that already takes in 2 arguments, then returns a function that takes in a tuple with the two arguments. Looking at uncurry in a usecase:

λ> f = uncurry (+)
λ> :t f
f :: Num c => (c, c) -> c
λ> f (1, 2)
3
λ> (+) 1 2
3

Also, curry (uncurry f) should be f, for any f that takes in two or more arguments.

Answer 2

Perhaps this is too obvious to point out, but for many Haskell functions that operate on other functions, it's easiest to understand them (or indeed, construct them) by taking the definitions as straightforward equivalencies or rewrite rules, rather than trying to work out how they're typed or how they "operate internally".

For example, if I have an uncurry function defined by:

uncurry f (a, b) = f a b

and want to understand how it works, just take an example of a curried function:

times a b = a * b

and apply uncurry to to it:

uncurry times

The definition above implies that this resulting expression can be applied to a pair and rewritten:

(uncurry times) (4, 8) = times 4 8

From this, it should be abundantly clear how given any curried function f that applies to two curried arguments, the expression uncurry f will produce an uncurried version that applies instead to a pair. What could be simpler? There's nothing left to "understand".

What if I want to implement a function instead of understand a given implementation? For example, if I have an uncurried function, like add (a,b) = a + b, suppose I want to curry it. Well, if I had the curry function to do so:

curry add

then how would it need to behave? The function curry add would take two arguments in curried fashion:

(curry add) a b

and it's result would be the application of the uncurried add to a tuple holding those arguments:

(curry add) a b = add (a,b)

If I generalize this:

(curry f) a b = f (a,b)

I get exactly the top-level declaration that defines curry. You can use it as-is, and it will compile, though it's more usual to drop the redundant parentheses on the left.

This is a helpful way of writing implementations of other high-level functions without much thought. How should the compose operator . be defined? Well, if I composed two functions f . g, its application to an argument ought to be the composition:

(f . g) x = f (g x)

This is a perfectly valid top-level definition of .. For performance reasons (i.e., it affects inlining), it's actually implemented in Prelude as:

(.) f g = \x -> f (g x)

but the above rewrite-based definition still works.

Other (sometimes apparently complicated) high-level functions have equally straightforward rewrite-based definitions, though it's sometimes hard to spot what's being defined:

flip f x y = f y x
x & f = f x

-- define "on" from Data.Function, which applies a binary operation
-- to f-transformed arguments
(binop `on` f) x y = binop (f x) (f y)

Answer 3

Note that curry could also be written

curry f = \a -> \b -> f (a, b)

Because curry itself is curried, it only takes one argument, the function of type (t1, t2) -> t. The definition curry f a b = ... itself is in some sense syntactic sugar for this explicitly defined lambda expression.

Answer 4

If you don't feel fluent in functional types in Haskell, it is usually easier to write some redundant parentheses:

curry :: ((a, b) -> c)) -> (a -> (b -> c))
uncurry :: (a -> (b -> c)) -> ((a, b) -> c)

And now we can prove derive the definitions from the types. (don't mind the type variable scoping):

curry = \(f :: (a, b) -> c) -> r1 where -- we have `(a, b) -> c`, but want `a -> (b -> c)`
  r1 :: (a -> (b -> c))
  r1 = \(x :: a) -> r2 where -- we have `a` but want `b -> c`
    r2 :: b -> c
    r2 = \(y :: b) -> r3 where -- we have `b` but want `c`
      r3 :: c
      r3 = f (x, y)  -- we have `c`, because `(x, y) :: (a, b)`, so `f (x, y) :: c`

After unfolding r? variables we get the following definition of curry:

curry = \f -> (\a -> (\b -> f (a, b)))

Which is equivalent in this case to

curry f a b = f (a, b)

This should work similarly with uncurry