# Does this "partition" function have a name?

**URL:** <https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581>\
**Category:** Learning\
**Created:** [October 5, 2022, 8:53am UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581 "2022-10-05T08:53:08Z")\
**Posts on this page:** 18\
**Page:** 1

<div class="post-metadata">

**Author:** ![triangle-man](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/triangle-man/32/3847_2.png) [@triangle-man](https://discuss.ocaml.org/u/triangle-man)\
**Post date:** [October 5, 2022, 8:53am UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/1 "2022-10-05T08:53:08Z")

</div>

I often seem to need the following computation, or a variation:

Given a list of things, and a function from things to ints (say), return a map from ints to lists of things.

That is: partition a list into sublists, where each sublist consists of those things having the same value of `f thing`.

Does this have a name and is it in a standard library?

The standard library `Seq.partition` does the equivalent for `f`s that return a `boolean`, but not the general case. If I understand correctly, `Map.Make.of_seq` makes maps from sequences but replaces entries with the same key.

Many thanks!

---

<div class="post-metadata">

**Author:** ![vds](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/vds/32/2013_2.png) [@vds](https://discuss.ocaml.org/u/vds)\
**Post date:** [October 5, 2022, 9:30am UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/2 "2022-10-05T09:30:20Z")

</div>

Not really answering your question but I thought it was well-fitted for @art-w’s [doc.sherlocode.com](https://doc.sherlocode.com/?q=%3A%20(%27a%20-%3E%20int)%20-%3E%20%27a%20list%20-%3E%20_) tool which is a nice way to search the ecosystem for a specific type signature:

With the query `: ('a -> int) -> 'a list -> _` I was able to find one occurrence of a function performing a similar task: [lascar’s `Utils.ListExt.scatter : ('a -> int) -> 'a list -> 'a list array`](https://ocaml.org/p/lascar/0.7.0/doc/Utils/ListExt/index.html#val-scatter)

So at least one author called this “scatter” and it looks like it is not part of the standard library 🙂  
If I was to propose a name, maybe `n_partition` ?

---

<div class="post-metadata">

**Author:** ![dbuenzli](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/dbuenzli/32/18_2.png) [@dbuenzli](https://discuss.ocaml.org/u/dbuenzli)\
**Post date:** [October 5, 2022, 9:51am UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/3 "2022-10-05T09:51:18Z")

</div>

Don’t know if it’s in a standard library but usually I use the name `classify` for these kind of functions. Here’s [an example](https://github.com/b0-system/b0/blob/061eb173bcdf7ad49753b5c0323f040d03989695/src/std/b0_std.mli#L1069-L1076) which is slightly more general (a thing can belong to more than one class) than what you described.

---

<div class="post-metadata">

**Author:** ![triangle-man](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/triangle-man/32/3847_2.png) [@triangle-man](https://discuss.ocaml.org/u/triangle-man)\
**Post date:** [October 5, 2022, 10:07am UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/4 "2022-10-05T10:07:19Z")

</div>

Thanks both, that’s super helpful.

@dbuenzli : it will be very useful for me to read the code for your more general example as I am still getting to grips with the module system etc.

@vds: my corporate wifi is blocking sherlocode (who knows why) but I’m pretty confident I can get it unblocked and I was exactly trying to find such a lookup site.

---

<div class="post-metadata">

**Author:** ![JohnWhitington](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/johnwhitington/32/1884_2.png) [@JohnWhitington](https://discuss.ocaml.org/u/JohnWhitington)\
**Post date:** [October 5, 2022, 2:03pm UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/5 "2022-10-05T14:03:33Z")

</div>

I have these two functions in my standard utility file:

```auto
(* Returns elements for which p is true, until one is not, paired with the
remaining list. The same as [takewhile p l], [dropwhile p l], but requiring
only one pass over the list. *)
let cleavewhile p l =
  let rec cleavewhile_inner p l elts =
    match l with
    | [] -> List.rev elts, []
    | e::es ->
        if p e
          then cleavewhile_inner p es (e::elts)
          else List.rev elts, l
  in
    cleavewhile_inner p l []

(* Collate a list into a list of lists based upon a comparison function by which
it has already been sorted. e.g [collate compare [1; 2; 2; 3; 3]] calculates
[[[1]; [2;2]; [3;3]]]. *)
let collate cmp l =
  let rec collate_inner prev = function
    | [] -> List.rev prev
    | h::t ->
        let x, y = cleavewhile (fun a -> cmp h a = 0) (h::t) in
          collate_inner (x::prev) y
  in
    collate_inner [] l

```

So building `(f x, x)` pairs, collating them and then post-processing, we may write:

```auto
let collect f l =
  List.map
    (function [] -> assert false | (fx, x)::t -> (fx, x::List.map snd t))
    (collate (fun (a, b) (a', b') -> compare a a') (List.sort compare (List.map (fun x -> (f x, x)) l)))

```

And we get:

```auto
# collect (fun x -> x mod 3) [1; 2; 3; 4; 5; 6; 7; 8];;
- : (int * int list) list = [(0, [3; 6]); (1, [1; 4; 7]); (2, [2; 5; 8])]

```

The only conclusion I draw from this is that writing the function from scratch instead of building it from existing functions would be a lot neater…

---

<div class="post-metadata">

**Author:** ![sanette](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/sanette/32/1645_2.png) [@sanette](https://discuss.ocaml.org/u/sanette)\
**Post date:** [October 5, 2022, 3:14pm UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/6 "2022-10-05T15:14:01Z")

</div>

Something like this should work (for general, not-necessarily ordered keys), but I don’t know if this is efficient:

```ocaml
let partition f list =
  let table = Hashtbl.create (List.length list) in
  List.iter (fun x ->
      let y = f x in
      let q = match Hashtbl.find_opt table y with
        | None -> let q = Queue.create () in Hashtbl.add table y q; q
        | Some q -> q in
      Queue.add x q) list;
  Hashtbl.fold (fun y q ->
      List.cons (y, Queue.fold (fun l x -> x::l) [] q)) table []

```

```ocaml
# partition (fun x -> x mod 3) [1; 2; 3; 4; 5; 6; 7; 8];;
- : (int * int list) list = [(1, [7; 4; 1]); (0, [6; 3]); (2, [8; 5; 2])]

```

---

<div class="post-metadata">

**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\
**Post date:** [October 5, 2022, 3:26pm UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/7 "2022-10-05T15:26:51Z")

</div>

I’d use a `_ list ref` instead of a queue, in each bucket of the  
hashtbl, personally. Easier to add items to, and it turns into a list  
trivially at the end.

---

<div class="post-metadata">

**Author:** ![n4323](https://avatars.discourse-cdn.com/v4/letter/n/97f17d/32.png) [@n4323](https://discuss.ocaml.org/u/n4323)\
**Post date:** [October 5, 2022, 4:05pm UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/8 "2022-10-05T16:05:19Z")

</div>

In the context of dataframes, I believe this is called ‘groupby’. At least it’s called that in [Pandas](https://pandas.pydata.org/docs/reference/api/pandas.DataFrame.groupby.html). That’s a bloated version of the same core concept. Also [R](https://dplyr.tidyverse.org/reference/group_by.html) has it.

---

<div class="post-metadata">

**Author:** ![jhw](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/jhw/32/1639_2.png) [@jhw](https://discuss.ocaml.org/u/jhw)\
**Post date:** [October 5, 2022, 5:31pm UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/9 "2022-10-05T17:31:55Z")

</div>

Looks like a specialization of the more general `union-find` algorithm to me.

---

<div class="post-metadata">

**Author:** ![kit-ty-kate](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/kit-ty-kate/32/5953_2.png) [@kit-ty-kate](https://discuss.ocaml.org/u/kit-ty-kate)\
**Post date:** [October 5, 2022, 6:29pm UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/10 "2022-10-05T18:29:06Z")

</div>

> [@triangle-man](#):
>
> @vds: my corporate wifi is blocking sherlocode (who knows why) but I’m pretty confident I can get it unblocked and I was exactly trying to find such a lookup site.

In case you can’t get it unblocked you can always use `opam grep` instead

---

<div class="post-metadata">

**Author:** ![K\_N](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/k_n/32/2793_2.png) [@K\_N](https://discuss.ocaml.org/u/K_N)\
**Post date:** [October 5, 2022, 6:39pm UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/11 "2022-10-05T18:39:45Z")

</div>

As @n4323 said, this is just a `GROUP BY` in functional style. It has existed since SQL but in SQL  
you don’t have nested tables, you have to apply an aggregate function to each sub-collection to return a list of pair (key, scalar value). Other languages are not limited by this data-model so e.g. Python has it in its [itertools](https://docs.python.org/3/library/itertools.html#itertools.groupby) module and for instance [Spark](https://spark.apache.org/docs/latest/api/scala/org/apache/spark/rdd/PairRDDFunctions.html) has it too (with a gazillion variations).

---

<div class="post-metadata">

**Author:** ![nobrowser](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nobrowser/32/2099_2.png) [@nobrowser](https://discuss.ocaml.org/u/nobrowser)\
**Post date:** [October 5, 2022, 10:46pm UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/12 "2022-10-05T22:46:13Z")

</div>

This doesn’t seem like the right signature for this thing in general, though. What if the image of `f` is sparse? I think @triangle-man original idea of the result as a _map_ makes better sense. Or just a list of `('a list, int)` tuples.

–  
Ian

---

<div class="post-metadata">

**Author:** ![art-w](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/art-w/32/4728_2.png) [@art-w](https://discuss.ocaml.org/u/art-w)\
**Post date:** [October 5, 2022, 11:38pm UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/13 "2022-10-05T23:38:06Z")

</div>

I guess you could try searching for simpler variations on the type:

- [`: list -> list Map.Make.t`](https://doc.sherlocode.com/?q=%3A%20list%20-%3E%20list%20Map.Make.t) reveals `Core.Map.Make.of_alist_multi : (Key.t * 'a) list -> 'a list t`
- [`: list -> Hashtbl.t`](https://doc.sherlocode.com/?q=%3A%20list%20-%3E%20Hashtbl.t) for a lot of solutions, because Hashtbl already accumulates same-key values in a list (extractable with `find_all` [`: Hashtbl.t -> list`](https://doc.sherlocode.com/?q=%3A%20Hashtbl.t%20-%3E%20list))
- [`: ('a -> int) -> list -> list list`](https://doc.sherlocode.com/?q=%3A%20(%27a%20-%3E%20int)%20-%3E%20list%20-%3E%20list%20list) for some group-by-equality stuff, or [`: ('a -> 'b) -> list -> (list * 'b) list`](https://doc.sherlocode.com/?q=%3A+%28%27a+-%3E+%27b%29+-%3E+list+-%3E+%28list+*+%27b%29+list) for a more general `group_by` (not the first results though! ☹ )

It doesn’t seem so popular to obtain the group via an `('a -> key)` function though, but the more common `(key * 'a) list` is a List.map away 🙂

---

<div class="post-metadata">

**Author:** ![triangle-man](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/triangle-man/32/3847_2.png) [@triangle-man](https://discuss.ocaml.org/u/triangle-man)\
**Post date:** [October 6, 2022, 8:23am UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/14 "2022-10-06T08:23:46Z")

</div>

Just to say I really appreciate all the thoughts here. Thank you.

---

<div class="post-metadata">

**Author:** ![nobrowser](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/nobrowser/32/2099_2.png) [@nobrowser](https://discuss.ocaml.org/u/nobrowser)\
**Post date:** [October 18, 2022, 3:00am UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/15 "2022-10-18T03:00:16Z")

</div>

How funny, a couple of weeks later this blog:

[[Lazily Grouping in Haskell - Donnacha Oisín Kidney](https://doisinkidney.com/posts/2022-10-17-lazy-group-on.html)]

---

<div class="post-metadata">

**Author:** ![jhw](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/jhw/32/1639_2.png) [@jhw](https://discuss.ocaml.org/u/jhw)\
**Post date:** [October 18, 2022, 5:06am UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/16 "2022-10-18T05:06:22Z")

</div>

I’ll just drop this here. [https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf](https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf)

---

<div class="post-metadata">

**Author:** ![n4323](https://avatars.discourse-cdn.com/v4/letter/n/97f17d/32.png) [@n4323](https://discuss.ocaml.org/u/n4323)\
**Post date:** [October 20, 2022, 8:14am UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/17 "2022-10-20T08:14:19Z")

</div>

Does this exist on opam?

---

<div class="post-metadata">

**Author:** ![hyphenrf](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/hyphenrf/32/2733_2.png) [@hyphenrf](https://discuss.ocaml.org/u/hyphenrf)\
**Post date:** [October 20, 2022, 9:58pm UTC](https://discuss.ocaml.org/t/does-this-partition-function-have-a-name/10581/18 "2022-10-20T21:58:12Z")

</div>

> `opam grep`

What! TIL 😄