how to do Seq.takeWhile + one item in F#

Question

I would like to write a function which filters a sequence using a predicate but the result should also INCLUDE the first item for which the predicate returns false.

The logic would be something like this, if there was a break keyword in F#

let myFilter predicate s =
    seq {
        for item in s do
            yield item
            if predicate item then
                break
    }

I tried combinations of Seq.takeWhile and Seq.skipWhile, something like this:

Seq.append 
    (Seq.takeWhile predicate s) 
    (Seq.skipWhile predicate s |> Seq.take 1)

...but the problem is that the first item which matches the predicate is lost between the takeWhile and the skipWhile

Also note that the input sequence is lazy so any solution which consumes the sequence and takes decisions afterwards is not viable.

Any ideas?

Thanks!

EDIT: Thanks a LOT for all the answers! I didn't expect so many responses so fast. I will take a look at each of them soon. Now I just want to give a little more context. Consider the following coding kata which implements a shell:

let cmdProcessor state = function
    | "q" -> "Good bye!"
    | "h" -> "Help content"
    | c -> sprintf "Bad command: '%s'" c

let processUntilQuit =
    Seq.takeWhile (fun cmd -> cmd <> "q")

let processor = 
    processUntilQuit
    >> Seq.scan cmdProcessor "Welcome!"

module io =
    let consoleLines = seq { while true do yield System.Console.ReadLine () }

    let display : string seq -> unit = Seq.iter <| printfn "%s" 

io.consoleLines |> processor|> io.display

printf "Press any key to continue..."
System.Console.ReadKey ()|> ignore

This implementation has the trouble that it doesn't print "Good bye!" when command q is entered.

What I want to do is to implement the function processUntilQuit such that it processes all the commands until "q", including "q".

Answer 1

The lack of support for break in computation expressions is a bit annoying. It does not fit well with the model used by F# (which is why it is not supported), but it would be really useful in this case.

If you want to implement this using just a single iteration over the sequence, then I think the cleanest solution is to just use the underlying structure of sequences and write it as a recursive loop using IEnumerator<'T>

This is fairly short (compared to other solutions here) and it is quite clear code too:

let myFilter predicate (s:seq<_>) = 
  /// Iterates over the enumerator, yielding elements and
  /// stops after an element for which the predicate does not hold
  let rec loop (en:IEnumerator<_>) = seq {
    if en.MoveNext() then
      // Always yield the current, stop if predicate does not hold
      yield en.Current
      if predicate en.Current then
        yield! loop en }

  // Get enumerator of the sequence and yield all results
  // (making sure that the enumerator gets disposed)
  seq { use en = s.GetEnumerator()
        yield! loop en }

Answer 2

Don't really get what is the problem with your solution.

Two small corrections:

(1) Use sequence expression for readability.

(2) Use Seq.truncate instead of Seq.take in case the input sequence is empty.

let myFilter predicate s = 
    seq { yield! Seq.takeWhile predicate s
          yield! s |> Seq.skipWhile predicate |> Seq.truncate 1 }

Answer 3

let duplicateHead xs = seq { yield Seq.head xs; yield! xs }
let filter predicate xs =
    xs
    |> duplicateHead
    |> Seq.pairwise
    |> Seq.takeWhile (fst >> predicate)
    |> Seq.map snd

Alternative version of duplicateHead, in case if you don't like computation expression here:

let duplicateHead' xs =
    Seq.append 
        (Seq.head xs)
        xs

This approach is based on building tuples of current and next element. The predicate is being applied to the current element, but the following one is returned.

NOTE: It is not safe for cases when predicate fails on the very first element. In order to make it working fine, you have to re-work duplicateHead by adding an element that would certainly pass the predicate.

Answer 4

Another late answer but it is "functional", simple and does not read any elements past the last one in the result sequence.

let myFilter predicate =
    Seq.collect (fun x -> [Choice1Of2 x; Choice2Of2 (predicate x)])
    >> Seq.takeWhile (function | Choice1Of2 _ -> true | Choice2Of2 p -> p)
    >> Seq.choose (function | Choice1Of2 x -> Some x | Choice2Of2 _ -> None)

Answer 5

Ugly non-functional solution

let myfilter f s =
    let failed = ref false
    let newf = fun elem -> match !failed with 
                           |true -> 
                               failed := f elem
                               true
                           |false->false
    Seq.takeWhile newf s

Answer 6

A bit better one. :)

let padWithTrue n xs = seq { for _ in 1..n do yield true; done; yield! xs }
let filter predicate n xs =
    let ys = xs |> Seq.map predicate |> padWithTrue n
    Seq.zip xs ys
    |> Seq.takeWhile snd
    |> Seq.map fst

This one takes an additional parameter n which defines how many additional elements to add.

