F Sharp將元組列表轉換爲映射元組列表

Question

聲明一個將對列表轉換爲關係的函數。在這種形式

[(2,["c";"b"]);(1,["a"])] 

：

type Relation<'a,'b> = ('a * 'b list) list 

基本上，把這個：

[(2,"c");(1,"a");(2,"b")] 

這個

toRel:(’a*’b) list -> Rel<’a,’b> 

任何想法？這不是家庭作業，只是自學，考慮到形式不允許積累，這個我有點難倒。

Answer 1

[(2,"c");(1,"a");(2,"b")] 
|> List.groupBy fst 
|> List.map (fun (x,y)->x,List.map snd y) 

結果：

[(2, ["c"; "b"]); (1, ["a"])] 

類型推斷是很方便的toRel位：

let toRel xs = 
    xs 
    |> List.groupBy fst 
    |> List.map (fun (x,y)->x,List.map snd y) 

用法：

toRel [(2,"c");(1,"a");(2,"b")] 

Answer 2

您可以使用各種內置的功能和改造重建行爲，但它也很好地掌握有關從頭開始構建特殊函數的遞歸基礎知識。

它也是一個很好的想法，通過遞歸來學習將問題分解爲更小的問題，以學習如何解決更大的問題。

如果你想在一個遞歸的方式，你需要什麼待辦事項是：

1. 您刪除列表中的頭部，以獲得一個元素。
2. 然後，使用鍵和指定鍵的所有值創建元組
3. 您可以刪除所有處理它們的元素，並使用它們處理當前鍵並在該列表上重複出現。
4. 如果您有一個空的輸入列表，您的輸出也是空的。

所以，你開始：

let rec group list = 
    if List.isEmpty list then [] 
    else 
     ??? 

你跟List.head刪除列表的第一個元素。但我們也想 將元組提取到它的兩個組件中。你有

let k,v = List.head list 

我們要創建什麼是具有相同的密鑰生成新的元組實現這一點，但是輸入列表中的所有值。我們還沒有這個功能，但我們假設我們有一個函數valuesOf，我們可以傳遞一個鍵和一個列表，並且它只是返回我們定義鍵的所有值。

(k, (valuesOf k list)) 

在您定義，我們將不得不2爲k和輸入列表中的第一次迭代，我們假設valuesOf 2 list回報["b";"c"]。

因此，上述代碼將返回(2, ["b";"c"])作爲值。現在遞歸調用。我們再次假設我們有一個函數removeKey，我們可以傳遞一個鍵和一個列表，並返回一個新列表，並刪除指定鍵的所有元素。

(removeKey k list) 

舉個例子

removeKey 2 [(1,"a");(2,"a");(2,"b");(3,"a")] 

應該返回

[(1,"a");(3,"a")] 

這個新名單removeKey的回報是你需要再次出現上一個：

(group (removeKey k list)) 

只有

你必須把機器人h件在一起。你想要返回的是你的新遞歸結果。

(k, (valuesOf k list)) :: (group (removeKey k list)) 

作爲一個功能。

let rec group list = 
    if List.isEmpty list then [] 
    else 
     let k,v = List.head list 
     (k, (valuesOf k list)) :: group (removeKey k list) 

我們還沒有完成，我們還需要創建valuesOf和removeKey。

let rec valuesOf key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then v :: (valuesOf key list) 
     else (valuesOf key list) 

valuesOf使用模式匹配，而不是使用List.head或List.tail解構名單。我們只是檢查元素是否具有指定的鍵。如果有，我們返回與剩餘列表連接的當前值。否則，我們只返回遞歸調用的結果並刪除當前值。

removeKey與此類似。我們檢查一個元組的鍵是否匹配，如果是，我們刪除整個元素，然後返回遞歸調用，否則我們用遞歸調用返回當前元素。

let rec removeKey key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then (removeKey key list) 
     else x :: (removeKey key list) 

現在我們完成了。全部一次

let rec valuesOf key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then v :: (valuesOf key list) 
     else (valuesOf key list) 

let rec removeKey key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then (removeKey key list) 
     else x :: (removeKey key list) 

let rec group list = 
    if List.isEmpty list then [] 
    else 
     let k,v = List.head list 
     (k, (valuesOf k list)) :: group (removeKey k list) 

group [(2,"c");(1,"a");(2,"b");(2,"d");(3,"a");(1,"b")] 
// returns: [(2, ["c"; "b"; "d"]); (1, ["a"; "b"]); (3, ["a"])] 

上述函數不是尾遞歸的。但是您可以用List.fold或List.foldBack輕鬆地重寫valuesOf和removeKey。這裏我使用List.fold，因爲我認爲元素的順序改變並不重要。

let valuesOf key list = 
    List.fold (fun acc (k,v) -> 
     if k = key 
     then v :: acc 
     else acc 
    ) [] list 

let removeKey key list = 
    List.fold (fun acc (k,v) -> 
     if k = key 
     then acc 
     else (k,v) :: acc 
    ) [] list 

group不能輕易與List.fold或List.foldBack重寫，因爲我們需要訪問整個列表。但是實現尾遞歸仍然不難。

let group list = 
    let rec loop result list = 
     if List.isEmpty list then result 
     else 
      let k,v = List.head list 
      loop 
       ((k, (valuesOf k list)) :: result) 
       (removeKey k list) 
    loop [] list 

如果您不希望列表中包含數千個或更多的鍵值對，那麼您還可以保留非尾遞歸函數。

即使感覺很好用已經提供的功能創建較小的代碼，如List.groupBy和List.map，您應該可以自己創建這種類型的遞歸函數。爲什麼？

不可變鏈接列表是一個遞歸定義的數據結構，使用遞歸函數是很自然的。如果你不知道如何自己創建這樣的函數，那麼當你創建你自己的遞歸數據結構的時候你就會遇到麻煩，因爲你已經可以使用零預定義的函數，如groupBy和map。你必須自己建立這些功能。

嘗試重建List模塊中定義的功能或您在此描述的類似事情，實際上是您應該自己完成的培訓的好方法。