Implementation of some functions in the Queue module

Community
1

Very simply put (I am really sorry if this is a naive question): why are some functions of the Queue module (standard library), namely copy, iter, and fold implemented using a pattern

  let f =
    let rec f ...
    in 
    fun q ...

?

To give a concrete example, the iter function is implemented as follows:

let iter =
  let rec iter f cell =
    match cell with
    | Nil -> ()
    | Cons { content; next } ->
      f content;
      iter f next
  in
  fun f q -> iter f q.first

Is there any memory or allocation trick behind these choices of implementations? In the case of iter what would be the difference with having

let iter f q =
  let rec iter f cell =
    match cell with
    | Nil -> ()
    | Cons { content; next } ->
      f content;
      iter f next
  in
  iter f q.first
2

The difference is that without optimisation, the second version allocates one closure for the inner iter function everytime the outer iter function is called.
With the native compiler the second version will be optimised into the first one anyway, but in bytecode you should be able to notice the extra allocation.

3 Likes
3

Ahh, interesting :slight_smile: It makes perfect sense, thank you so much for your answer!

I wounder, why can’t we find this pattern among other mother in the Standard Library? Is it the fact that Queue allocates more memory (given the representation of the data structure), hence we need to gain a little bit more somewhere else?

4

I suspect that it’s the only Stdlib module to have a recursive type wrapped in an outer record.
This means that one needs to write auxiliary recursive functions to traverse the inner structure, that do not need to be exported. In the other modules, I expect that the functions that are exported can be defined directly at toplevel, so no need for the inner function.
Have you seen other modules with the pattern let f x y = let rec f a b = ... in f x y or similar ? If so, you can propose to switch to the better pattern with fun x y -> f x y at the end, although I’m not sure it’s worth the trouble.