F Sharp convert list of tuples into list of mapped tuples

Question

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

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

Basically, turn this:

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

into this:

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

in this form:

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

Any ideas? This isn't homework, just self-study and this one has me a bit stumped considering the form doesn't allow for accumulation.

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 handy for the toRel bit:

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

Usage:

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

Answer 2

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

Its also a good idea of doing this with recursion to learn to split a problem into more smaller problems to learn how to solve a bigger problem.

If you think in a recursive way, what you need todo is:

1. You remove the head of the list to get one element.
2. Then you create your tuple with the key and all values of the specified key
3. You remove all elements with they current key you processed and recurs on this list.
4. If you have an empty input list, your output is also empty.

So you start with:

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

You remove the first element of a list with List.head. But we also want to extract the tuple into its two components. You achieve this with

let k,v = List.head list

What we want to create is a new tuple that has the same key, but all values of the input list. We don't have that function yet, but we just assume we have a function valuesOf that we can pass a key and a list, and it just returns us all values of the defined key.

(k, (valuesOf k list))

In the first iteration of the input list you defined we would have 2 as k and we assume valuesOf 2 list returns ["b";"c"].

So the above code would return (2, ["b";"c"]) as a value. Now the recursive call. We again assume we have a function removeKey that we can pass a key and a list and it returns a new list with all elements of the specified key removed.

(removeKey k list)

As an example

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

should return

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

This new list that removeKey returns is the one you need to recurs on:

(group (removeKey k list))

You only have to put both pieces together. What you want to return is your new tuple with the recursive result.

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

and as one function.

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

We are not done yet, we still need to create valuesOf and 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 uses Pattern Matching to deconstruct the list, instead of using List.head or List.tail. We just check if the element has the specified key. If it has we return the current value concatenated with the remaining list. Otherwise we just return the result of the recursive call and drop the current value.

removeKey is similar. We check if they key of a tuple matches, if yes we drop the whole element and just return the recursive call otherwise we return the current element with the recursive call.

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)

and now we are done. Everything at once

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

The above functions are not tail-recursive. But you can re-write valuesOf and removeKey easily with List.fold or List.foldBack. Here I use List.fold as I assume it doesn't matter if the order of the elements changes.

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 cannot easily re-written with List.fold or List.foldBack because we need access to the whole list. But it is still not hard to achieve tail-recursion.

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

If you don't expect to have lists with thousands or more key,value pairs then you also can keep the non tail-recursive functions.

Even if it feels good to create smaller code with already provided functions like List.groupBy and List.map you should be able to create such kind of recursive functions yourself. Why?

An immutable linked list is a recursive defined data-structure and working with recursive functions is only natural. If you don't know how to create such functions yourself you run into trouble the moment you create your own recursive data-structures, because then you have zero pre-defined functions like groupBy and map you already can use. You must build those functions yourself.

Trying to rebuild the function defined in the List module or things like you described here are actually good ways of training that you should do yourself.