CODEWITHSUNDEEP
f#
Jammes
Jammes

Reputation: 291

Merging two lists in F#

I wrote this function which merges two lists together but as I'm fairly new to functional programming I was wondering whether there is a better (simpler) way to do it?

let a = ["a"; "b"; "c"]
let b = ["d"; "b"; "a"]

let merge a b =
    // take all a and add b
    List.fold (fun acc elem -> 
                     let alreadyContains = acc |> List.exists (fun item -> item = elem)
                     if alreadyContains = true then
                        acc
                     else 
                        elem :: acc |> List.rev
                     ) b a                

let test = merge a b

Expected result is: ["a"; "b"; "c"; "d"], I'm reverting the list in order to keep the original order. I thought I would be able to achieve the same using List.foldBack (and dropping List.rev) but it results in an error:

Type mismatch. Expecting a 'a
but given a 'a list
The resulting type would be infinite when unifying ''a' and ''a list'

Why is there a difference when using foldBack?

Upvotes: 2

Views: 8568

Answers (2)

Tomas Petricek
Tomas Petricek

Reputation: 243041

If I wanted to write this in a way that is similar to your original version (using fold), then the main change I would do is to move List.rev outside of the function (you are calling List.rev every time you add a new element, which is wrong if you're adding even number of elements!)

So, a solution very similar to yours would be:

let merge a b =
  (b, a) 
  ||> List.fold (fun acc elem -> 
        let alreadyContains = acc |> List.exists (fun item -> item = elem)
        if alreadyContains = true then acc
        else elem :: acc)   
  |> List.rev

This uses the double-pipe operator ||> to pass two parameters to the fold function (this is not necessary, but I find it a bit nicer) and then passes the result to List.rev.

Upvotes: 4

Patrick McDonald
Patrick McDonald

Reputation: 65421

You could use something like the following

let merge a b =
    a @ b
    |> Seq.distinct
    |> List.ofSeq

Note that this will preserve order and remove any duplicates.

In F# 4.0 this will be simplified to

let merge a b = a @ b |> List.distinct

Upvotes: 9

Related Questions