0

In below snippet, the recursive function lookup has only one parameter.

How could it later be applied with two parameters k and t?

let rec lookup k = function  (* only 1 parameter k *)
| [] -> None
| (k', v) :: t -> 
  if k = k' then Some v 
  else lookup k t  (* applied with 2 parameters k and t *)

ADD 1 - 2:44 PM 1/24/2025

OCaml function only takes one parameter.

There are 2 syntactic forms of function definition (ref).

Form 1:

enter image description here|200

In form 1, the parameter is only used for pattern matching. The function body expression doesn't directly use the parameter so the parameter doesn't need to be explicitly listed/named.

Form 2:

enter image description here

In form 2, the function body expression does directly use the parameter so the parameter must be explicitly listed/named.

My lookup is defined as a functional value that maps a value of type 'a to a functional value of type ('a * 'b) list -> 'b option.

Applying lookup to an input like lookup k will output the functional value of type ('a * 'b) list -> 'b option.

So in practice, the application of lookup 1 evaluates to a functional value that takes a (int * 'b) list and returns a value of 'b type.

This functional value can be further applied to a value of the type (int * 'b) list.

Improve this question
5
  • Hint: Where do you think the list you match on comes from? Commented Jan 10 at 10:40
  • I can apply lookup with an additional list argument. But that doesn’t comply with the let definition. But it can work. Strange. Commented Jan 10 at 11:01
  • I know about the partial application. But this seems like some over application… Commented Jan 10 at 11:04
  • Is the "ADD 1" supposed to be an answer? Commented Jan 24 at 17:52
  • @mkrieger1, No it's my understanding based on answers below. Just put it there for reference. Commented Jan 26 at 12:39

3 Answers 3

Reset to default
3

All functions take one parameter, and lookup k t is equivalent to (lookup k) t.

lookup k is also a function that takes one parameter - that's what let rec lookup k = function ... means.

However, that parameter is not named, but used only in the pattern-matching clause.

Your definition is (at least more or less) equivalent to

let rec lookup k = fun table -> match table with
    | [] -> None
    | (k', v) :: t -> if k = k' then Some v else lookup k t

which is the same as

let rec lookup k table = match table with
    | [] -> None
    | (k', v) :: t -> if k = k' then Some v else lookup k t

but avoids the match and the naming of the parameter whose name is only used for the matching.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

You defined lookup k as a function, so lookup k can be applied to t. See https://ocaml.org/manual/5.3/expr.html#sss:expr-function-definition

Improve this answer

2 Comments

Thanks for the authoritative reference.
Yes, the t is the implicit parameter that the function keyword offers. The fun keyword doesn't offer this.
1

Another way of looking at your function in terms of OCaml functions only taking one parameter is that lookup generates a closure: a function that iterates recursively over a list knowing which value to look for.

let lookup k =
  let rec aux t = 
    match t with 
    | [] -> None
    | (k', v)::_ when k = k' -> Some v
    | _::tl -> aux tl
  in
  aux

Also note that you've just implemented List.assoc_opt from the standard library.

A note on partial application of polymorphic functions

Applying lookup to an input like lookup k will output the functional value of type ('a * 'b) list -> 'b option.

So in practice, the application of lookup 1 evaluates to a functional value that takes a (int * 'b) list and returns a value of 'b type.

Be careful that in OCaml this isn't true. You run afoul of the value restriction.

# let l = lookup 42;;
val l : (int * '_weak1) list -> '_weak1 option = <fun>
# l [(42, "foo")];;
- : string option = Some "foo"
# l;;
- : (int * string) list -> string option = <fun>
# l [(42, 27.3)];;
Error: This expression has type float but an expression was expected of type
         string
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.