Signature of a function changed when adding a recursion

[kttmm]

I have a function whose type is changed when introducing a recursive calling function with and. The change in type breaks callers somewhere else in the code (spooky action at distance!).

The function before the change:

let convert_inline (t : Inline.t) =
  match t with
  | Emphasis _ -> txt "nyi emphasis"
  | Break_Line -> br ()
  | Hard_Break_Line -> br ()
  | Verbatim _ -> txt "nyi verbatim"
  | Code s -> code [txt s]
  | Tag _ -> txt "nyi tag"
  | Spaces _ -> txt "nyi spaces"
  | Plain s -> txt s
  | Link link -> convert_link link
  | Nested_link _ -> txt "nyi link"
  | Target _ -> txt "nyi target"
  | Subscript _ -> txt "nyi subscript"
  | Superscript _ -> txt "nyi subscript"
  | Footnote_Reference _ -> txt "nyi footnote"
  | Cookie _ -> txt "nyi cookie"
  | Latex_Fragment _ -> txt "nyi latext fragement"
  | Macro _ -> txt "nyi macro"
  | Entity _ -> txt "nyi entity"
  | Timestamp _ -> txt "nyi timestamp"
  | Radio_Target _ -> txt "nyi radio target"
  | Export_Snippet (_, _) -> txt "nyi snippet"
  | Inline_Source_Block _ -> txt "nyi inline"
  | Email _ -> txt "nyi email"
  | Inline_Hiccup _ -> txt "nyi hiccup"
  | Inline_Html _ -> txt "nyi inline html"

Infered type: t -> [> `A of [> Html_types.txt ] | `Br | `Code | `PCDATA ] elt

Function after modification:

let rec convert_inline : Inline.t -> 'a elt = function
  | Emphasis _ -> txt "nope"  (* convert_emphasis e *)
  | Break_Line -> br ()
  | Hard_Break_Line -> br ()
  | Verbatim _ -> txt "nyi verbatim"
  | Code s -> code [txt s]
  | Tag _ -> txt "nyi tag"
  | Spaces _ -> txt "nyi spaces"
  | Plain s -> txt s
  | Link link -> convert_link link
  | Nested_link _ -> txt "nyi link"
  | Target _ -> txt "nyi target"
  | Subscript _ -> txt "nyi subscript"
  | Superscript _ -> txt "nyi subscript"
  | Footnote_Reference _ -> txt "nyi footnote"
  | Cookie _ -> txt "nyi cookie"
  | Latex_Fragment _ -> txt "nyi latext fragement"
  | Macro _ -> txt "nyi macro"
  | Entity _ -> txt "nyi entity"
  | Timestamp _ -> txt "nyi timestamp"
  | Radio_Target _ -> txt "nyi radio target"
  | Export_Snippet (_, _) -> txt "nyi snippet"
  | Inline_Source_Block _ -> txt "nyi inline"
  | Email _ -> txt "nyi email"
  | Inline_Hiccup _ -> txt "nyi hiccup"
  | Inline_Html _ -> txt "nyi inline html"
 
and convert_emphasis : Inline.emphasis -> 'a elt = fun e ->
  let (s, l) = e in
  match s with
    | `Bold -> b (List.map ~f:convert_inline l)
    | _ -> txt "nyi emphasis"

New inferred type: t -> [< Html_types.b_content_fun > `A `B `Br `Code `PCDATA ] elt.

This results in this very beginner friendly error message:

