Force a broader type for optional argument with more restrictive default value

Question

Is there a way to make optional argument f flexible enough to have type 'a -> 'b, yet still make it default to identity, given that identity has type 'a -> 'a?

An earlier question begins by stating my question, exactly:

I want to define a function that accepts an optional argument which is a function ('a -> 'b). The default value should be the identity, which is actually ('a -> 'a), but i see no reason why it should not be compatible with the more general ('a -> 'b).

However, the question then includes an example that exemplifies a narrower problem. The answers to that question respond to the narrower problem. Here is a simplistic illustration of the general issue:

# let g1 ~f x = f x;;
val g1 : f:('a -> 'b) -> 'a -> 'b = <fun>

OK, that's the type I want. But I'd like to f to default to an identity function. That should be possible, since identity has type 'a -> 'b where 'b is 'a. But it doesn't work:

# let g2 ?(f=identity) x = f x;;
val g2 : ?f:('a -> 'a) -> 'a -> 'a = <fun>

Adding a type specification on identity doesn't help:

# let g3 ?(f=(identity:'a -> 'b)) x = f x;;
val g3 : ?f:('b -> 'b) -> 'b -> 'b = <fun>

EDIT: After I posted this question, I discovered this question, which really is a very close duplicate of my question. So mark my question as a duplicate if you want. However, the answers to that question imply that there is no good use for what I want to do, and that's not true. Here are details:

The actual use case is a function that selects some elements from a list. The optional f argument allows one to extract a bit of data from each element and use that data to decide whether to include that particular list element in the result. When elements are selected by the whole element, f should be identity. The actual function I'm trying to define is for lazy lists. Here's a simplified version for lists, with L as an alias for List:

let select ?(accessor=identity) keys vals =
  let rec sel ks vs =
    if ks = [] || vs = [] then []
    else let k, v = L.hd ks, L.hd vs in
         let v_key = accessor v in
         if k = v_key then v::(sel (L.tl ks) (L.tl vs))
         else if k > v_key then sel ks (L.tl vs) (* let vs catch up *)
         else sel (L.tl ks) vs                   (* let ks catch up *)
  in sel keys vals

Simple use:

# let vs = Batteries.List.range 1 `To 100;;
# let ks = [4; 10];;
# select ks vs;;
- : int list = [4; 10]

The more general use is when elements of ks are, say, records with a key field that's an integer. Then the accessor function would map from the record type to int.

(Yes, I know that the use of hd and tl is a bit unusual. It translates into the lazy list context better.)

Answer 1

OCaml simply does not support this. You cannot write a function with a type that is refined depending on whether an optional argument has been passed.

Unlike some the answers in the linked question, I agree that this is a reasonable thing to want to do. Indeed, typing things like Common Lisp's sequence functions (with :key and :test) seems to require something like this. However, OCaml is not a language in which it can be done.

The most reasonable approach is probably to write two functions, one of which takes an accessor as non-optional argument, and the other which supplies identity as that argument:

let g f x = f x

let g_default x = g identity x

This is only a little clumsy, and you do not need to implement the logic in g twice. However, applying this approach to combinations of more than one optional argument will become ugly.

Answer 2

I think the way to look at this is to imagine what type your function would have. You seem to be asking for this type:

?f:('a -> 'b) -> 'a -> 'b

However, this doesn't capture the idea that when you leave out the optional parameter, the type reverts to 'a -> 'a.

Instead, what this type says is that if you leave out the optional parameter, you have a function of type 'a -> 'b. But there is no well-formed function of type 'a -> 'b. This can only be the type of a function that never returns (or similar).

My take on this is that the OCaml type system can't represent the function you want, even though it does make sense.