F # build list / array of values ​​+ consecutive duplicates

Question

I need to collect such data:

let data = [1; 2; 2; 3; 2; 2; 2; 4] let packed = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)] 

Where each item says how many times it exists until the next. However, it must work with non-contiguous duplications.

I can work with classic imperative code, but I wonder how this happens.

In addition, Seq.countBy does not work because it takes all values ​​into account.

Answer 1

If you already have an imperative version, you can follow many small steps to the rector for a recursive implementation .

Recursion

While I don't know what your imperative version looks like, here's a recursive version:

 let pack xs = let rec imp acc = function | [] -> acc | h::t -> match acc with | [] -> imp [(h, 1)] t | (i, count) :: ta -> if h = i then imp ((i, count + 1) :: ta) t else imp ((h, 1) :: (i, count) :: ta) t xs |> imp [] |> List.rev 

This function is of type 'a list -> ('a * int) list when 'a : equality . To do this, a private "implementation function" called imp . This function is recursive and overlays the drive (called acc ). This drive is a list of results of type ('a * int) list .

If the battery list is empty, the head of the original list ( h ), as well as counter 1 is created as a tuple as the only element of the updated battery, and the imp function is recursively called with this updated battery.

If the drive already contains at least one element, the element is extracted using pattern matching, and the element in this tuple ( i ) is compared with h . If h = i , the battery is updated; otherwise, the new tuple is considered acc . In both cases, however, imp recursively called with a new battery.

You can call it with a list equivalent to the original tuple, for example:

 > pack [1; 2; 2; 3; 2; 2; 2; 4];; val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)] 

Fold

Once you have a recursive version, you often have a recipe for a version that uses a fold. In this case, since the pack function above should cancel the drive at the end (using List.rev ), the correct fold is most suitable. In F #, this is done with the built-in List.foldBack function:

 let pack' xs = let imp x = function | (i, count) :: ta when i = x -> (i, count + 1) :: ta | ta -> (x, 1) :: ta List.foldBack imp xs [] 

In this case, the function passed to List.foldBack is too complex to pass as an anonymous function, so I decided to define it as a private internal function. This is equivalent to the recursive imp function used by the above pack function, but you'll know that it doesn't need to call itself recursively. Instead, you just need to return the new value for the battery.

The result is the same:

 > pack' [1; 2; 2; 3; 2; 2; 2; 4];; val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)] 

Answer 2

My solution assumes the data collection is a list. If you had it as a tuple (in accordance with your example), it was intentional, then for my solution to work, the tuple should be converted to a list (an example of how to do this can be found here ).

 let groupFunc list = let rec groupFuncRec acc lst init count = match lst with | [] -> List.rev acc | head::[] when head = init -> groupFuncRec ((init, count)::acc) [] 0 0 | head::[] when head <> init -> groupFuncRec ((head, 1)::acc) [] 0 0 | head::tail when head = init -> groupFuncRec acc tail head (count+1) | head::tail when head <> init -> groupFuncRec ((init, count)::acc) tail head 1 let t = List.tail list let h = List.head list groupFuncRec [] th 1 

When I run the function in your sample data, I return the expected result:

  list = [(1, 1); (2, 2); (3, 1); (4, 1)] 

Answer 3

You can get Seq.countBy to work by including some positional information in your argument. Of course, you need to then return to the original data.

 [1; 2; 2; 3; 2; 2; 2; 4] |> Seq.scan (fun (s, i) x -> match s with | Some p when p = x -> Some x, i | _ -> Some x, i + 1 ) (None, 0) |> Seq.countBy id |> Seq.choose (function | (Some t, _), n -> Some(t, n) | _ -> None ) |> Seq.toList // val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)]