I have a parameterized type that recursively uses itself but with a type parameter specialized and when I implement a generic operator, the type of that operator is bound too tightly because of the case that handles the specialized sub-tree. The first code sample shows the problem, and the second shows a workaround that I'd rather not use because the real code has quite a few more cases so duplicating code this way is a maintenance hazard.
Here's a minimal test case that shows the problem:
module Op1 = struct
type 'a t = A | B (* 'a is unused but it and the _ below satisfy a sig *)
let map _ x = match x with
| A -> A
| B -> B
end
module type SIG = sig
type ('a, 'b) t =
| Leaf of 'a * 'b
(* Here a generic ('a, 'b) t contains a specialized ('a, 'a Op1.t) t. *)
| Inner of 'a * ('a, 'a Op1.t) t * ('a, 'b) t
val map : ('a -> 'b) -> ('a_t -> 'b_t) -> ('a, 'a_t) t -> ('b, 'b_t) t
end
module Impl : SIG = struct
type ('a, 'b) t =
| Leaf of 'a * 'b
| Inner of 'a * ('a, 'a Op1.t) t * ('a, 'b) t
(* Fails signature check:
Values do not match:
val map :
('a -> 'b) ->
('a Op1.t -> 'b Op1.t) -> ('a, 'a Op1.t) t -> ('b, 'b Op1.t) t
is not included in
val map :
('a -> 'b) -> ('a_t -> 'b_t) -> ('a, 'a_t) t -> ('b, 'b_t) t
*)
let rec map f g n = match n with
| Leaf (a, b) -> Leaf (f a, g b)
(* possibly because rec call is applied to specialized sub-tree *)
| Inner (a, x, y) -> Inner (f a, map f (Op1.map f) x, map f g y)
end
This modified version of Impl.map
fixed the problem but introduces a maintenance hazard.
let rec map f g n = match n with
| Leaf (a, b) -> Leaf (f a, g b)
| Inner (a, x, y) -> Inner (f a, map_spec f x, map f g y)
and map_spec f n = match n with
| Leaf (a, b) -> Leaf (f a, Op1.map f b)
| Inner (a, x, y) -> Inner (f a, map_spec f x, map_spec f y)
Is there any way to get this to work without duplicating the body of let rec map
?
Applying gasche's solution yields the following working code:
let rec map
: 'a 'b 'c 'd . ('a -> 'b) -> ('c -> 'd) -> ('a, 'c) t -> ('b, 'd) t
= fun f g n -> match n with
| Leaf (a, b) -> Leaf (f a, g b)
| Inner (a, x, y) -> Inner (f a, map f (Op1.map f) x, map f g y)