NOTE: careful with single-line padWithTrue (done keyword)

Answer 7

Ugly functional solution :):

let rec myFilter predicate =
        Seq.fold (fun acc s ->
            match acc with
                | (Some x, fs) -> 
                    match predicate s with
                        | true -> (Some x, fs @ [s])
                        | false -> (Some x, fs)
                | (_, fs) ->
                    match predicate s with
                        | true -> (None, fs @ [s])
                        | false -> (Some s, fs))
            (None, [])

You end up with tuple, of which first element contains option with first non-matching element from source list and second element contains filtered list.

Ugly functional lazy solution (sorry, i didn't read your post correctly for the first time):

let myFilterLazy predicate s =
        let rec inner x =
            seq {
                match x with
                    | (true, ss) when ss |> Seq.isEmpty = false ->
                        let y = ss |> Seq.head
                        if predicate y = true then yield y
                        yield! inner (true, ss |> Seq.skip 1)
                    | (_, ss) when ss |> Seq.isEmpty = false ->
                        let y = ss |> Seq.head
                        if predicate y = true then
                            yield y
                            yield! inner (false, ss |> Seq.skip 1)
                        else
                            yield y
                            yield! inner (true, ss |> Seq.skip 1)
                    | _ -> 0.0 |> ignore
            }

        inner (false, s)

I'm not fluent enough in F# to make terminating case in match look good, maybe some of the F# gurus will help.

Edit: Not-so-ugly, pure F# solution inspired by Tomas Petricek answer:

let myFilterLazy2 predicate s =
        let rec inner ss = seq {
            if Seq.isEmpty ss = false then
                yield ss |> Seq.head
                if ss |> Seq.head |> predicate then
                    yield! ss |> Seq.skip 1 |> inner
        }

        inner s

Answer 8

I guess what you want it takeUntil:

let takeUntil pred s =
  let state = ref true
  Seq.takeWhile (fun el ->
    let ret= !state
    state := not <| pred el
    ret
    ) s

Answer 9

This is very old but thought I'd contribute because the other solutions did not suggest this...

What about using Seq.scan to establish a two element stack of predicate results and simply take while the bottom of that stack, representing the previous element's predicate result, is true? (note, haven't tested this code)

Seq.scan (fun (a,b,v) e -> (pred e, a, Some e)) (true, true, None )
>> Seq.takeWhile (fun (_,b,_) -> b)
>> Seq.map (fun (_,_,c) -> c)

Answer 10

I get that this is an old question. But there is a more functional solution.

Even though, to be honest, for this question I like the more imperative solution by Tomas Petricek better.

let takeWhileAndNext predicate mySequence =
    let folder pred state element =
        match state with
            | Some (_, false) ->
                None
            | _ ->
                Some (Some element, pred element)
    let initialState = Some (None, true)
    Seq.scan (folder predicate) initialState mySequence |> Seq.takeWhile Option.isSome
                                                        |> Seq.map Option.get
                                                        |> Seq.map fst
                                                        |> Seq.filter Option.isSome
                                                        |> Seq.map Option.get

In the penultimate line, |> Seq.filter Option.isSome may be replaced by |> Seq.tail, as no states other than initialState match Some (None, _).

Answer 11

I know its ages since the question was asked, but I had to deal with the similar but more generic problem and I hope someone will find my solution useful.

The idea is to catch enumerator in closure and then return a function which iterates through the rest of original sequence. This function has one boolen parameter - whether to include current element (OP's case)

/// allows fetching elements from same sequence
type ContinueSequence<'a> (xs: 'a seq) =

    let en = xs.GetEnumerator()

    member _.Continue (includeCurrent: bool) =
        let s = seq { while en.MoveNext() do yield en.Current }
        let c = seq { en.Current }
        if includeCurrent then
            Seq.append c s
        else
            s

    interface IDisposable with 
        member _.Dispose() =
            en.Dispose()

Actual answer for the question would be:

use seq = new ContinueSequence a 
let result = Seq.append
   seq.Continue(false) |> Seq.takeWhile(predicate) 
   seq.Continue(true) |> Seq.take(1)  //include element which breaks predicate

More generic example

/// usage example:
let a = seq [1; 2; 3; 4; 5; 6; 7]

use seq = new ContinueSequence<_>(a)
let s1 = seq.Continue(false) |> Seq.takeWhile((>) 3) // take 1 and 2, 3 is current
let s2 = seq.Continue(true) |> Seq.take(2)    // take 3 and 4
let s3 = seq.Continue(false) |> Seq.skip(1)   // skip 5

let s = 
    s1 
    |> Seq.append <| s2 
    |> Seq.append <| s3 
    |> Seq.toList

// s = [1; 2; 3; 4; 6; 7]