File "lib/to_html.ml", line 76, characters 32-68:
76 |   | Paragraph p -> Some (div @@ List.map ~f:(convert_inline $ fst) p)
                                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: This expression has type
         ([< `A of Html_types.phrasing_without_interactive
           | `Abbr
           | `Audio of
               Html_types.phrasing_without_media &
               Html_types.flow5_without_media
           | `Audio_interactive of
               Html_types.phrasing_without_media &
               Html_types.flow5_without_media
           | `B
           | `Bdo
           | `Br
           | `Button
           | `Canvas of Html_types.phrasing & Html_types.flow5
           | `Cite
           | `Code
           | `Command
           | `Datalist
           | `Del of Html_types.phrasing & Html_types.flow5
           | `Dfn
           | `Em
           | `Embed
           | `I
           | `Iframe
           | `Img
           | `Img_interactive
           | `Input
           | `Ins of Html_types.phrasing & Html_types.flow5
           | `Kbd
           | `Keygen
           | `Label
           | `Map of Html_types.phrasing & Html_types.flow5
           | `Mark
           | `Meter
           | `Noscript of
               Html_types.phrasing_without_noscript &
               Html_types.flow5_without_noscript
           | `Object of Html_types.phrasing & Html_types.flow5
           | `Object_interactive of Html_types.phrasing & Html_types.flow5
           | `Output
           | `PCDATA
           | `Picture
           | `Progress
           | `Q
           | `Ruby
           | `Samp
           | `Script
           | `Select
           | `Small
           | `Span
           | `Strong
           | `Sub
           | `Sup
           | `Svg
           | `Template
           | `Textarea
           | `Time
           | `U
           | `Var
           | `Video of
               Html_types.phrasing_without_media &
               Html_types.flow5_without_media
           | `Video_interactive of
               Html_types.phrasing_without_media &
               Html_types.flow5_without_media
           | `Wbr
           > `A `B `Br `Code `PCDATA ]
          as 'a)
         elt list
       but an expression was expected of type
         ([< `A of Html_types.flow5_without_interactive
           | `Abbr
           | `Audio of
               Html_types.flow5_without_media &
               Html_types.phrasing_without_media
           | `Audio_interactive of
               Html_types.flow5_without_media &
               Html_types.phrasing_without_media
           | `B
           | `Bdo
           | `Br
           | `Button
           | `Canvas of Html_types.flow5 & Html_types.phrasing
           | `Cite
           | `Code
           | `Command
           | `Datalist
           | `Del of Html_types.flow5 & Html_types.phrasing
           | `Dfn
           | `Em
           | `Embed
           | `I
           | `Iframe
           | `Img
           | `Img_interactive
           | `Input
           | `Ins of Html_types.flow5 & Html_types.phrasing
           | `Kbd
           | `Keygen
           | `Label
           | `Map of Html_types.flow5 & Html_types.phrasing
           | `Mark
           | `Meter
           | `Noscript of
               Html_types.flow5_without_noscript &
               Html_types.phrasing_without_noscript
           | `Object of Html_types.flow5 & Html_types.phrasing
           | `Object_interactive of Html_types.flow5 & Html_types.phrasing
           | `Output
           | `PCDATA
           | `Picture
           | `Progress
           | `Q
           | `Ruby
           | `Samp
           | `Script
           | `Select
           | `Small
           | `Span
           | `Strong
           | `Sub
           | `Sup
           | `Svg
           | `Template
           | `Textarea
           | `Time
           | `U
           | `Var
           | `Video of
               Html_types.flow5_without_media &
               Html_types.phrasing_without_media
           | `Video_interactive of
               Html_types.flow5_without_media &
               Html_types.phrasing_without_media
           | `Wbr
           > `B `Br `Code `PCDATA ]
          as 'b)
         elt list
       Type
         'a =
           [< `A of Html_types.phrasing_without_interactive
            | `Abbr
            | `Audio of
                Html_types.phrasing_without_media &
                Html_types.flow5_without_media
            | `Audio_interactive of
                Html_types.phrasing_without_media &
                Html_types.flow5_without_media
            | `B
            | `Bdo
            | `Br
            | `Button
            | `Canvas of Html_types.phrasing & Html_types.flow5
            | `Cite
            | `Code
            | `Command
            | `Datalist
            | `Del of Html_types.phrasing & Html_types.flow5
            | `Dfn
            | `Em
            | `Embed
            | `I
            | `Iframe
            | `Img
            | `Img_interactive
            | `Input
            | `Ins of Html_types.phrasing & Html_types.flow5
            | `Kbd
            | `Keygen
            | `Label
            | `Map of Html_types.phrasing & Html_types.flow5
            | `Mark
            | `Meter
            | `Noscript of
                Html_types.phrasing_without_noscript &
                Html_types.flow5_without_noscript
            | `Object of Html_types.phrasing & Html_types.flow5
            | `Object_interactive of Html_types.phrasing & Html_types.flow5
            | `Output
            | `PCDATA
            | `Picture
            | `Progress
            | `Q
            | `Ruby
            | `Samp
            | `Script
            | `Select
            | `Small
            | `Span
            | `Strong
            | `Sub
            | `Sup
            | `Svg
            | `Template
            | `Textarea
            | `Time
            | `U
            | `Var
            | `Video of
                Html_types.phrasing_without_media &
                Html_types.flow5_without_media
            | `Video_interactive of
                Html_types.phrasing_without_media &
                Html_types.flow5_without_media
            | `Wbr
            > `A `B `Br `Code `PCDATA ]
       is not compatible with type
         'b =
           [< `A of Html_types.flow5_without_interactive
            | `Abbr
            | `Audio of
                Html_types.flow5_without_media &
                Html_types.phrasing_without_media
            | `Audio_interactive of
                Html_types.flow5_without_media &
                Html_types.phrasing_without_media
            | `B
            | `Bdo
            | `Br
            | `Button
            | `Canvas of Html_types.flow5 & Html_types.phrasing
            | `Cite
            | `Code
            | `Command
            | `Datalist
            | `Del of Html_types.flow5 & Html_types.phrasing
            | `Dfn
            | `Em
            | `Embed
            | `I
            | `Iframe
            | `Img
            | `Img_interactive
            | `Input
            | `Ins of Html_types.flow5 & Html_types.phrasing
            | `Kbd
            | `Keygen
            | `Label
            | `Map of Html_types.flow5 & Html_types.phrasing
            | `Mark
            | `Meter
            | `Noscript of
                Html_types.flow5_without_noscript &
                Html_types.phrasing_without_noscript
            | `Object of Html_types.flow5 & Html_types.phrasing
            | `Object_interactive of Html_types.flow5 & Html_types.phrasing
            | `Output
            | `PCDATA
            | `Picture
            | `Progress
            | `Q
            | `Ruby
            | `Samp
            | `Script
            | `Select
            | `Small
            | `Span
            | `Strong
            | `Sub
            | `Sup
            | `Svg
            | `Template
            | `Textarea
            | `Time
            | `U
            | `Var
            | `Video of
                Html_types.flow5_without_media &
                Html_types.phrasing_without_media
            | `Video_interactive of
                Html_types.flow5_without_media &
                Html_types.phrasing_without_media
            | `Wbr
            > `B `Br `Code `PCDATA ] 
       Type
         Html_types.phrasing_without_interactive =
           [ `Abbr
           | `Audio of Html_types.phrasing_without_media
           | `B
           | `Bdo
           | `Br
           | `Canvas of Html_types.phrasing
           | `Cite
           | `Code
           | `Command
           | `Datalist
           | `Del of Html_types.phrasing
           | `Dfn
           | `Em
           | `I
           | `Img
           | `Ins of Html_types.phrasing
           | `Kbd
           | `Map of Html_types.phrasing
           | `Mark
           | `Meter
           | `Noscript of Html_types.phrasing_without_noscript
           | `Object of Html_types.phrasing
           | `PCDATA
           | `Picture
           | `Progress
           | `Q
           | `Ruby
           | `Samp
           | `Script
           | `Small
           | `Span
           | `Strong
           | `Sub
           | `Sup
           | `Svg
           | `Template
           | `Time
           | `U
           | `Var
           | `Video of Html_types.phrasing_without_media
           | `Wbr ]
       is not compatible with type
         Html_types.flow5_without_interactive =
           [ `Abbr
           | `Address
           | `Article
           | `Aside
           | `Audio of Html_types.flow5_without_media
           | `B
           | `Bdo
           | `Blockquote
           | `Br
           | `Button
           | `Canvas of Html_types.flow5
           | `Cite
           | `Code
           | `Command
           | `Datalist
           | `Del of Html_types.flow5
           | `Dfn
           | `Div
           | `Dl
           | `Em
           | `Fieldset
           | `Figure
           | `Footer
           | `Form
           | `H1
           | `H2
           | `H3
           | `H4
           | `H5
           | `H6
           | `Header
           | `Hgroup
           | `Hr
           | `I
           | `Img
           | `Input
           | `Ins of Html_types.flow5
           | `Kbd
           | `Keygen
           | `Label
           | `Main
           | `Map of Html_types.flow5
           | `Mark
           | `Menu
           | `Meter
           | `Nav
           | `Noscript of Html_types.flow5_without_noscript
           | `Object of Html_types.flow5
           | `Ol
           | `Output
           | `P
           | `PCDATA
           | `Picture
           | `Pre
           | `Progress
           | `Q
           | `Ruby
           | `Samp
           | `Script
           | `Section
           | `Select
           | `Small
           | `Span
           | `Strong
           | `Style
           | `Sub
           | `Sup
           | `Svg
           | `Table
           | `Template
           | `Textarea
           | `Time
           | `U
           | `Ul
           | `Var
           | `Video of Html_types.flow5_without_media
           | `Wbr ] 
       The first variant type does not allow tag(s)
       `Address, `Article, `Aside, `Blockquote, `Button, `Div, `Dl,
       `Fieldset, `Figure, `Footer, `Form, `H1, `H2, `H3, `H4, `H5, `H6,
       `Header, `Hgroup, `Hr, `Input, `Keygen, `Label, `Main, `Menu, `Nav,
       `Ol, `Output, `P, `Pre, `Section, `Select, `Style, `Table, `Textarea,
       `Ul

Note that the caller code compiled before the refactoring.

What is happening?

[davesnx]

It seems like it’s a common pitfall where the inference works too well against you.

Without getting much information from the code, it seems like convert_inline calls other functions, (potentially convert_link) and those functions might endup calling convert_inline (that’s why you wanted to add rec in the first place I assume), so the callers of convert_inline (indirectly) would need to take into account this.

To help you fix the error thought, I recommend adding type annotations into all your functions so the compiler will complain at the exact location.

[octachron]

@kttmm

|Bold → b (List.map ~f:convert_inline l)`

Calling convert_inline in this context means that the return type of convert_inline must always be compatible with the required type of b. Consequently, the type of convert_inline can be at most Html_types.b_contents_fun as indicated by the return type:

[< Html_types.b_content_fun > ...

To avoid this issue, one must annotate the type of the group of mutually recursive functions.
Generally, with recursive functions on polymorphic variants, such annotations are useful to avoid error snowballing into complex error messages. Here, such annotations are required because the definitions are polymorphically recursive: the constraint on the type of the result of convert_inline in the body of convert_inline should not be applied to the convert_inline function in general.

let rec convert_inline : 'a. Inline.t -> ( `[> Html_types.txt | `Br | `Code | `PCDATA ]  as 'a)  elt = function
  | Emphasis _ -> txt "nope"  (* convert_emphasis e *)
  | Break_Line -> br ()
  | Hard_Break_Line -> br ()
  | Verbatim _ -> txt "nyi verbatim"
  | Code s -> code [txt s]
  | Tag _ -> txt "nyi tag"
  | Spaces _ -> txt "nyi spaces"
  | Plain s -> txt s
  | Link link -> convert_link link
  | Nested_link _ -> txt "nyi link"
  | Target _ -> txt "nyi target"
  | Subscript _ -> txt "nyi subscript"
  | Superscript _ -> txt "nyi subscript"
  | Footnote_Reference _ -> txt "nyi footnote"
  | Cookie _ -> txt "nyi cookie"
  | Latex_Fragment _ -> txt "nyi latext fragement"
  | Macro _ -> txt "nyi macro"
  | Entity _ -> txt "nyi entity"
  | Timestamp _ -> txt "nyi timestamp"
  | Radio_Target _ -> txt "nyi radio target"
  | Export_Snippet (_, _) -> txt "nyi snippet"
  | Inline_Source_Block _ -> txt "nyi inline"
  | Email _ -> txt "nyi email"
  | Inline_Hiccup _ -> txt "nyi hiccup"
  | Inline_Html _ -> txt "nyi inline html"
 
and convert_emphasis : 'a. Inline.emphasis -> ([> Html_types.b | Html_types.txt]  as 'a) elt =
 fun (s,l) ->
  match s with
    | `Bold -> b (List.map ~f:convert_inline l)
    | _ -> txt "nyi emphasis"