-
Notifications
You must be signed in to change notification settings - Fork 6
/
p28.re
41 lines (37 loc) · 1.32 KB
/
p28.re
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/* Sorting a list of lists according to length of sublists
a) sort the elements of this list according to their length.
b) sort the elements of this list according to their length frequency
*/
let rec insert = (cmp, e, list) =>
switch list {
| [] => [e]
| [x, ...xs] as z => cmp(e, x) <= 0 ? [e, ...z] : [x, ...insert(cmp, e, xs)]
};
let rec sort = (cmp, list) =>
switch list {
| [] => []
| [x, ...xs] => insert(cmp, x, sort(cmp, xs))
};
/* Sorting according to length : prepend length, sort, remove length */
let length_sort = (lists) => {
let lists = List.map((list) => (List.length(list), list), lists);
let lists = sort((a, b) => compare(fst(a), fst(b)), lists);
List.map(snd, lists)
};
let rle = (list) => {
let rec aux = (count, acc, list) =>
switch list {
| [] => [] /* Can only be reached if original list is Leaf */
| [x] => [(x, count + 1), ...acc]
| [x, ...[y, ..._] as z] =>
x == y ? aux(count + 1, acc, z) : aux(0, [(x, count + 1), ...acc], z)
};
aux(0, [], list)
};
let frequency_sort = (lists) => {
let lengths = List.map(List.length, lists);
let freq = rle(sort(compare, lengths));
let by_freq = List.map((list) => (List.assoc(List.length(list), freq), list), lists);
let sorted = sort((a, b) => compare(fst(a), fst(b)), by_freq);
List.map(snd, sorted)
};