# Difference between revisions of "Currying"

Basvandijk (talk | contribs) |
(c/e) |
||

(9 intermediate revisions by 2 users not shown) | |||

Line 1: | Line 1: | ||

[[Category:Glossary]] |
[[Category:Glossary]] |
||

− | Currying is the process of transforming a function that takes multiple arguments into a function that takes just a single argument and returns another function |
+ | Currying is the process of transforming a function that takes multiple arguments in a tuple as its argument, into a function that takes just a single argument and returns another function which accepts further arguments, one by one, that the original function would receive in the rest of that tuple. |

− | This is mostly hidden in notation, and so may not be apparent to a new Haskeller. Let's take the function <haskell>div :: Int -> Int -> Int</haskell> which performs integer division. The expression <hask>div 11 2</hask> unsurprisingly evaluates to <hask>5</hask>. |
||

+ | <haskell> |
||

+ | f :: a -> (b -> c) -- (which can also be written as f :: a -> b -> c ) |
||

+ | </haskell> |
||

+ | is the '''curried''' form of |
||

+ | <haskell> |
||

+ | g :: (a, b) -> c |
||

+ | </haskell> |
||

+ | You can convert these two types in either directions with the Prelude functions <hask>curry</hask> and <hask>uncurry</hask>. |
||

+ | <haskell> |
||

+ | f = curry g |
||

+ | g = uncurry f |
||

+ | </haskell> |
||

+ | Both forms are equally expressive. |
||

+ | It holds |
||

+ | <haskell> |
||

+ | f x y = g (x,y) , |
||

+ | </haskell> |
||

+ | however the curried form is usually more convenient because it allows [[partial application]]. |
||

− | But there's more that's going on than immediately meets the untrained eye. It's a two-part process. First, <haskell>div 11</haskell> is evaluated and ''returns a function'' of type <haskell>Int -> Int</haskell> Then that resulting function is applied to the value <hask>2</hask>, and yields <hask>5</hask>. |
||

+ | In Haskell, ''all'' functions are considered curried: That is, ''all functions in Haskell take just one argument.'' |
||

+ | This is mostly hidden in notation, and so may not be apparent to a new Haskeller. It can be said that arrows in the types notation associate ''to the right'', so that <hask>f :: a -> b -> c</hask> is really <hask>f :: a -> (b -> c)</hask>. Functional application, correspondingly, associates ''to the left'': <hask>f x y</hask> is really <hask>(f x) y</hask>, so the types fit. <br><br> |
||

+ | As an illustration, let's take the function <haskell>div :: Int -> Int -> Int -- which is actually Int -> (Int -> Int)</haskell> which performs integer division. The expression <hask>div 11 2</hask> unsurprisingly evaluates to <hask>5</hask>. |
||

− | You'll notice that the notation for types reflects this: you can read <haskell>Int -> Int -> Int</haskell> incorrectly as "takes two <hask>Int</hask>s and returns an <hask>Int</hask>", but what it's ''really'' saying is "takes an <hask>Int</hask> and returns something of the type <hask>Int -> Int</hask>--that is, it returns a function that takes an <hask>Int</hask> and returns an <hask>Int</hask>. (One can write the type as <hask>Int x Int -> Int</hask> if you really mean the former--but since all functions in Haskell are curried, that's not legal Haskell. Alternatively, using tuples, you can write <hask>(Int, Int) -> Int</hask>, but keep in mind that the tuple constructor <hask>(,)</hask> itself can be curried.) |
||

+ | But there's more going on here than immediately meets the untrained eye. It could be a two-part process. |
||

+ | |||

+ | On its own, <hask>div 11</hask> is a function of type <hask>Int -> Int</hask>. Then that resulting function can be applied to the value <hask>2</hask>, so <hask>(div 11) 2</hask> yields <hask>5</hask>. Of course an optimizing compiler will probably handle that whole expression at once, but conceptually that's what's going on. <br /><br /> |
||

+ | |||

