# Lambda is *fun!*

Lambda is certainly fun, but what I mean here is that the * λ* in lambda calculus is similar to the expression

**in OCaml.**

*fun*Recall that in lambda calculus, we have **function expressions** and **function applications**:

1 2 |
λx.λy.x+y (*A function expression*) λx.λy.x+y 3 4 (*A function application*) |

In OCaml, you can express the same with –*fun*:

1 2 |
fun x y -> x + y (fun x y -> x + y) 3 4 |

Each term separated by a space after *fun* and before *->* are all arguments to the function expression. ** ->** is similar to the

**last dot**in lambda calculus, i.e., the expression after

*->*is the function definition. In fact, you can treat

*fun*as

*λ*and

*->*as

*.*in lambda calculus. The following are the same in OCaml:

1 2 |
fun x -> fun y -> x + y fun x y -> x + y |

A function expression is **an anonymous function**, i.e., a function without a name. Of course, you can name the function. In OCaml:

1 |
let f = fun x y -> x + y |

Which is equivalent to (the usual way of defining a function) :

1 |
let f x y = x + y |

Note that the order of evaluation of *fun* is similar to in lambda calculus too. The function is evaluated first, then the argument is evaluated (OCaml is *eager*). After that, the application is performed. That is, in OCaml ** f x y z** is equivalent to

*.*

**((f x) y) z**# Eta Reduction and *function*

In lambda calculus, we have **α-conversion** and **β-reduction**, as discussed in this post. Here we introduce the last kind of conversion/reduction: **η-conversion**. η-conversion is the concept that two functions are the same if and only if they give the same result for all values of an argument. That is,

1 |
λx.M x ↔ M where x must not be a free variable in M |

Specifically, when the longer form (*λx.M x*) is **reduced** to the shorter form (*M*), it’s called **η-reduction**.

Why is η-reduction relevant here? It’s because ** function** in OCaml can be an η-reduction of

*fun*!

*In OCaml,*

**function****is like**E.g., the following are equivalent:

*fun*that takes only one argument.
1 2 |
fun x -> x + 1 function x -> x + 1 |

*function* also enables pattern matching. The argument you pattern match is omitted in *function. *E.g., the following are equivalent:

1 2 3 4 |
fun x -> match x with | 0 -> 1 | _ -> 0 function | 0 -> 1 | _ -> 0 (*η-reduction of the argument x.*) |

# An Example: RNA Transcription

We can apply the above when solving the coding problem of RNA transcription (taken from the exercism OCaml track exercise):

Given a DNA strand, return its RNA complement (per RNA transcription).

Both DNA and RNA strands are a sequence of nucleotides.

The four nucleotides found in DNA are adenine (**A**), cytosine (**C**), guanine (**G**) and thymine (**T**).

The four nucleotides found in RNA are adenine (**A**), cytosine (**C**), guanine (**G**) and uracil (**U**).

Given a DNA strand, its transcribed RNA strand is formed by replacing each nucleotide with its complement:

`G`

->`C`

`C`

->`G`

`T`

->`A`

`A`

->`U`

First, we define the types according to the mli file in the exercise:

1 2 |
type dna = [ `A | `C | `G | `T ] type rna = [ `A | `C | `G | `U ] |

To convert each DNA nucleotide, we can use pattern matching:

1 2 3 4 5 6 |
let convert dna = match dna with | `A -> `U | `C -> `G | `G -> `C | `T -> `A |

Note that we are writing in the form of *let f x = match x with* …this means we can write it using *function* instead, without specifying the argument *dna*:

1 |
let convert = function `A -> `U | `C -> `G | `G -> `C | `T -> `A |

Now, we just need to apply *convert* to the whole DNA strand. We can use List.map:

1 2 |
let to_rna dnalist = List.map convert dnalist |

Note that we are writing in the form of *let f x = … x*, another chance to η-reduce:

1 |
let to_rna = List.map convert |

What we did here is also called pointfree style. Note that because of the value restriction it is sometimes not possible to omit the argument like this.