pass type to module for abstract data type

Question

I am trying to create a heap module (and eventually priority queue) implemented with an array.

The portion of the heap I have written so far compiles fine:

module MinHeap = {
  type elem
  type heap = array<elem>

  let make = (): heap => []

  let insert = (h: heap, e: elem): heap => {
    Belt.Array.push(h, e)->ignore
    h
  }

  let next = (h: heap): option<elem> => Belt.Array.get(h, 0)
}

However I cannot instantiate it:

let h = MinHeap.make()
MinHeap.insert(h, 10)->ignore

The build fails with

FAILED: src/use-case-composites/heap-LogicParser.cmj

  We've found a bug for you!   /Users//projects//src/use-case-composites/heap.res:25:19-20

  23 │  
  24 │ let h = MinHeap.make() 
  25 │ MinHeap.insert(h, 10)->ignore 
  26 │ 

  This has type: int 
  Somewhere wanted: MinHeap.elem

There must be a away to pass types into modules. For example I am able to type option, but how do you do that in a custom module?

Answer 1

If you don't need any behaviour associated with the elem type, you could simply parameterize heap over it, the same way array is:

module MinHeap = {
  type heap<'elem> = array<'elem>

  let make = (): heap<_> => []

  let insert = (h: heap<'elem>, e: 'elem): heap<'elem> => {
    Belt.Array.push(h, e)->ignore
    h
  }

  let next = (h: heap<'elem>): option<'elem> => Belt.Array.get(h, 0)
}

Edit: To also answer your question of how to "pass a type into a module", you could do this using a functor:

module type Config = {
  type elem
}

module MinHeap = (Config: Config) => {
  type elem = Config.elem
  type heap = array<elem>

  let make = (): heap => []

  let insert = (h: heap, e: elem): heap => {
    Belt.Array.push(h, e)->ignore
    h
  }

  let next = (h: heap): option<elem> => Belt.Array.get(h, 0)
}

module IntMinHeap = MinHeap({
  type elem = int
})
let h = IntMinHeap.make()
IntMinHeap.insert(h, 10)->ignore

It seems a bit overkill for this use case though.