CODEWITHSUNDEEP
.netlistf#
Eugene
Eugene

Reputation: 143

Filtering a list based on a condition that depends on the value of multiple list elements

I have a list in F# that looks like this:

let x = [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0; 0; -1; -2; -3]

I need to write a function that returns the elements of the list that come before and including two consecutive 0's. It should return:

[10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0]

This would be pretty easy to do in a for loop in a non-functional language, but what's the correct functional way to approach this?

Upvotes: 1

Views: 100

Answers (4)

kaefer
kaefer

Reputation: 5741

You could also look at the problem from the other end.

Iterate the list in reverse order and drop elements seen so far if encountering two consecutive zeros, or return the whole list otherwise.

([10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0; 0; -1; -2; -3], [])
||> List.foldBack (fun x -> function
| 0::xs when x = 0 -> 0::0::[]
| xs -> x::xs )
// val it : int list = [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0]

Upvotes: 1

Tomas Petricek
Tomas Petricek

Reputation: 243051

In addition to the direct solution using recursion and the pairwise function, here is one solution using the general fold function, which looks quite readable:

x |> Seq.fold (fun (res, zs) el ->
  if zs = 2 then res, zs
  elif el = 0 then el::res, zs+1
  else el::res, 0 ) ([], 0) |> fst |> List.rev

The idea is to keep the elements collected so far (res) and the number of zero seen so far before the current element (zs). Once the number reaches 2, we ignore the rest of the list (this still iterates over the rest of the list, so there may be some overhead).

Upvotes: 0

MrD at KookerellaLtd
MrD at KookerellaLtd

Reputation: 2795

If you are learning fp you may prefer to do it directly (theres nothing wrong with doing it directly).

let x = [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0; 0; -1; -2; -3]

let rec find : int list -> int list = function
    | 0 :: 0 :: _ -> [ 0; 0 ]
    | head :: tail -> head :: find tail
    | _ -> []

let foo = find x

and get

val foo: int list = [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0]

Upvotes: 2

Brian Berns
Brian Berns

Reputation: 17038

There's no single "correct" solution, but here's one that uses built-in functions instead of recursion:

let snip list =
    list
        |> List.pairwise
        |> List.takeWhile (fun pair ->
             pair <> (0, 0))
        |> List.map fst
        |> fun list' -> list' @ [0; 0]

let x = [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0; 0; -1; -2; -3]
snip x
    |> printfn "%A"   // [10; 9; 8; 7; 7; 6; 6; 5; 5; 4; 4; 4; 3; 3; 2; 2; 1; 0; 0]

Or, if you like point-free style, you can do this:

let flip f b a = f a b

let snip =
    List.pairwise
        >> List.takeWhile ((<>) (0, 0))
        >> List.map fst
        >> flip List.append [0; 0]

Upvotes: 0

Related Questions