Bimap (bi-directional map) implementation

Ecosystem
, ,
1

An implementation of a bimap, a map that is bi-directional and which any client code can use to look up keys if given values as well as traditional lookup of values given keys. Implemented using functors as a class and a module, with support for multi-maps as well as well as single-valued maps. Master branch uses Core. A no-core branch is a work-in-progress and needs re-writing. OUnit testing also implemented.

1 Like
2

With a moderate amount of non-trivial logic, this seems to be a prime for property-based testing and in particular Crowbar fuzzing. Have you tried to use crowbar?

There seems to be a fair amount of almost-duplication of logic between your module version (which implements an immutable interface) and your class version (which implements an imperative interface). Would you be able to refactor the code to eliminate the duplication? One approach would be to call the module implementation from your class module (which becomes simply an adapter); you could do this by hand (adding ! and := in the right places), but it could even be possible to write generaic adapter combinators, along the lines of

    let find = Pure.find |> (id @-> source @!-> id)
    let change = Pure.change |> (id @-> id @-> source @!-> sink) 
    let iter = Pure.iter |> (id @-> source @!-> id)

in the following proof-of-concept

module Pure : sig
  type key = bool
  type 'a data
  val create : 'a * 'a -> 'a data
  val find : key -> 'a data -> 'a
  val change : key -> 'a -> 'a data -> 'a data
  val iter : ('a -> unit) -> 'a data -> unit
end = struct
  type key = bool
  type 'a data = 'a * 'a
  let create (v1, v2) = (v1, v2)
  let find b (v1, v2) =
    if b then v1 else v2
  let change b v (v1, v2) =
    if b then (v, v2) else (v1, v)
  let iter f (v1, v2) =
    f v1;
    f v2;
    ()
end

let test (type a) (v1, v2) =
  let module Impure : sig
    val find : Pure.key -> a
    val change : Pure.key -> a -> unit
    val iter : (a -> unit) -> unit
  end = struct
    let state : a Pure.data ref = ref (Pure.create (v1, v2))
        
    let id x = x
    let sink result = state := result
    let source () = !state
    let (@->) c1 c2 f = fun x -> c2 (f (c1 x))
    let (@!->) c1 c2 f = c2 (f (c1 ()))

    let find = Pure.find |> (id @-> source @!-> id)
    let change = Pure.change |> (id @-> id @-> source @!-> sink) 
    let iter = Pure.iter |> (id @-> source @!-> id)
  end in
  ()
1 Like
3

I just took a look at Crowbar…had not heard of it. But at first glance it seems to be the way to go. I will incorporate it as soon as I get the chance.

Thank you for the excellent suggestions to reduce code duplication. I should have thought of that. Code duplication is the source of all evil (in coding). I like your first suggestion to make the class module an adapter for the other implementation if only because I’m not familiar with generic adapter combinators…yet.