Higher Order Functions Considered Unnecessary???

01-parameterized-modules.md

Higher Order Functions Considered Unnecessary??

This is my conversation with my custom GPT. Beyond this point, my questions are in blockquotes, and the GPT's responses are in normal text.

Can you help me explain to my friend how higher-order functions can be replaced with parameterized modules? Here's the rub: I don't want you to do it with OBJ, I want you to show how to do it with parameterized modules in OCaml. FYI - He's an F# programmer, so you don't have to explain things like higher-order functions.

Here's the paper: https://cseweb.ucsd.edu/~goguen/pps/utyop.pdf

Hey Friend,

Let’s talk about how you can replace higher-order functions with parameterized modules in OCaml. Since you're already familiar with higher-order functions, I'll dive straight into how this can be done with modules.

The Concept

In OCaml, parameterized modules (also known as functors) allow us to pass modules as arguments to other modules, similar to how you'd pass functions as arguments in higher-order functions. This technique provides a way to achieve modularity and code reuse, just like higher-order functions but with a twist that fits well with OCaml’s type system.

Example Walkthrough

Let's break down the code piece by piece.

1. Define a Module Type (Interface)

First, we define a module type, MONOID, which acts like an interface. This is where you declare the operations that any module implementing this type should provide.

module type MONOID = 
  sig
    type t
    val neutral : t
    val combine : t -> t -> t
  end

Here, t is the type of the elements in the monoid, neutral is the identity element, and combine is the operation that combines two elements.

2. Create a Parameterized Module (Functor)

Next, we define a parameterized module Iter, which takes a module M that matches the MONOID signature.

module Iter (M: MONOID) = 
  struct
      type e = M.t
      let rec iter = function
        | [] -> M.neutral
        | x :: xs -> M.combine x (iter xs)
  end

This module Iter provides a function iter that folds a list using the combine function from the M module. It’s like a general-purpose fold that can work with any monoid.

3. Define a Specific Monoid

Now, let’s implement a concrete monoid. Here’s a simple one for summing integers:

module Sum : MONOID with type t = int =
  struct
    type t = int
    let neutral = 0
    let combine = (+)
  end

This Sum module defines the type t as int, the neutral element as 0, and the combine function as the addition operator.

4. Apply the Functor

Finally, we apply the Iter functor to the Sum module to get a specialized version of the iter function that sums a list of integers:

module SumIter = Iter(Sum)

Now, SumIter is a module with an iter function that sums up a list of integers using the monoid's combine and neutral.

5. Use the Resulting Module

Here’s how you can use it:

let () =
  let r = SumIter.iter [1;2;3;4;5] in
  Js.log(r)

This code will log the sum of [1;2;3;4;5] to the console.

Putting It All Together

The key idea is that instead of passing functions directly (like you would with higher-order functions), you pass around entire modules. This approach is more type-safe and modular in OCaml because the module system ensures that all necessary operations (like combine and neutral) are provided by the module you pass in.

It’s a powerful technique when you want to enforce certain structures or operations across different types, making your code both flexible and safe.

If you want to play around with the code and see how it gets compiled into JavaScript:

Play with the code on melange.re

02-example.ml

module type MONOID = 
  sig
    type t
    val neutral : t
    val combine : t -> t -> t
  end

module Iter (M: MONOID) = 
  struct
      type e = M.t
      let rec iter = function
        | [] -> M.neutral
        | x :: xs -> M.combine x (iter xs)
  end

module Sum : MONOID with type t = int =
  struct
    type t = int
    let neutral = 0
    let combine = (+)
  end

module SumIter = Iter(Sum)

let () =
  let r = SumIter.iter [1;2;3;4;5] in
  Js.log(r)

03-example.fs

type IMonoid<'T> =
    static abstract member Neutral : 'T
    static abstract member Combine : 'T -> 'T -> 'T

type Iter<'T, 'M when 'M :> IMonoid<'T>> =
    static member Iterate(list: seq<'T>) : 'T =
        let mutable result : 'T = 'M.Neutral
        for item in list do
            result <- 'M.Combine result item
        result

type SumMonoid() =
    interface IMonoid<int> with
        static member Neutral = 0
        static member Combine x y = x + y

let result = Iter<int, SumMonoid>.Iterate([1; 2; 3; 4; 5])
printfn "%d" result

04-example.cs

void Main()
{
	var result = Iter<int, SumMonoid>.Iterate(new List<int> { 1, 2, 3, 4, 5 });
	Console.WriteLine(result);
}

public interface IMonoid<T>
{
	static abstract T Neutral { get; }
	static abstract T Combine(T x, T y);
}

public static class Iter<T, M> where M : IMonoid<T>
{
	public static T Iterate(IEnumerable<T> list)
	{
		T result = M.Neutral;
		foreach (var item in list)
		{
			result = M.Combine(result, item);
		}
		return result;
	}
}

public class SumMonoid : IMonoid<int>
{
	public static int Neutral => 0;
	public static int Combine(int x, int y) => x + y;
}