ocaml any types matching

Question

I'm trying to write a function that optionally take a function as argument

let xxx ?(extractor = (fun a -> a)) yyy = ...

This ends up having type:

val xxx: ?extractor:('a -> 'a) -> 'c -> ...

My intention is to have the extractor to be a function that extract information from a structure, so the return type can be anything, but I want the default to be identity function

I tried to change the signature of it in the mli as

val xxx: ?extractor:('a -> 'b) -> 'c -> ...

But it does not compile, saying that ('a -> 'a) is not compatible with (a' -> 'b). I find it strange that ('a -> 'a) is not subset of (a' -> 'b). Is there a syntax that I can put in the mli file to say ('a -> *) ?

Answer 1

In a functional language, an unspecified (variable) type you get back from a function basically has to appear somewhere in the type that you pass in. Otherwise, where would the value come from? So there are no (useful) functions of type 'a -> 'b.

It might help to think about the types that you're expecting to pass to your function, and how the extractor function would relate to them. It should be possible to have a fairly straightforward relation. Fighting with the type system usually means you're trying to do something that is likely to fail unexpectedly, which is what the type system is trying to prevent.

Edit:

Maybe what I'm trying to say is that 'a and 'b, the input and output types of your extractor function, aren't going to be arbitrary types. The input type 'a is probably related somehow to the type 'c. Similarly the result type 'b is probably going to be related to the return type of the function xxx as a whole. Without a little more info about these relationships, it's hard to make suggestions.

If you try to think of them as independent, arbitrary types you run into the parametric impossibility that I was talking about above. (It also requires advanced typing, rank 2 polymorphism I think it is.)

As a simple example, say that 'a and 'c are the same type and that 'b is the return type of the function. Then your function would pretty much have to look like this:

let xxx ?extractor s =
    match extractor with
    | Some f -> f s
    | None -> s

This has the behavior you wanted: the default extractor function is the identity function. But this also forces the return type of f to be the same as its input type. So the type of xxx is:

val xxx : ?extractor:('a -> 'a) -> 'a -> 'a

Unless you want to get extremely fancy, there's really no way around this, and I suspect a fancy solution would introduce complexities that would outweigh the convenience of having the optional parameter.

Maybe it would work to have two functions. To continue the simplified example they would look like this:

# let xxx extractor s = extractor s;;
val xxx : ('a -> 'b) -> 'a -> 'b = <fun>
# let xxx_id s = xxx (fun x -> x) s;;
val xxx_id : 'a -> 'a = <fun>

I think these have the types you want, and the only inconvenience is that you have two different names.

Answer 2

When a function signature has type variables like 'a, 'b, etc., that does NOT mean the function can put whatever type in there it wants when it runs. On the contrary, it means that someone from the outside can tell the function what type each of those type variables are, and no matter what it says the function will still be able work correctly. (That someone is the type checker, which sets the types based on the context where the function is used.)

The reason that what you have doesn't make sense is, let's say the function is used in a context that requires 'a to be int and 'b to be string. Your default argument, fun a -> a, cannot satisfy the required type int -> string. Whatever you put there must work for any combination of type variables, but as others have mentioned, it doesn't really make sense to have a function that takes any type and returns any other desired type.

I think what you want instead is two separate functions, one with the extra argument, and the other without, with the latter calling the former using fun a -> a as the extra argument. Note that the function without the extra argument will have one less type variable in its type, since it won't have 'a and 'b separately anymore.

Answer 3

My intention is to have the extractor to be a function that extract information from a structure, so the return type can be anything, but I want the default to be identity function

O_PONIES? Return type of identity function can't be anything, it is exactly something passed to it.

I find it strange that ('a -> 'a) is not subset of (a' -> 'b).

If you want to constrain type A with type B then every instance of type B should be instance of type A, i.e. type B should be the subset of (in other words - more narrow than) type A (not the other way round). In your case ('a -> 'b) is not a subset of ('a -> 'a). This has something to do with LSP, but just intuition is enough to figure this out.