I have 2 lists. They will always be the same length with respect to each other and might look like this toy example. The actual content is not predictable.
val original = [1, 2, 0, 1, 1, 2]
val elements = ["a","b","c","d","e","f"]
I want to create the following list:
val mappedList = [["c"],["a","d","e"],["b","f"]]
0 1 2
So the pattern is to group elements in the elements list, based on the value of the same-position element in original list. Any idea how can I achieve this in SML? I am not looking for a hard coded solution for this exact data, but a general one.
One way is to first write a function which takes an ordered pair such as (2,"c") and a list of ordered pairs such as
[(3,["a"]),(2,["b"]),(1,["a","e"])]
and returns a modified list with the element tacked onto the appropriate list (or creates a new (key,list) pair if none exists) so that the result would look like:
[(3,["a"]),(2,["c","b"]),(1,["a","e"])]
The following function does the trick:
fun store ((k,v), []) = [(k,[v])]
| store ((k,v), (m,vs)::items) = if k = m
then (m,v::vs)::items
else (m,vs)::store ((k,v) ,items);
Given a list of keys and a corresponding list of values, you could fold this last function over the corresponding zip of the keys and values:
fun group ks vs = foldl store [] (ListPair.zip(ks,vs));
For example, if
val original = [1, 2, 0, 1, 1, 2];
val elements = ["a","b","c","d","e","f"];
- group original elements;
val it = [(1,["e","d","a"]),(2,["f","b"]),(0,["c"])] : (int * string list) list
Note that you could sort this list according to the keys if so desired.
Finally -- if you just want the groups (reversed to match their original order in the list) the following works:
fun groups ks vs = map rev (#2 (ListPair.unzip (group ks vs)));
For example,
- groups original elements;
val it = [["a","d","e"],["b","f"],["c"]] : string list list
On Edit: if you want the final answer to be sorted according to the keys (as opposed to the order in which they appear) you could use @SimonShine 's idea and store the data in sorted order, or you could sort the output of the group function. Somewhat oddly, the SML Standard Basis Library lacks a built-in sort, but the standard implementations have their own sorts (and it is easy enough to write your own). For example, using SML/NJ's sort you could write:
fun sortedGroups ks vs =
let
val g = group ks vs
val s = ListMergeSort.sort (fn ((i,_),(j,_)) => i>j) g
in
map rev (#2 (ListPair.unzip s))
end;
Leading to the expected:
- sortedGroups original elements;
val it = [["c"],["a","d","e"],["b","f"]] : string list list