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…

Merge Sort and the Divide and Conquer Approach

Algorithm Design Techniques In earlier posts, I went through the insertion sort and the selection sort algorithms.  They both use the incremental approach.  Each step of the algorithms sorts one element, and thus the algorithms solve the problem incrementally. The divide-and-conquer is another approach.  It includes 3 steps that are…