I tried to write my own solution for this exercise by iterating through a list with a empty complst list where all non duplicates are inserted into and then get returned. I know it is a over complicated approach after looking up the solution but would still like to understand why the pattern matching does not work as intended:

let compress list =
  let rec aux complst lst =
    match lst with 
    | [] -> complst
    | a :: (b :: c) -> if a = b then aux complst (b::c) else aux (a::complst) (b::c)
    | x -> x  
  in aux [] list;;
val comp : 'a list -> 'a list = <fun>

Regardless of the input, the output is always a list with only the last element:

 compress [1;1;2;2;3];;
- : int list = [3]

 compress [1;2;3];;
- : int list = [3]

CodePudding user response：

Pattern matching

Your pattern-matching matches against three patterns:

1. The empty list: []
2. The list with at least two elements: a :: (b :: c)
3. A catch-all, which must by process of elimination be a list with a single element.

Consider what happens when we evaluate your example:

compress [1; 1; 2; 2; 3]
aux [] [1; 1; 2; 2; 3]
aux [] [1; 2; 2; 3]
aux [1] [2; 2; 3]
aux [1] [2; 3]
aux [2; 1] [3]
[3]

Oops, as soon as it hit lst being [3] it just returned it.

Let's rewrite your function to handle that single element list by adding to complst.

let compress lst =
  let rec aux complst lst =
    match lst with 
    | [] -> complst
    | [x] -> aux (x::complst) []
    | a :: (b :: c) -> 
      if a = b then aux complst (b::c) 
      else aux (a::complst) (b::c)
  in 
  aux [] list

Now:

compress [1; 1; 2; 2; 3]
aux [] [1; 1; 2; 2; 3]
aux [] [1; 2; 2; 3]
aux [1] [2; 2; 3]
aux [1] [2; 3]
aux [2; 1] [3]
aux [3; 2; 1] []
[3; 2; 1]

Clean up and reversing the resulting list

Of course, there are also ways to clean up your code a bit using a conditional guard and _ for values you don't need to bind names to. You probably also want to reverse your accumulator.

let compress lst =
  let rec aux complst lst =
    match lst with 
    | [] -> List.rev complst
    | [x] -> aux (x::complst) []
    | a :: (b :: _ as tl) when a = b -> aux complst tl
    | a :: (_ :: _ as tl) -> aux (a::complst) tl   
  in
  aux [] lst

Fold

When you see this pattern of iterating over a list one element at a time and accumulating a new value, you can usually map that pretty well to List.fold_left.

let compress lst =
  List.(
    fold_left 
      (fun i x -> 
         match i with 
         | (x'::_) when x = x' -> i 
         | _ -> x::i) 
      [] lst 
    |> rev
  )

Because List.fold_left can only be aware of one element at a time on the list, the function we pass as its first argument can't be aware of the next element in the list. But it is aware of the accumulator or "init" value. In this case that's another list, and we can pattern match out that list.

If it's not empty and the first element is equal to the current element we're looking at, don't add it to the result list. Otherwise, do add it. This also handles the first element case where the accumulator is empty.

Kudos on creating a tail-recursive solution to this problem!

CodePudding user response：

The problem with your code here is mainly the last part, which corresponds to when you have the last element in your list so here [3], and you return that list with this single element. What you need to do instead is append it to complst like this :

let compress list =
  let rec aux complst lst =
    match lst with 
    | [] -> complst
    | a :: (b :: c ) -> if a=b then aux complst (b::c) else  aux (a::complst) (b::c)
    | x::e -> x::complst 
  in aux [] list;;
val comp : 'a list -> 'a list = <fun>

Now you can check with the given example :

compress [1;1;2;2;3];;
- : int list = [3; 2; 1]

Hope it helps you understand your mistake better.

Note regarding comments: you should keep the [] case, because although it can only happen in one scenario, it is still a valid input meaning it must be kept!.