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模块中定义的功能或您在此描述的类似事情，实际上是您应该自己完成的培训的好方法。