Haskell: Uncurry, Curry, composition

Question

I have a problem with understanding what the compiler does when I enter this:

(curry . uncurry) (+) 1 2 

After my understanding the compiler goes with uncurry first which would mean that an error would occur because the uncurry function needs an input like this:

(curry . uncurry) (+) (1,2)

but obviously the first one is right. I don't get why though.

What exactly are the steps the compiler takes when evaluating this?

Another topic included question: Why does

(uncurry . curry) (+) (1,2) 

does not work?

Answer 1

After my understanding the compiler goes with uncurry.

No it goes with the (curry . uncurry)

If we evaluate the (curry . uncurry) function we see that this short for:

\x -> curry (uncurry x)

so the (curry . uncurry) (+) 1 2 function is short for:

(\x -> curry (uncurry x)) (+) 1 2

or thus:

(curry (uncurry (+))) 1 2

and uncurry :: (a -> b -> c) -> (a, b) -> c and curry :: ((a, b) -> c) -> a -> b -> c thus transform a function. This thus means that uncurry (+) indeed expects a 2-tuple:

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

but now pass this function through the curry function:

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

so the curry function undoes the transformation the uncurry made to the (+) function. This thus means that curry (uncurry (+)) is the same as (+), and thus:

(curry (uncurry (+))) 1 2

is equivalent to:

(+) 1 2

and this is thus equivalent to 3.

The curry . uncurry is not completely equivalent to id however, since it has as type:

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

this thus means that it restricts the function to a function of type a -> (b -> c).

Answer 2

Your expression parses as

(((curry . uncurry) (+)) 1) 2

so, it builds the function (curry . uncurry) (+) and applies it to 1, then the resulting function is applied to 2.

Hence, we start from (curry . uncurry) (+) which means curry (uncurry (+)). Assume for simplicity that (+) is implemented as

(+) = \x y -> ...

Note the above is an curried function, taking x and then y as separate arguments. We then have:

curry (uncurry (+))
= { definition + }
curry (uncurry (\x y -> ...))    -- note the separate arguments
= { definition uncurry }
curry (\(x, y) -> ...)           -- only one pair argument
= { definition curry }
(\x y -> ...)                    -- back to two arguments
= { definition + }
(+)

Above, uncurry transforms the function + into one that accepts a single pair argument instead of two. This transformation is reversed by curry, which breaks the pair argument into two separate ones.

Indeed, curry . uncurry is the identity transformation on binary curried functions since it applies a transformation and its inverse. Hence, it has no effect on the result, or on the type of the functions involved.

We conclude that your expression is equivalent to ((+) 1) 2, which evaluates to 3.

Answer 3

This question got great answers, yet I would like to add a note about curry . uncurry.

You might have heard of SKI-calculus. If you haven't, it is a calculus where we work with 3 combinators:

Sabc = ac(bc)
Kab  = a
Ia   = a

It is widely known to be Turing-full.

Besides, the I combinator is redundant. Let us try writing it down in terms of S and K combinators. The main idea is that the only argument of I should be passed as the first argument of K, whose second argument is occupied. That is exactly what the S combinator does: if we pass K as the first argument of S, we would have it return the third argument of S:

SKbc = Kc(bc) = c

We have shown that (K*ab = b):

K* = SK

Therefore, we just need to choose the second argument: both K and S would do:

I = SKK = SKS

As one can see, combinator I corresponds to id; combinator K corresponds to const; and combinator S corresponds to (<*>) :: (e -> a -> b) -> (e -> a) -> e -> b.

I = SKK corresponds to const <*> const :: a -> a. Our other results (I = SKS and K* = SK) do not hold in Haskell due to typing:

GHCi> :t (<*>) const (<*>) {- id -}
(<*>) const (<*>) {- id -}
  :: Applicative f => f (a -> b) -> f (a -> b)

GHCi> :t (const <*>) {- flip const -}
(const <*>) {- flip const -} :: (b -> a) -> b -> b

As one can see, our implementations act as the required functions on their domain, but we narrowed the domains down.

If we specify (<*>) const (<*>) to the reader, we get exactly the function you wrote down as curry . uncurry - id for functions.

Another workalike for curry . uncurry is ($):

f $ x   = f x
($) f x = f x
($) f   = f
($)     = id

The function you found is very interesting - it might be a good exercise to look for other workalikes (I don't know whether there are any other notable ones out there).