基于另一个列表内容创建列表的列表

Question

我有2个列表。它们的长度总是相同，可能看起来就像这个玩具的例子。实际的内容是不可预测的。

val original = [1, 2, 0, 1, 1, 2] 
val elements = ["a","b","c","d","e","f"] 

我想创建以下列表：

val mappedList = [["c"],["a","d","e"],["b","f"]] 
        0   1   2 

所以该模式是在元素列表族元素，基于相同的位置元素的原始列表值。任何想法如何在SML中实现这一点？我不是在寻找这个确切数据的硬编码解决方案，而是一个通用的解决方案。

Answer 1

的一种方法是先写一个函数，它接受一个有序对如(2,"c")和有序对诸如

[(3,["a"]),(2,["b"]),(1,["a","e"])] 

的列表，并返回与上涨到适当的列表中的元素的修改列表（或创建如果不存在新的（键，列表）对），这样的结果会是这样的：

[(3,["a"]),(2,["c","b"]),(1,["a","e"])] 

以下功能的伎俩：

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); 

鉴于键列表和值的对应列表，你可以在键和值的相应拉链最后这个功能折叠：

fun group ks vs = foldl store [] (ListPair.zip(ks,vs)); 

例如，如果

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 

请注意，如果需要，您可以根据键对列表进行排序。

最后 - 如果你只是想组（逆转到列表中的原来的顺序一致）以下工作：

fun groups ks vs = map rev (#2 (ListPair.unzip (group ks vs))); 

例如，

- groups original elements; 
val it = [["a","d","e"],["b","f"],["c"]] : string list list 

上编辑：如果你想根据关键字（而不是它们出现的顺序）对最终答案进行排序，你可以使用@SimonShine的想法并按照排序顺序存储数据，或者你可以对group函数的输出进行排序。有点奇怪的是，SML Standard Basis Library lacks a built-in sort，但是标准实现有它们自己的分类（并且很容易编写你自己的）。例如，使用SML/NJ的排序，你可以这样写：

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; 

领先于预期：

- sortedGroups original elements; 
val it = [["c"],["a","d","e"],["b","f"]] : string list list 

Answer 2

与一般的战略，先形成对(k, vs)的一个列表，其中k是他们的价值分组和vs是元素，然后可以单独提取元素。约翰既然这样做，我会添加其他两件事情可以做：

1. 假设original : int list，插入排序的顺序对：

   fun group ks vs = 
       let fun insert ((k, v), []) = [(k, [v])] 
         | insert (k1v as (k1, v), items as ((k2vs as (k2, vs))::rest)) = 
          case Int.compare (k1, k2) of 
           LESS => (k1, [v]) :: items 
          | EQUAL => (k2, v::vs) :: rest 
          | GREATER => k2vs :: insert (k1v, rest) 
        fun extract (k, vs) = rev vs 
       in 
        map extract (List.foldl insert [] (ListPair.zip (ks, vs))) 
       end 
   

   这产生相同的结果作为例子：

   - val mappedList = group original elements; 
   > val mappedList = [["c"], ["a", "d", "e"], ["b", "f"]] : string list list 
   

   我有点不确定是否通过“实际内容不可预测”。您也意味着“该类型original和elements是不知道的。”所以：

   假设original : 'a list和一些cmp : 'a * 'a -> order存在：

   fun group cmp ks vs = 
       let fun insert ((k, v), []) = [(k, [v])] 
         | insert (k1v as (k1, v), items as ((k2vs as (k2, vs))::rest)) = 
          case cmp (k1, k2) of 
           LESS => (k1, [v]) :: items 
          | EQUAL => (k2, v::vs) :: rest 
          | GREATER => k2vs :: insert (k1v, rest) 
        fun extract (k, vs) = rev vs 
       in 
        map extract (List.foldl insert [] (ListPair.zip (ks, vs))) 
       end 
   

2. 使用树用于存储对：

   datatype 'a bintree = Empty | Node of 'a bintree * 'a * 'a bintree 
   
   (* post-order tree folding *) 
   fun fold f e Empty = e 
       | fold f e0 (Node (left, x, right)) = 
       let val e1 = fold f e0 right 
        val e2 = f (x, e1) 
        val e3 = fold f e2 left 
       in e3 end 
   
   fun group cmp ks vs = 
       let fun insert ((k, v), Empty) = Node (Empty, (k, [v]), Empty) 
         | insert (k1v as (k1, v), Node (left, k2vs as (k2, vs), right)) = 
          case cmp (k1, k2) of 
           LESS => Node (insert (k1v, left), k2vs, right) 
          | EQUAL => Node (left, (k2, v::vs), right) 
          | GREATER => Node (left, k2vs, insert (k1v, right)) 
        fun extract ((k, vs), result) = rev vs :: result 
       in 
        fold extract [] (List.foldl insert Empty (ListPair.zip (ks, vs))) 
       end