# Bimap (bi-directional map) implementation

**URL:** <https://discuss.ocaml.org/t/bimap-bi-directional-map-implementation/3776>\
**Category:** Ecosystem\
**Tags:** datastructures, library, announce\
**Created:** [May 9, 2019, 3:21am UTC](https://discuss.ocaml.org/t/bimap-bi-directional-map-implementation/3776 "2019-05-09T03:21:22Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![papatango](https://avatars.discourse-cdn.com/v4/letter/p/b782af/32.png) [@papatango](https://discuss.ocaml.org/u/papatango)\
**Post date:** [May 9, 2019, 3:21am UTC](https://discuss.ocaml.org/t/bimap-bi-directional-map-implementation/3776/1 "2019-05-09T03:21:22Z")

</div>

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.

> **[pat227/bimap](https://github.com/pat227/bimap)**
>
> Contribute to pat227/bimap development by creating an account on GitHub.

---

<div class="post-metadata">

**Author:** ![gasche](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gasche/32/4_2.png) [@gasche](https://discuss.ocaml.org/u/gasche)\
**Post date:** [May 14, 2019, 9:02am UTC](https://discuss.ocaml.org/t/bimap-bi-directional-map-implementation/3776/2 "2019-05-14T09:02:44Z")

</div>

With a moderate amount of non-trivial logic, this seems to be a prime for property-based testing and in particular [Crowbar](https://github.com/stedolan/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

```ocaml
    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

```auto
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
  ()

```

---

<div class="post-metadata">

**Author:** ![papatango](https://avatars.discourse-cdn.com/v4/letter/p/b782af/32.png) [@papatango](https://discuss.ocaml.org/u/papatango)\
**Post date:** [May 15, 2019, 2:36am UTC](https://discuss.ocaml.org/t/bimap-bi-directional-map-implementation/3776/3 "2019-05-15T02:36:46Z")

</div>

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.