+ | You'll notice that the notation for types reflects this: you can read <hask>Int -> Int -> Int</hask> incorrectly as "takes two <hask>Int</hask>s and returns an <hask>Int</hask>", but what it's ''really'' saying is "takes an <hask>Int</hask> and returns something of the type <hask>Int -> Int</hask>" -- that is, it returns a function that takes an <hask>Int</hask> and returns an <hask>Int</hask>. (One can write the type as <hask>Int x Int -> Int</hask> if you really mean the former -- but since all functions in Haskell are curried, that's not legal Haskell. Alternatively, using tuples, you can write <hask>(Int, Int) -> Int</hask>, but keep in mind that the tuple constructor <hask>(,)</hask> itself can be curried.) |
||

Much of the time, currying can be ignored by the new programmer. The major advantage of considering all functions as curried is theoretical: formal proofs are easier when all functions are treated uniformly (one argument in, one result out). Having said that, there ''are'' Haskell idioms and techniques for which you need to understand currying. |
Much of the time, currying can be ignored by the new programmer. The major advantage of considering all functions as curried is theoretical: formal proofs are easier when all functions are treated uniformly (one argument in, one result out). Having said that, there ''are'' Haskell idioms and techniques for which you need to understand currying. |
||

− | Currying provides a convenient way of writing some functions without having to explicitly name them: |
||

+ | See |
||

− | *<hask>(1+)</hask> (unsugared: <hask>(+) 1</hask>) is the "increment" function, |
||

+ | * [[partial application]] |
||

− | *<hask>(2*)</hask> is the "double" function, |
||

+ | * [[Section of an infix operator]] |
||

− | *<hask>("\t"++)</hask> is the "indent" function, |
||

+ | * Sometimes it's valuable to think about functions abstractly without specifically giving all their arguments: this is the [[Pointfree]] style. |
||

− | *<hask>(`elem` "AEIOU")</hask> is the "is-capital-vowel-in-English" function (ignoring the "sometimes Y"). |
||

+ | * Sometimes half the work of the function can be done looking only at the first argument (but there really ''is'' only one argument, remember?): see [[functional dispatch]]. |
||

− | These are examples of [[partial application]] (and of "section" notation). |
||

+ | * Conversion between curried and uncurried style allows [[Composing functions with multiple values|composition of functions with multiple values]] |
||

− | Sometimes it's valuable to think about functions abstractly without specifically giving all their arguments: this is the [[Pointfree]] style. |
||

+ | == Exercises == |
||

− | Sometimes half the work of the function can be done looking only at the first argument (but there really ''is'' only one argument, remember?): see [[functional dispatch]]. |
||

+ | * Simplify <hask>curry id</hask> <!-- (,) --> |
||

+ | * Simplify <hask>uncurry const</hask> <!-- fst --> |
||

+ | * Express <hask>snd</hask> using <hask>curry</hask> or <hask>uncurry</hask> and other basic Prelude functions and without lambdas <!-- uncurry (flip const) --> |
||

+ | * Write the function <hask>\(x,y) -> (y,x)</hask> without lambda and with only Prelude functions <!-- uncurry (flip (curry id)) --> |

## Latest revision as of 13:41, 22 August 2018

Currying is the process of transforming a function that takes multiple arguments in a tuple as its argument, into a function that takes just a single argument and returns another function which accepts further arguments, one by one, that the original function would receive in the rest of that tuple.

```
f :: a -> (b -> c) -- (which can also be written as f :: a -> b -> c )
```

is the **curried** form of

```
g :: (a, b) -> c
```

You can convert these two types in either directions with the Prelude functions `curry`

and `uncurry`

.

```
f = curry g
g = uncurry f
```

Both forms are equally expressive. It holds

```
f x y = g (x,y) ,
```

however the curried form is usually more convenient because it allows partial application.

In Haskell, *all* functions are considered curried: That is, *all functions in Haskell take just one argument.*
This is mostly hidden in notation, and so may not be apparent to a new Haskeller. It can be said that arrows in the types notation associate *to the right*, so that `f :: a -> b -> c`

is really `f :: a -> (b -> c)`

. Functional application, correspondingly, associates *to the left*: `f x y`

is really `(f x) y`

, so the types fit.

```
div :: Int -> Int -> Int -- which is actually Int -> (Int -> Int)
```

`div 11 2`

unsurprisingly evaluates to `5`

.
But there's more going on here than immediately meets the untrained eye. It could be a two-part process.

On its own, `div 11`

is a function of type `Int -> Int`

. Then that resulting function can be applied to the value `2`

, so `(div 11) 2`

yields `5`

. Of course an optimizing compiler will probably handle that whole expression at once, but conceptually that's what's going on.

You'll notice that the notation for types reflects this: you can read `Int -> Int -> Int`

incorrectly as "takes two `Int`

s and returns an `Int`

", but what it's *really* saying is "takes an `Int`

and returns something of the type `Int -> Int`

" -- that is, it returns a function that takes an `Int`

and returns an `Int`

. (One can write the type as `Int x Int -> Int`

if you really mean the former -- but since all functions in Haskell are curried, that's not legal Haskell. Alternatively, using tuples, you can write `(Int, Int) -> Int`

, but keep in mind that the tuple constructor `(,)`

itself can be curried.)

Much of the time, currying can be ignored by the new programmer. The major advantage of considering all functions as curried is theoretical: formal proofs are easier when all functions are treated uniformly (one argument in, one result out). Having said that, there *are* Haskell idioms and techniques for which you need to understand currying.

See

- partial application
- Section of an infix operator
- Sometimes it's valuable to think about functions abstractly without specifically giving all their arguments: this is the Pointfree style.
- Sometimes half the work of the function can be done looking only at the first argument (but there really
*is*only one argument, remember?): see functional dispatch. - Conversion between curried and uncurried style allows composition of functions with multiple values

## Exercises

- Simplify
`curry id`

- Simplify
`uncurry const`

- Express
`snd`

using`curry`

or`uncurry`

and other basic Prelude functions and without lambdas - Write the function
`\(x,y) -> (y,x)`

without lambda and with only Prelude functions