CODEWITHSUNDEEP
ocaml
user42493
user42493

Reputation: 1103

How to handle nested match expressions

I'm implementing a method in Ocaml to perform run-length encoding data compression of a list of a random type 'a. Consecutive elements that are the same in the list is compressed into the type defined in the beginning of the provided code. My provided code dosen't work. One of the reason that I think it doesn't work is if you look at the new line between the big chuck of the first match cases, the matched cases after the new line should belong to the upper matched cases. However, the compiler in learn Ocaml cannot recognize that. It automatically grouped the remaining matched statements(which were supposed to be for the first match) to the nested match statement.

This is one of the excise in Ocaml tutorial website(Question 13): "Implement the so-called run-length encoding data compression method directly. I.e. don't explicitly create the sublists containing the duplicates, as in problem "Pack consecutive duplicates of list elements into sublists", but only count them. As in problem "Modified run-length encoding", simplify the result list by replacing the singleton lists (1 X) by X."

type 'a rle =
  | One of 'a
  | Many of int * 'a;;

let encodeDirect (l: 'a list)=
  let rec helper current acc ll=
    match ll with
    |[] -> current::acc
    |[a]-> match current with
      |None -> (Some(One a))::acc 
      |Some(One q) -> (Some(Many(2,q)))::acc
      |Some(Many(t,y)) -> (Some(Many(t+1,y)))::acc 

      |a::(m::ls as e) -> if a=m then match current with 
      |None -> helper (Some(One a)) acc e
      |Some(One q) -> helper (Some(Many(2,q)))  acc e
      |Some(Many(t,y)) -> helper (Some(Many(t+1,y))) acc e
      else match current with 
        |None -> helper None (Some(One a)::acc) e
        |Some(One q) -> helper None (Some(Many(2,q))::acc)  e
        |Some(Many(t,y)) ->helper None (Some(Many(t+1,y))::acc) e
  in helper None [] l

Here is an example of how it should work: encode ["a";"a";"a";"a";"b";"c";"c";"a";"a";"d";"e";"e";"e";"e"];; - : string rle list = [Many (4, "a"); One "b"; Many (2, "c"); Many (2, "a"); One "d"; Many (4, "e")]

Upvotes: 0

Views: 1152

Answers (1)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66818

I encounter this same problem with nested match pretty often. You can solve it by parenthesizing the inner match.

type 'a rle =
| One of 'a
| Many of int * 'a;;

let rec helper current acc ll=
  match ll with
  |[] -> current::acc
  |[a]->
    (match current with
    |None -> (Some(One a))::acc 
    |Some(One q) -> (Some(Many(2,q)))::acc
    |Some(Many(t,y)) -> (Some(Many(t+1,y)))::acc 
    )
  |a::(m::ls as e) ->
    if a=m then
      match current with 
      |None -> helper (Some(One a)) acc e
      |Some(One q) -> helper (Some(Many(2,q)))  acc e
      |Some(Many(t,y)) -> helper (Some(Many(t+1,y))) acc e
    else
      match current with 
      |None -> helper None (Some(One a)::acc) e
      |Some(One q) -> helper None (Some(Many(2,q))::acc)  e
      |Some(Many(t,y)) ->helper None (Some(Many(t+1,y))::acc) e

Upvotes: 1

Related Questions