別のリストの内容に基づいてリストのリストを作成する

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

：最初kは彼らが価値あるペア(k, vs)のリストを形成するのが一般的な戦略で

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

Answer 2

グループ化され、vsが要素である場合、要素を単独で抽出することができます。ジョンはこれをしなかったので、私はあなたが行うことができる2つの他のものを追加します：

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 

これはあなたの例と同じ結果を生成します：

1. はoriginal : int listは、ソート順にペアを挿入することを想定します

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

   "実際のコンテンツは予測できません"とは少し分かりません。また、タイプのoriginalとelementsは知られていません。だから、：

   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