# Re: Factor

Factor: the language, the theory, and the practice.

## Group By

Friday, April 8, 2011

When dealing with sequences, it can be useful to “group” them based on some criteria into smaller sequences. I couldn’t find a word that quite solved my problem in Factor, so I wrote `group-by`:

``````USING: assocs kernel sequences ;

: group-by ( seq quot: ( elt -- key ) -- assoc )
H{ } clone [
[ push-at ] curry compose [ dup ] prepose each
] keep ; inline
``````

### Examples

For example, we could use it to split the first 20 numbers into two groups based on whether they are prime or not:

``````IN: scratchpad USE: math.primes

IN: scratchpad 20 <iota> [ prime? ] group-by .
H{
{ f V{ 0 1 4 6 8 9 10 12 14 15 16 18 } }
{ t V{ 2 3 5 7 11 13 17 19 } }
}
``````

Or, we could group the subsets of a string by their length:

``````IN: scratchpad USE: math.combinatorics

IN: scratchpad "abc" all-subsets [ length ] group-by .
H{
{ 0 V{ "" } }
{ 1 V{ "a" "b" "c" } }
{ 2 V{ "ab" "ac" "bc" } }
{ 3 V{ "abc" } }
}
``````

Or, group some random numbers by their bit-count:

``````IN: scratchpad USE: math.bitwise

IN: scratchpad 20 [ 100 random ] replicate
[ bit-count ] group-by .
H{
{ 1 V{ 32 1 32 4 } }
{ 2 V{ 12 } }
{ 3 V{ 13 74 56 98 44 } }
{ 4 V{ 83 30 45 46 75 77 } }
{ 5 V{ 61 59 61 } }
{ 6 V{ 63 } }
}
``````

### How it works

The Factor code is roughly equivalent to the following Python code:

``````from collections import defaultdict

def group_by(seq, f):
d = defaultdict(list)
for value in seq:
key = f(value)
d[key].append(value)
return d
``````

Let’s take it step-by-step. First, start defining a word (function) called `group-by`.

``````: group-by
``````

Next, define it to take two arguments, a sequence (list or array) of values and a quotation (anonymous function or lambda) that computes a key for each element, and outputs an assoc (association, map, or dict). Names here are used only for documentation, it could take a `foo` and `bar` and return a `baz`.

``````( seq quot: ( elt -- key ) -- assoc )
``````

The code inside the word is everything until the “`;`”. We want to output a hashtable, so we first create one by cloning an empty hashtable (`H{ }`).

``````H{ } clone
``````

We will compose a word that duplicates each element to compute a key that is used to push each element into an appropriate bucket (a vector) in the hashtable. The `push-at` word has the signature `( value key assoc -- )`. For example, if grouping by the length of a string, we want something that looks a bit like `[ dup length H{ } push-at ]`:

``````[ push-at ] curry compose [ dup ] prepose
``````

We then, apply this quotation to each element in the sequence:

``````each
``````

And, finally, we want to make sure that the hashtable that we created isn’t “consumed”, but kept on the stack as a return value.

``````[ ... ] keep ;
``````