Haskell list difference operator in F#
-
09-06-2019 - |
Question
Is there an equivalent operator to Haskell's list difference operator \\
in F#?
Solution
Was bounced, yet I believe it is worth to write here the implementation of ( /-/ )
(the F# version of Haskell's \\
):
let flip f x y = f y x
let rec delete x = function
| [] -> []
| h :: t when x = h -> t
| h :: t -> h :: delete x t
let inline ( /-/ ) xs ys = List.fold (flip delete) xs ys
This will operate as Haskell's \\
, so that (xs @ ys) /-/ xs = ys
. For example: (7 :: [1 .. 5] @ [5 .. 11]) /-/ [4 .. 7]
evaluates into [1; 2; 3; 5; 7; 8; 9; 10; 11]
.
OTHER TIPS
Nope... Just write it and make it an infix operator --using the set of special characters. Backslash (\
) is not in the list below, so it will not work as an infix operator. See the manual:
infix-op :=
or || & && <OP >OP $OP = |OP &OP ^OP :: -OP +OP *OP /OP %OP **OP
prefix-op :=
!OP ?OP ~OP -OP +OP % %% & &&
Filter items from the set of the subtrahend:
let ( /-/ ) xs ys =
let ySet = set ys
let notInYSet x = not <| Set.contains x ySet
List.filter notInYSet xs
I'm using this:
let (/-/) l1 l2 = List.filter (fun i -> not <| List.exists ((=) i) l2) l1
If anyone sees a problem, let me know.
Is for lists, so there could be duplicates in the result. For example:
[1;1;2] /-/ [2;3] would be eq to [1;1]
Assuming you really want conventional set difference rather than the weird ordered-but-unsorted multiset subtraction that Haskell apparently provides, just convert the lists to sets using the built-in set
function and then use the built-in -
operator to compute the set difference:
set xs - set ys
For example:
> set [1..5] - set [2..4];;
val it : Set<int> = seq [1; 5]