how to keep only 'stable' values in a list in F#

Question

I have the following data:

[ 0, +1, +1, +1, 0, +1, -1, -1, 0, -1, -1, -1, -1, +1, +1, -1, +1, +1, +1, +1, +1, +1, +1, 0]

and this is the output I want:

[ 0, +1, +1, +1, 0, 0, 0, 0, 0, -1, -1, -1, -1, 0, 0, 0, +1, +1, +1, +1, +1, +1, +1, 0]

in the source column, data can be +1, -1 or 0.

in the output, the +1s and -1s that have 3, or more, sequential occurrences can stay; the ones that do not, have to get converted to 0.

the Python/Pandas implementation is this:

s = df[data].where(df[data].groupby(df[data].ne(df[data].shift()).cumsum()).transform('size').ge(3), 0)

how can I implement this in F#?

Answer 1

Although the OP received two satisfactory answers already, there's also the synthesis of both approaches: recursion in Continuation Passing Style, as well as the basic fold operation, just recursively implemented.

Divided into a helper and a folder, it would work with any type that fulfills the equality and get_Zero constraints imposed by inlining. The helper replaces the contents of the accumulator with a generic zero value if these are not stable enough, and returns a function prepending them to whatever list will be presented as a second argument.

The folder will either accumulate equal values or construct a function that eventually composes the result.

let inline stabilizeGeneric zs =
    let stabilizePrepend acc =
        if List.length acc > 2 then acc
        else [for _ in acc -> LanguagePrimitives.GenericZero]
        |> List.append
    let rec loop k = function
    | x::xs, y::ys when x = y -> loop k (xs, x::y::ys)
    | x::xs, ys -> loop (k << stabilizePrepend ys) (xs, [x])
    | [], ys -> (k << stabilizePrepend ys) []
    loop id (zs, [])

[ 0; +1; +1; +1; 0; +1; -1; -1; 0; -1; -1; -1; -1; +1; +1; -1; +1; +1; +1; +1; +1; +1; +1; 0]
|> stabilizeGeneric
// val it : int list =
//   [0; 1; 1; 1; 0; 0; 0; 0; 0; -1; -1; -1; -1; 0; 0; 0; 1; 1; 1; 1; 1; 1; 1; 0]

Answer 2

Although the OP received a satisfactory answer I thought I demonstrate a more explicit technique implementing a stabilize function using List.fold

The idea here is that we iterate over the input stream using List.fold, this allows us to compute a state as we iterate. This state consists of 2 parts:

1. v, n: n is how many times v has been seen in row
2. vs: The aggregated stable list.

As long as the value processed is the same as v we increment n. If we see a 0 or a value different to v we prepend v n times on vs if n > 2 otherwise we prepend 0 n times.

In code it could look something like this:

let stabilize m input =
  // prepends v n-times on vs
  let rec prepend n v vs = if n > 0 then prepend (n - 1) v (v::vs) else vs

  // Returns 0 if n < m (not stable) otherwise v (stable)
  let stable n v = if n < m then 0 else v

  // fold a sequence of potentially integers into stable sequence
  //  v: value to check if stable, n: number of times v appeared in sequence, 
  //    vs: the aggregated stable sequence, u: next value to check
  let folder (v, n, vs) u =
    // Check invariant
    assert (n = 0 || (n > 0 && v <> 0))
    // n > 0 => we are checking if v is stable, if v = u increase n by 1
    if n > 0 && v = u then (u, n + 1, vs) 
    // u = 0, we have received a 0, prepend the checked sequence and reset v, n
    elif u = 0 then (0, 0, 0::prepend n (stable n v) vs)
    // u <> 0, we have a value we need to check, preprend the checked sequence and start checking u
    else (u, 1, prepend n (stable n v) vs)

  let (v, n, vs) = input |> List.fold folder (0, 0, [])

  // Handle the fold remainder
  let vs = prepend n (stable n v) vs

  // Result is reversed, so reverse it to get the result in the right order
  let vs = vs |> List.rev

  vs

[<EntryPoint>]
let main argv =
  let i = [0; +1; +1; +1; 0; +1; -1; -1; 0; -1; -1; -1; -1; +1; +1; -1; +1; +1; +1; +1; +1; +1; +1; 0]
  let e = [0; +1; +1; +1; 0; 0; 0; 0; 0; -1; -1; -1; -1; 0; 0; 0; +1; +1; +1; +1; +1; +1; +1; 0]

  let vs = stabilize 3 i

  printfn "Input   : %A" i
  printfn "Expected: %A" e
  printfn "Actual  : %A" vs
  printfn "Result  : %A" (vs = e)

  0

Answer 3

I don't think there is any easy way to do this using built-in F# functions. However, if you define one helper operation, then you can solve this nicely.

The helper is a function that I'll call groupAdjacentBy which groups together adjacent elements in the list based on some function that computes a grouping key. This is like List.groupBy, except that it groups elements that have the same key only as long as they are next to each other.

val groupAdjacentBy : ('a -> 'b) -> 'a list -> 'a list list 

The implementation of this for F# lists looks as follows:

module List =
  let groupAdjacentBy f list = 
    let rec loop k group acc list = 
      match list with 
      | [] when List.isEmpty group -> List.rev acc
      | [] -> List.rev ((List.rev group)::acc)
      | x::xs when f x = k -> loop k (x::group) acc xs 
      | x::xs when not (List.isEmpty group) -> loop (f x) [x] ((List.rev group)::acc) xs
      | x::xs -> loop (f x) [x] [] xs
    if List.isEmpty list then []
    else loop (f (List.head list)) [List.head list] [] (List.tail list)

Now you can solve your original problem by grouping adjacent elements that have the same value and replacing all groups smaller than 3 with groups of equal length containing zeros:

[ 0; +1; +1; +1; 0; +1; -1; -1; 0; -1; -1; -1; -1; 
  +1; +1; -1; +1; +1; +1; +1; +1; +1; +1; 0]
|> List.groupAdjacentBy id
|> List.map (fun group ->
  if List.length group >= 3 then group
  else List.map (fun _ -> 0) group)
|> List.concat