Wednesday, September 17, 2025

OCAML HIGHER-ORDER FUNCTIONS

 



REVISED: Sunday, September 21, 2025                                        




1. INTRODUCTION

Here are OCaml scripts demonstrating map and filter implemented recursively (which is the idiomatic OCaml equivalent to list comprehensions found in other languages) and a curried function.

2. MAP

OCaml doesn't have a built-in list comprehension syntax. The equivalent and idiomatic way to achieve this is through recursive functions, which is what the standard library's List.map function does behind the scenes.

(* OCaml Map defined using Recursion *) 

(* Define a recursive function 'map_lc' that takes a function 'f' and a list 'lst'. *) 
let rec map_lc f lst = 

(* Match the input list 'lst' with possible patterns. *) match lst with | [] -> [] 

(* Base Case: If the list is empty, return an empty list. *) | h :: t -> (f h) :: (map_lc f t) 

(* Recursive Step: Apply function 'f' to the head 'h', *) (* and prepend (::) the result to the recursive call on the tail 't'. *) (* Example Usage: *) (* Define a function to square a number. *) let square x = x * x;; 

(* Define a list of integers. *) let numbers = [1; 2; 3; 4; 5];; 

(* Apply the 'square' function to every element in the 'numbers' list. *) let squared_numbers = map_lc square numbers;;

(* Print the result to the console. The format specifier "%d" is for integers. *) (* List.iter applies a function to each element for side effects, like printing. *) print_endline "Map Example (squaring [1; 2; 3; 4; 5]):";; List.iter (fun x -> print_int x; print_string " ") squared_numbers;;

(* Expected output: 1 4 9 16 25 *) print_newline ();;

Windows PowerShell
Copyright (C) Microsoft Corporation. All rights reserved.

Install the latest PowerShell for new features and improvements! https://aka.ms/PSWindows

OCaml version: The OCaml toplevel, version 5.3.0
Coq-LSP version: 0.2.3
Loading personal and system profiles took 1081ms.
PS C:\Users\User> ocaml C:\AI2025\map.ml
Map Example (squaring [1; 2; 3; 4; 5]):
1 4 9 16 25
PS C:\Users\User>

3. FILTER

Similarly to map, a filter function is implemented idiomatically with recursion. It iterates through the list, building a new list containing only the elements that satisfy a given condition (predicate).


(* OCaml Filter defined using Recursion *)

(* Define a recursive function 'filter_lc' that takes a predicate function 'p' and
 a list 'lst'. *) let rec filter_lc p lst =

  (* Match the input list 'lst' with possible patterns. *)
  match lst with
  | [] -> [] (* Base Case: If the list is empty, return an empty list. *)

  | h :: t -> (* Recursive Step: Check the head of the list 'h'. *)

    if p h then (* If the predicate 'p' returns true for the head 'h', *)

      h :: (filter_lc p t) (* then include 'h' in the result list and continue with 
the tail 't'. *)

    else (* If the predicate returns false, *)

      filter_lc p t (* then discard 'h' and continue processing the tail 't'. *)

(* Example Usage: *)

(* Define a predicate function to check for even numbers. *)
let is_even x = x mod 2 = 0;;

(* Define a list of integers. *)
let more_numbers = [1; 2; 3; 4; 5; 6; 7; 8];;

(* Select only the even numbers from the list. *)
let even_numbers = filter_lc is_even more_numbers;;

(* Print the result to the console. *)
print_endline "\nFilter Example (finding evens in [1; 2; 3; 4; 5; 6; 7; 8]):";;
List.iter (fun x -> print_int x; print_string " ") even_numbers;;
 (* Expected output: 2 4 6 8 *)

print_newline ();;
Windows PowerShell
Copyright (C) Microsoft Corporation. All rights reserved.

Install the latest PowerShell for new features and improvements!
 https://aka.ms/PSWindows

OCaml version: The OCaml toplevel, version 5.3.0
Coq-LSP version: 0.2.3
Loading personal and system profiles took 1157ms.
PS C:\Users\User> ocaml C:\AI2025\filter.ml

Filter Example (finding evens in [1; 2; 3; 4; 5; 6; 7; 8]):
2 4 6 8
PS C:\Users\User>
3. CURRIED
In OCaml, functions are curried by default. This means a function that appears to take multiple arguments is actually a series of functions, each taking a single argument and returning the next function in the chain until all arguments are supplied.

(* OCaml Curried Function *)

(* Define a function 'add' that takes two arguments, 'x' and 'y'. *)

(* Its type is 'int -> int -> int', meaning it takes an 'int' and returns
 a function of type 'int -> int'. *)
let add x y = x + y;;

(* 'add' is a curried function. We can partially apply it by providing only the 
first argument. *)
(* This creates a new function 'add_five' that "remembers" that x is 5. *)
let add_five = add 5;; 
(* 'add_five' has the type 'int -> int'. It's a function waiting 
for one more integer. *)

(* Now, call the new function 'add_five' with the final argument. *)
let result = add_five 10;; (* This is equivalent to calling 'add 5 10'. *)

(* Print the result to demonstrate the curried function in action. *)
print_endline "\nCurrying Example (add 5 to 10):";;
print_int result;; (* Expected output: 15 *)
print_newline ();;

(* Another example: creating a 'multiply' function. *)
let multiply x y = x * y;; (* Type is 'int -> int -> int' *)

(* Partially apply 'multiply' to create a 'doubler' function. *)
let doubler = multiply 2;; (* Type is 'int -> int' *)

(* Use the new 'doubler' function. *)
let doubled_result = doubler 7;; (* result is 14 *)

(* Print the second example's result. *)
print_endline "\nCurrying Example (doubling 7):";;
print_int doubled_result;; (* Expected output: 14 *)
print_newline ();;
Windows PowerShell
Copyright (C) Microsoft Corporation. All rights reserved.

Install the latest PowerShell for new features and improvements!
 https://aka.ms/PSWindows

OCaml version: The OCaml toplevel, version 5.3.0
Coq-LSP version: 0.2.3
Loading personal and system profiles took 1107ms.
PS C:\Users\User>  ocaml C:\AI2025\curried.ml

Currying Example (add 5 to 10):
15

Currying Example (doubling 7):
14
PS C:\Users\User>

4. CONCLUSION

OCaml doesn't have a built-in list comprehension syntax. The equivalent and idiomatic way to achieve this is through recursive functions, which is what the standard library's List.map function does behind the scenes. Similarly to map, a filter function is implemented idiomatically with recursion. And, in OCaml, functions are curried by default.

  5. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.