Lambda Calculus in OCaml: “fun” and “function”

Lambda is fun! Lambda is certainly fun, but what I mean here is that the λ in lambda calculus is similar to the expression fun in OCaml. Recall that in lambda calculus, we have function expressions and function applications: λx.λy.x+y (*A function expression*) λx.λy.x+y 3 4 (*A function application*) In OCaml,…

Lazy or Eager? Order of Evaluation in Lambda Calculus and OCaml

Recall in lambda calculus, two items side by side is an application.  One applies the left item (the function) to the right item (the input).  E.g.: f x is read as “apply f to x“, in which f and x can be any lambda expressions.  Therefore, f and/or x may be…

Encoding Recursion with the Y Combinator

In this post I’ll go through some exercises and encode some recursive functions with the Y combinator. Encoding with rec Continuing on from my last post, Professor Hutton gave us two exercises in the Y combinator video: Encode loop (the function that just calls itself) with rec.  I.e., loop = rec…

Imperative and Functional Insertion Sort in OCaml

I wrote the insertion algorithm in both imperative and functional styles in OCaml!  I talk about the fun and challenges of each style below: Imperative Insertion Sort I strictly follow the pseudocode on p.18 of the book Introduction to Algorithms.  The pseudocode is in imperative style so all I need…