Help with Belt.Map.Dict

1

Hi,

I am having an error with the following code.
I would like to know how to resolve it. A way to create Belt.Id.cmp for a type parameter?
Thank you.

let foo: ('v, 'v => 'k) => () = (value, projection) => {
  
  module KeyCmp = Belt.Id.MakeComparable({
    type t = 'k // error msg : Unbound type parameter 'k
    let cmp = Pervasives.compare
  })

  let dict: Belt.Map.Dict.t<'k, 'v, _> = Belt.Map.Dict.empty
  let resDict: Belt.Map.Dict.t<'k, 'v, _> = Belt.Map.Dict.set(dict, projection(value), value, ~cmp=KeyCmp.cmp)
  Js.log(resDict)
}

Regards,
Jazz

2

Hello! What are you trying to do?

That type isn’t gonna work the way you think it will. I suggest you start with a concrete use-case before abstracting over it. Aka just make a single KeyCmp with a concrete type.

1 Like
3

Hi @chenglou,

Thank you for your reply.

I am trying to write a utility method for array as follow:
Instead of using array<('key,int)>, i was trying to use Belt.Map.Dict as i mentioned above because i think Dict is faster for lookup than findIndex.
Looking for suggestion. Thanks!

open Js.Array2

let countBy: (array<'a>, 'a => 'key) => array<('key, int)> = (arr, projection) => {
  let len = arr->length
  if len == 0 {
    ([]: array<('key, int)>)
  } else {
    let result: array<('key, int)> = []

    for i in 0 to len - 1 {
      let key = projection(arr[i])
      let idx = result->findIndex(x => {
        let (k, _) = x
        k == key
      })
      if idx > -1 {
        let (k, v) = result[idx]
        result[idx] = (k, v + 1)
      } else {
        result->push((key, 1))->ignore
      }
    }

    result
  }
}


let log = Js.log
log([{"Lang": "OCaml", "Score": 10}, {"Lang": "ReScript", "Score": 10}, 
{"Lang": "OCaml", "Score": 10}, {"Lang": "TypeScript", "Score": 4}]->countBy(x => x))

// result =>
/*
[
  [ { Lang: 'OCaml', Score: 10 }, 2 ],
  [ { Lang: 'ReScript', Score: 10 }, 1 ],
  [ { Lang: 'TypeScript', Score: 4 }, 1 ]
]
*/
4

Might wanna measure that first. Also, since Belt.Map.Dict requires a comparator, it means your array can be sorted too. So you might wanna just keep the array sorted *, then use the sort functions in Belt.SortArray. Now you’ll end up with a much simpler, faster and interoperable data structure.

* Belt.Map.Dict is backed by a binary tree, so either way you’ll end up sorting.

But yeah. Measure! I doubt your MapDict is gonna be faster than an array binary search or even a linear scan, under a certain threshold. Caches and all.

2 Likes
5

@chenglou is probably correct that Belt.Map.Dict may not be the best tool for this job. But for the sake of learning, here’s how you would solve the problem in the OP:

You need to use a “locally abstract type.” As you can see from the error message, polymorphic type parameters in function signatures aren’t accessible inside of the function bodies. However, you can declare a fresh abstract type alongside the arguments and use that inside the function.

// note type k and v
let foo = (type k v, value: v, projection: v => k) => {
  module KeyCmp = Belt.Id.MakeComparable({
    type t = k
    let cmp = compare
  })
  let dict = Belt.Map.Dict.empty
  let resDict = Belt.Map.Dict.set(dict, projection(value), value, ~cmp=KeyCmp.cmp)
  Js.log(resDict)
}

Locally abstract types are a bit of an advanced feature and make maintaining the code more complicated, so I’m not sure this is a good example that justifies using them. It would make more sense to define your KeyCmp module somewhere before calling your foo function, and just passing the cmp value as a parameter. Then no type annotations are needed anymore.

let bar = (value, projection, ~cmp) => {
  let dict = Belt.Map.Dict.empty
  let resDict = Belt.Map.Dict.set(dict, projection(value), value, ~cmp)
  Js.log(resDict)
}

Playground link.

You probably don’t want to be using functors inside functions most of the time. I assume all of your types are defined somewhere in a module already, so it’s much simpler to just call Belt.Id.MakeComparable alongside those type definitions, and then reference that whenever you need to use it. That’s simpler to maintain, and also makes more sense from a performance perspective.

A side note: if you’re concerned about performance, then the built-in polymorphic compare function is probably not a good idea. You should provide your own compare function that’s specific for the type you’re using.

3 Likes
6

Thank you @johnj. That’s i what i am looking for. I learned a new thing today. :smile: