基於另一個列表內容創建列表的列表

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