How to define "apply" in OCaml

Question

I am trying to define a function that is similar to Lisp's apply. Here is my attempt:

type t =
  | Str of string
  | Int of int

let rec apply f args =
  match args with
  | (Str s)::xs -> apply (f s) xs
  | (Int i)::xs -> apply (f i) xs
  | [] -> f

(* Example 1 *)
let total = apply (fun x y z -> x + y + z)
                  [Int 1; Int 2; Int 3]

(* Example 2 *)
let () = apply (fun name age ->
                  Printf.printf "Name: %s\n" name;
                  Printf.printf "Age: %i\n" age)
               [Str "Bob"; Int 99]

However, this fails to compile. The compiler gives this error message:

File "./myprog.ml", line 7, characters 25-30:
7 |   | (Str s)::xs -> apply (f s) xs
                             ^^^^^
Error: This expression has type 'a but an expression was expected of type
         string -> 'a
       The type variable 'a occurs inside string -> 'a

What is the meaning of this error message? How can I fix the problem and implement apply?

Answer 1

You cannot mix an untyped DSL for data:

type t =
| Int of int
| Float of float

and a shallow embedding (using OCaml functions as functions inside the DSL) for functions in apply

let rec apply f args =
  match args with
  | (Str s)::xs -> apply (f s) xs (* f is int -> 'a *)
  | (Int i)::xs -> apply (f i) xs  (* f is string -> 'a *) 
  | [] -> f (* f is 'a *)

The typechecker is complaining that if f has type 'a, f s cannot also have for type 'a since it would mean that f has simultaneously type string -> 'a and 'a (without using the recursive types flag). And more generally, your function apply doesn't use f with a coherent type: sometimes it has type 'a, sometimes it has type int -> 'a, other times it would rather have type string -> 'a. In other words, it is not possible to write a type for apply

val apply: ??? (* (int|string) -> ... *) -> t list -> ???

You have to choose your poison.

Either go with a fully untyped DSL which contains functions, that can be applied:

type t =
| Int of int
| Float of float
| Fun of (t -> t)

exception Type_error
let rec apply f l = match f, l with
| x, [] -> f
| Fun f, a :: q -> apply (f a) q
| (Int _|Float _), _ :: _ -> raise Type_error

or use OCaml type system and define a well-typed list of arguments with a GADT:

type ('a,'b) t =
| Nil: ('a,'a) t
| Cons: 'a * ('b,'r) t -> ('a -> 'b,'r) t
 
let rec apply: type f r. f -> (f,r) t -> r = fun f l ->
match l with
| Nil -> f
| Cons (x,l) -> apply (f x) l

EDIT: Using the GADT solution is quite direct since we are using usual OCaml type without much wrapping:

let three = apply (+) (Cons(1, Cons(2,Nil))) 

(and we could use a heterogeneous list syntactic sugar to make this form even lighter syntactically)

The untyped DSL requires to build first a function in the DSL:

let plus = Fun(function
  | Float _ | Fun _ -> raise Type_error
  | Int x -> Fun(function
    | Float _ | Fun _ -> raise Type_error
    | Int y -> Int (x+y)
    )
  )

but once we have built the function, it is relatively straightforward:

let three = apply_dsl plus [Int 2; Int 1]

Answer 2

type t =
  | Str of string
  | Int of int
  | Unit

let rec apply f args =
  match args with
  | x::xs -> apply (f x) xs
  | [] -> f Unit

Let's go step by step:

• line 1: apply : 'a -> 'b -> 'c (we don't know the types of f, args and apply's return type
• line 2 and beginning of line 3: args : t list so apply : 'a -> t list -> 'c
• rest of line 3: Since f s (s : string), f : string -> 'a but f t : f because apply (f s). This means that f contains f in its type, this is a buggy behaviour

It's actually buggy to call f on s and i because this means that f can take a string or an int, the compiler will not allow it.

And lastly, if args is empty, you return f so the return type of f is the type of f itself, another buggy part of this code.

---

Looking at your examples, a simple solution would be:

type t = Str of string | Int of int

let rec apply f acc args =
  match args with x :: xs -> apply f (f acc x) xs | [] -> acc

(* Example 1 *)
let total =
  apply
    (fun acc x ->
      match x with Int d -> d + acc | Str _ -> failwith "Type error")
    0 [ Int 1; Int 2; Int 3 ]

(* Example 2 *)
let () =
  apply
    (fun () -> function
      | Str name -> Printf.printf "Name: %s\n" name
      | Int age -> Printf.printf "Age: %i\n" age)
    () [ Str "Bob"; Int 99 ]

Since you know the type you want to work on, you don't need GADT shenanigans, just let f handle the pattern matching and work with an accumulator