Monday, 19 November 2007

Currying

As a lazy functional language Haskell has to provide automatic currying of all functions. But once you've tried to use a functional language that doesn't automatically curry you realise this isn't just an implementation detail, it's a useful technique for concisely implementing programs.

but before describing how currying helps, what is it? Currying is a concept from the analysis of mathematical functions. Say, you have a function f(a, b), that takes two parameters and returns a value. Currying reduces this to two functions: one that takes the other parameter and returns the original value.

That is, currying reduces functions parameter-by-parameter into other functions - these new functions each take one less parameter, but return a function, instead of a value, that then takes the remaining parameters.

For example: f(a, b) = a + 2b. If this were curried with respect to a = 5, b = 10, then the function would be reduced as follows:

f(5, b) = 5 + 2b
        = f(b)
f(10) = 5 + 2 x 10
      = 25

And hopefully you noticed that halfway through that evaluation we found a function over b which had already had a value substituted in for a. This, by the way, is also an example of partial evaluation. In fact, it's more an example of partial evaluation than currying, as currying does not require values for function parameters.

Anyway, that's a brief introduction to currying in maths, but I'm not a mathematician so for some more (accurate) information try reading up on combinatory logic.

So, how does currying exhibit in Haskell? Function application is treated as a special operation, distinct from calling a function. Functions are applied from left to right, to the first parameter, producing a new function that is applied to the second parameter and so on. A Haskell function call like:

f 1 10 "Hello"

is evaluated as if it's parenthesised like:

((f 1) 10) "Hello"

If working from left to right each additional expression produces a new valid expression, then does that mean we can leave off an arbitrary number of of expressions from the right and still have a valid expression? Yes, that's precisely true. In fact that would actually be a function which could then be given a name and provided with any number of values.

And this is where currying really comes in use for expressing code. Using the right functions and operations you can typically define your own functions without naming any parameters.

In particular, this dramatically reduces the number of anonymous functions you need to declare. As opposed to Scheme, they become quite rare.

A Scheme implementation of reverse could look something like:

(define (reverse lst)
  (define (r lst)
    (if (null? (cdr lst))
        (lambda (t) (cons (car lst) t))
        (lambda (t) ((r (cdr lst)) (cons (car lst) t)))))
  ((r lst) null))

While an equivalent Haskell implementation could look like:

reverse lst = r lst []
  where
    r (h:[]) = (:) h
    r (h:hs) = r hs . (:) h

Of course, in the languages' standard libraries these functions are defined quite differently (Haskell's is only one line...) But this is useful as those are equivalent implementations - Haskell's is shorter only because it automatically curries.

Finally, currying is required in Haskell because it's a lazy language. The currying produces a train of anonymous functions - each retained as a value. Arriving at a result when required is simply achieved by evaluating those retained anonymous function values. But only the minimum set that are actually required.

Understanding currying and being able to curry your own functions is your head is a fundamental step to 'getting' functional programming.

2 comments:

Nuwan said...

Thnx bro ........ It helps me lot

Giles said...

No worries, glad I could help. Btw, this blog has moved to here