F Sharp converts a list of tuples to a list of displayed tuples

Question

Declare a function that converts a list of pairs to Relation.

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

Basically do the following:

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

in it:

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

in this form:

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

Any ideas? This is not homework, just self-study, and it puzzles me a bit, given that the form does not allow to accumulate.

Answer 1

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

Result:

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

Type inference is convenient for the toRel bit:

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

Using:

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

Answer 2

You can use various built-in functions and transform to rebuild the behavior, but it is also good to have basic knowledge of recursion to create special functions from scratch.

, , , .

, todo:

• , .
• , , .
• , .

, :

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

. , , - .

(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 Pattern Matching 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"])]

. valuesOf removeKey List.fold List.foldBack. 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, , , , .