Skip to content

Instantly share code, notes, and snippets.

@artur-s
Last active November 4, 2017 16:13
Show Gist options
  • Save artur-s/a7e9d34dee2998e45dea95f043ae1ae8 to your computer and use it in GitHub Desktop.
Save artur-s/a7e9d34dee2998e45dea95f043ae1ae8 to your computer and use it in GitHub Desktop.
Diffs two lists preserving duplicates
module List
let rec diffDups minuend subtrahend =
let rec removeFirst i = function
| h::t -> if h = i then t else h::(removeFirst i t)
| [] -> []
match subtrahend with
| h::t -> diffDups (removeFirst h minuend) t
| [] -> minuend
#time
let test =
[ diffDups [] [1;2;3] = []
diffDups [1;2;3;2;4] [] = [1;2;3;2;4]
diffDups [1;2;3;2;4] [2;3] = [1;2;4]
diffDups ["a";"b"] ["a";"b"] = []
diffDups [5;6] [6;5] = []
diffDups [2;3] [1;2;3;2;4] = []
diffDups [1;2;1;2;4] [1;1] = [2;2;4]
diffDups ([0..10]@[10..100]) [0..10] = [10..100]
diffDups [1..2..300000] [1..2..299990] = [299991..2..300000]
]
|> List.forall id
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment