# Efficiently checking if Map/Set is singleton?

**URL:** <https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611>\
**Category:** Learning\
**Tags:** core, stdlib, base\
**Created:** [February 22, 2018, 7:30pm UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611 "2018-02-22T19:30:19Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![smolkaj](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/smolkaj/32/266_2.png) [@smolkaj](https://discuss.ocaml.org/u/smolkaj)\
**Post date:** [February 22, 2018, 7:30pm UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/1 "2018-02-22T19:30:19Z")

</div>

Map/Set provide O(1) `is_empty` functions, but they don’t provide `is_singleton` functions. Concretely, I would like O(1) functions

```auto
Set.(is_singleton : 'val t -> 'val option)
Map.(is_singlelton : ('key,'val) t -> ('key * 'val) option)

```

Maybe the `length` functions are guaranteed to be O(1), and so I can achieve this simply by using `is_length` followed by `to_list`?

---

<div class="post-metadata">

**Author:** ![bcc32](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/bcc32/32/203_2.png) [@bcc32](https://discuss.ocaml.org/u/bcc32)\
**Post date:** [February 22, 2018, 8:36pm UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/2 "2018-02-22T20:36:36Z")

</div>

Depends on whether you’re using the Core Map or the stdlib Map. Core’s (Base’s) Map and Set return `length` in O(1), but the stdlib’s are O(n).

```auto
┌──────────────┬─────────────┬────────────┐
│ Name │ Time/Run │ Percentage │
├──────────────┼─────────────┼────────────┤
│ stdlib:1 │ 9.56ns │ 0.02% │
│ stdlib:10 │ 51.94ns │ 0.10% │
│ stdlib:100 │ 505.01ns │ 0.92% │
│ stdlib:1000 │ 4_899.77ns │ 8.97% │
│ stdlib:10000 │ 54_595.93ns │ 100.00% │
│ core:1 │ 3.56ns │ │
│ core:10 │ 3.56ns │ │
│ core:100 │ 3.67ns │ │
│ core:1000 │ 3.52ns │ │
│ core:10000 │ 4.01ns │ │
└──────────────┴─────────────┴────────────┘

```

See [this gist](https://gist.github.com/bcc32/98e30ba0cecdd953572139a16d6a2e6c) for the benchmark. (compile with dune/jbuilder or `corebuild -pkg core_bench`).

---

<div class="post-metadata">

**Author:** ![smolkaj](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/smolkaj/32/266_2.png) [@smolkaj](https://discuss.ocaml.org/u/smolkaj)\
**Post date:** [February 22, 2018, 8:52pm UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/3 "2018-02-22T20:52:06Z")

</div>

I usually use Base/Core, so that will work for me.  
Seems like an embarrassing flaw in the standard library, though…

---

<div class="post-metadata">

**Author:** ![gsg](https://avatars.discourse-cdn.com/v4/letter/g/858c86/32.png) [@gsg](https://discuss.ocaml.org/u/gsg)\
**Post date:** [February 23, 2018, 4:17am UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/4 "2018-02-23T04:17:34Z")

</div>

For the stdlib you could always do something ugly like this:

```
module S = Set.Make (String)

exception Done

let sole_element set =
  let cell = ref None in
  begin try
      S.iter (fun x ->
          match !cell with
          | None -> cell := Some x
          | Some _ -> cell := None; raise Done)
        set;
    with Done -> ()
  end;
  !cell
```

---

<div class="post-metadata">

**Author:** ![jeffsco](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/jeffsco/32/45_2.png) [@jeffsco](https://discuss.ocaml.org/u/jeffsco)\
**Post date:** [February 23, 2018, 4:34am UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/5 "2018-02-23T04:34:55Z")

</div>

Here is another way to test for a singleton set in the standard lib:

```
module S = Set.Make(String)

let is_singleton s =
  try S.min_elt s = S.max_elt s with Not_found -> false

```

This doesn’t generalize nicely to arbitrary cardinality tests.

---

<div class="post-metadata">

**Author:** ![paurkedal](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/paurkedal/32/586_2.png) [@paurkedal](https://discuss.ocaml.org/u/paurkedal)\
**Post date:** [February 23, 2018, 7:58am UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/6 "2018-02-23T07:58:27Z")

</div>

One more using stdlib:

```ocaml
module String_set = struct
  include Set.Make (String)

  let is_singleton s =
    match choose_opt s with
    | None -> false
    | Some e -> equal s (singleton e)
end

```

---

<div class="post-metadata">

**Author:** ![let-def](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/let-def/32/2948_2.png) [@let-def](https://discuss.ocaml.org/u/let-def)\
**Post date:** [February 23, 2018, 9:35am UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/7 "2018-02-23T09:35:08Z")

</div>

```auto
(* O(log n), a bit less polymorphic than necessary as it depends on equality of keys.
    corrected: I thought it was O(1), gsg pointed out it is logarithmic. My bad! *)
let is_singleton s =
  match split (choose s) s with
  | exception Not_found -> false (* empty *)
  | (l, _, r) -> is_empty l && is_empty r

(* polymorphic (it depends only on the structure of the container, not on elements),
   but O(log n) as iter/fold has to traverse the left-most branch before starting to iterate *)
let is_singleton s =
  match fold (fun elt count -> if count > 0 then raise Exit else count + 1) s 0 with
  | 1 -> true
  | _ -> false
  | exception Exit -> false

```

Should work on Set and Map (slightly adapting the fold function, doesn’t depend on elements of the map).

---

<div class="post-metadata">

**Author:** ![let-def](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/let-def/32/2948_2.png) [@let-def](https://discuss.ocaml.org/u/let-def)\
**Post date:** [February 23, 2018, 10:16am UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/8 "2018-02-23T10:16:33Z")

</div>

Another variation, using `exists`/`for_all` functions, which dontt do in order traversal, thus are O(1) (in this case):

```auto
let is_singleton s =
  not (is_empty s) && 
  let count = ref 0 in for_all (fun _ -> incr count; !count = 1) s

```

---

<div class="post-metadata">

**Author:** ![gsg](https://avatars.discourse-cdn.com/v4/letter/g/858c86/32.png) [@gsg](https://discuss.ocaml.org/u/gsg)\
**Post date:** [February 23, 2018, 10:17am UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/9 "2018-02-23T10:17:05Z")

</div>

> O(1) for a reasonable implementation

`choose` is O(log n), though? That’s why it can guarantee equal elements for equal sets.

> O(log n) as iter/fold has to traverse the left-most branch

Nuts.

---

<div class="post-metadata">

**Author:** ![let-def](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/let-def/32/2948_2.png) [@let-def](https://discuss.ocaml.org/u/let-def)\
**Post date:** [February 23, 2018, 10:20am UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/10 "2018-02-23T10:20:13Z")

</div>

Arrgghh, you are right. `choose` is indeed `O(log n)` (would work with sets with a unique structure, such as patricia :P).  
It happens to be min\_elt in current implementation.

---

<div class="post-metadata">

**Author:** ![gsg](https://avatars.discourse-cdn.com/v4/letter/g/858c86/32.png) [@gsg](https://discuss.ocaml.org/u/gsg)\
**Post date:** [February 23, 2018, 10:30am UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/11 "2018-02-23T10:30:02Z")

</div>

Seems as if the `exists` approach is the least bad. I suppose that occasionally having to write this kind of ugly code is the downside of abstract data types with minimalist interfaces.

---

<div class="post-metadata">

**Author:** ![smolkaj](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/smolkaj/32/266_2.png) [@smolkaj](https://discuss.ocaml.org/u/smolkaj)\
**Post date:** [February 23, 2018, 5:35pm UTC](https://discuss.ocaml.org/t/efficiently-checking-if-map-set-is-singleton/1611/12 "2018-02-23T17:35:21Z")

</div>

Checking equality can be expensive in general, so I would like to avoid that.