Learn Haskell— 3 Link to heading

Currying is a technique of transforming a function that takes multiple arguments into a function that takes one argument and returns another function that takes the rest of the arguments. This allows for partial application of functions, which can be useful for creating specialized or reusable functions.

For example, consider map function in Haskell

map :: (a -> b) -> [a] -> [b]

What does it mean? Well, for those not familiar with currying, we can interpret this in two different ways, depending on where we place parentheses.

Interpretation 1. map takes two arguments Link to heading

• a function that transform type a into b, i.e., a->b
• a list of type a.

Then, map returns a list of type b. Its signature would look like

map((a -> b), [a]) -> [b]

Interpretation 2. map takes one argument Link to heading

• a function a->b

Then map returns a function that takes a list of type a and returns a list of type b. Its signature would look like

map((a -> b)) -> ([a] -> [b])

These signatures are completely different in typical non-functional programming languages, but in Haskell, the two interpretations are equivalent if we provide two arguments.

If you provide a single argument to map, then it will return a function. This is in accordance with interpretation 2. If you provide one more argument, then it will return a list of type b. Both interpretations yields exactly the same result!

-- interpretation 1
map (*2) [1,2,3] -- doubles each element of [1,2,3], returns [2,4,6]

-- interpretation 2
f = (map (*2)) -- doubles each element of a given list
f [1,2,3] -- returns [2,4,6]

So, interpretation 2 is more general and should be how we think of the function signature. That is, -> operators are right-associative.

Example 1 Link to heading

Let’s do an example. We want to create two functions, double() and plus_one(). They take an iterator and doubles or adds one to each element of an iterator, respectively. Here is how we would write them in Rust

fn double(iter: impl Iterator<Item=u32>) -> impl Iterator<Item=u32> {
    iter.map(|x| x*2)
}

fn plus_one(iter: impl Iterator<Item=u32>) -> impl Iterator<Item<u32>> {
    iter.map(|x| x+1)
}

fn main() {
    let xs: Vec<_> = double([1,2,3,4,5].into_iter()).collect();
    println!("{:?}", xs);
    let xs: Vec<_> = plus_one([1,2,3,4,5].into_iter()).collect();
    println!("{:?}", xs);
}

And, here is how we would write in Haskell

double = map (*2)
plus_one = map (+1)
main = do
  putStrLn $ show $ double [1,2,3,4,5]
  putStrLn $ show $ plus_one [1,2,3,4,5]

Example 2 Link to heading

Let’s look at a bit more difficult example. We want to re-implement length function ourselves, which returns the length of a Foldable:

length' :: Foldable t => t a -> Int

We will be using foldr function, whose signature is

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

foldr takes three parameters using interpretation 1

• a binary function a->b->b
• initial value type b
• and a Foldable of a

Then foldr returns type b. With curry, we can provide the first two arguments to foldr to make it the same signature as length function, where b type is Int.

The first argument—let’s call it f—is a binary function that simply increment its second argument b by 1. We can easily define it as follows

f :: a -> Int -> Int
f _ x = x + 1

The second argument should naturally be 0. Putting all together, we have

f :: a -> Int -> Int
f _ x = x + 1

length' :: Foldable t => t a -> Int
length' = foldr f 0

main = do
  putStrLn $ show $ length' [] -- 0
  putStrLn $ show $ length' "12345" -- 5

Example 3 Link to heading

This is all good, but defining f explicitly makes it a bit verbose. Can we do it more concise? There is a built-in function const that takes two parameters and returns the first, ignoring the second. Its definition is show below

const :: a -> b -> a
const x _ =  x

How can we transform const into f above? Well, we can use another currying! Note that f ignores the first parameter while const ignores the second. If we curry const by providing only the first argument, then we can essentially create a function that ignores the first parameter! That is, we can redefine f like this

f' = const (+1)

In fact, we don’t even need explicit definition of f anymore. With this, let’s simplify what we wrote in Example 2 by substituting f:

length' :: Foldable t => t a -> Int
length' = foldr (const (+1)) 0

main = do
  putStrLn $ show $ length' [] -- 0
  putStrLn $ show $ length' "12345" -- 5

It may take a while for the concept of currying to sink for those not experienced with functional paradigm. However, once it sinks, you will find a new dimension and possibilities in writing concise code, even in non-functional programming language!