Remove same values from two lists and compare them using List.fold in F#

Although you say you are trying to use List.fold for this to understand it better, there is another List function that makes this simpler. This is to use List.except which is one of a number of methods that treats lists as sets.

let list1 = [1;2;3] 
let list2 = [1;2;3;4] 

let myFunc list1 list2= 
    list1 |> List.except list2, list2 |> List.except list1

printfn "%A" (myFunc list1 list2) 

[],[4]

If you want to understand List.fold here you could try and create an explicit implementation of except using List.fold. However, again, this is simpler to implement using List.filter.

let list1 = [1;2;3] 
let list2 = [1;2;3;4] 

let except exclude src =
    src |> List.filter (fun i -> exclude |> List.contains i |> not)

let myFuncCustom list1 list2 = 
    (list1 |> except list2), (list2 |> except list1)

printfn "%A" (myFuncCustom list1 list2)

[],[4]

So really you want to implement filter using List.fold. In this case you would actually need List.foldBack:

let filter f src =  
    List.foldBack (fun item filtered  -> 
        if f item then item :: filtered else filtered) src []

You can use List.fold but then results are reversed and you need to pipe this into List.rev. And note that List.fold only takes three arguments: the first a folder function; second the accumulator which becomes the output - in this case a list too; and, the last, the source list to fold over. (Let us expand List.contains as well):

    let list1 = [1;2;3] 
    let list2 = [1;2;3;4] 
    
    let rec contains item  = function
        | [] -> false
        | hd::tl when  hd = item -> true
        | hd::tl -> contains item tl
    
    let filter f src =  
        src 
        |> List.fold (fun filtered item  -> 
            if f item then item :: filtered else filtered) []
        |> List.rev
    
    let except exclude src =
        src |> filter (fun i -> exclude |> contains i |> not)
    
    let myFuncCustom list1 list2 = 
        (list1 |> except list2), (list2 |> except list1)
    
    printfn "%A" (myFuncCustom list1 list2)

    [],[4]

This should be what you want:

let difference list blacklist =
    let folder acc a =
        if List.contains a blacklist
        then acc
        else a::acc
    List.fold folder [] list

difference [1;2;3;4] [1;2;3] // [4]
difference [1;2;3] [1;2;3;4] // []

Looking at the code you posted, there seems to be some confusion on how fold works.

• the arguments to fold are
  • A function that somehow combines a given state with an element of the list. This function can be as simple as summing the two arguments together resulting in a single scalar or it can be something really complicated that creates some weird data structure.
  • An initial state which must be of the type that you want fold to produce
  • And, of course, the list you want to fold over
• Fold iterates the list, by calling your fold function for every element of the list.
• The first time your fold function is called, it will get the initial state. Every other time it will get the state produced from the previous iteration.
• Fold will return the last state that was produced by your fold function (or the initial state if the list is empty)

As your goal is to better understand fold I try to explain fold instead of explaining how you achive your goal.

fold is bacially a for loop for immutable data-types. It allows you to eliminate mutable variables. For example, lets assume you want to sum all values of an integer list. In an "imperative" style you are probaly used to write something like this.

(* This xs is used through all exampes *)
let xs = [1..10]

(* Example A1 *)
let mutable sum = 0
for x in xs do
    sum <- sum + x

(* sum = 55 *)

Before you loop through a list, you define a mutable sum and then mutate the sum and updating it on everey iteration. This is how you achive it with List.fold.

(* Example A2 *)
let sum =
    List.fold (fun sum x ->
        sum + x
    ) 0 xs

(* sum = 55 *)

You can think of List.fold as the following.

1. The function is the body of the loop that gets executed for every item in your list.
2. The second argument to List.fold (here 0) is the state you want to compute. This is the sum.
3. The last argument of List.fold is finally the list you want to traverse.

The function always gets two arguments. The state and the next item of your list. Your function must return the next state.

With the for-loop you also have state. But the state is outside of the for-loop and you achieve your goal by mutating the state.

You also can think of the List.fold by mentally mapping the values to the lambda function you provide. The second argument 0 will be sum in your lambda and x in your lambda is one value of xs. The result of your lambda is the sum for the next call.

Let's say you want to compute three things on the fly. A mutable version looks like this

(* Helper Function *)
let isEven x = x &&& 1 = 0

(* Example B1 *)
let mutable count = 0
let mutable evens = 0
let mutable sum   = 0

for x in xs do
    count <- count + 1

    if isEven x then
        evens <- evens + 1

    sum <- sum + x

(* count=10; evens=5; sum=55 *)

Here we compute the amount of values in a list, how many even values exists, and the sum in one go.

List.fold only allows one state, but the state can be a complex value. For example a tuple with three values. The same example with List.fold looks like this:

(* Example B2 *)
let count,evens,sum =
    List.fold (fun (count,evens,sum) x ->
        (count+1), (if isEven x then evens + 1 else evens), (sum + x)
    ) (0,0,0) xs

(* count=10; evens=5; sum=55 *)

To better understand fold it is crucial to understand recursion and immutable data-strucutres like how list works. You could implement fold yourself like this:

(* Self-defined fold *)
let rec myFold f state xs =
    match xs with
    | []      -> state
    | x::rest -> myFold f (f state x) rest

(* Example C *)
let sum = myFold (fun sum x -> sum + x) 0 xs

(* sum = 55 *)

fold just do two things, it checks if the list is empty and in that case returns the state. Or it removes one element from the top of your list and calls itself recursively by

1. Keeping the function.
2. Producing the next state with (f state x)
3. Use the remaining list rest

Maybe you wonder about performance. This is tail-recursive, and tail-recursive functions are basically turned into for-loops by the compiler. So it has no performance penalty compared to the code that mutate things.

This is at least the case in F#. Just a reminder, not every compiler or run-time for other languages support tail-recursion.