Modified run-length encoding in OCaml

Question

I tried to write my own solution to the modified run-length encoding problem which appends ether a single element or an tuple into a list with a user defined type.

During the iteration I pattern-match the amount of occurrence of each element (which is computed with the helper method count) against 1 or _. However I get a warning at the second last line because the appending of a tuple is not accepted.

type 'a rle_type = 
| One of 'a
| Many of int * 'a

(*hm for the amount of occurrences of a single element*)
let count e list = List.filter (fun x -> x=e ) list |> List.length

(*hm to delete dublicates*)
let rec compress = function
    | a :: (b :: _ as t) -> if a = b then compress t else a :: compress t
    | smaller -> smaller

let rle_mod list = 
  let rec aux lst enclst = 
    match lst with 
    | [] -> enclst
    | h :: t -> match (count h list) with 
                | 1 -> aux t (h :: enclst)
                | _ -> aux t ((count h list, h) :: enclst) 
in aux (List.rev list |> compress) 

I tried to manually specify the type of the list with (enclst : rle_type 'a) but it isn't working ether.
Do I have to modify the type definition to make it work?

As a reference for a better understanding, I already wrote the regular run-length encoding problem of the same site:

(*rle is using the same helper methods count and compress*)
    let rle list = 
      let rec aux lst enclst = 
        match lst with 
        | [] -> enclst
        | h :: t -> aux t ((count h list, h) :: enclst)
    in aux (List.rev list |> compress) []

Answer 1

You've defined

type 'a rle_type = 
| One of 'a
| Many of int * 'a

so you should actually use it:

....

    | h :: t -> match (count h list) with 
                | 1 -> aux t (One h :: enclst)
                | _ -> aux t (Many (count h list, h) :: enclst) 
....

Notice that using count is incorrect there, it counts all the occurrences of h in the whole list, not just the adjacent ones as the RLE should.

Answer 2

As noted in Will Ness' answer you need to use the rle_type type.

Note also that the count function is not necessary. You can instead pattern match on the original list and the accumulator list, directly representing the six possible meaningful combinations of state.

1. The original list is empty.
2. The original list is not empty, but the accumulator list is empty.
3. Both lists have at least one element, and the first element in the accumulator was constructed with One and it encodes the same value as the first element in the input list.
4. Both lists have at least one element, and the first element in the accumulator was constructed with One and it encodes a different value than the first element in the input list.
5. Both lists have at least one element, and the first element in the accumulator was constructed with Many and it encodes the same value as first element in the input list.
6. Both lists have at least one element, and the first element in the accumulator was constructed with Many and it encodes a different value than the first element in the input list.

type 'a encoding =
  | One of 'a
  | Many of int * 'a

let rec compress lst acc =
  match lst, acc with
  | []     , _                              -> List.rev acc
  | (x::xs), []                             -> compress xs [One x]
  | (x::xs), (One a::tl) when x = a         -> compress xs (Many (2, x) :: tl)
  | (x::xs), (One _::_)                     -> compress xs (One x :: acc)
  | (x::xs), (Many (c, a) :: tl) when x = a -> compress xs (Many (c+1, x) :: tl)
  | (x::xs), _                              -> compress xs (One x :: acc)

As we are transforming a list into another value one element at a time with this approach, it's readily adapted to use List.fold_left.

let compress lst = 
  List.(
    fold_left
      (fun i x ->
         match i with
         | [] -> [One x]
         | One a::tl when x = a -> Many (2, x)::tl
         | One _::_ -> One x::i
         | Many (c, a)::tl when x = a -> Many (c+1, x)::tl
         | _ -> One x::i)
      [] lst
      |> rev
  )