Подтвердить что ты не робот

Как сделать Seq.takeWhile + один элемент в F #

Я хотел бы написать функцию, которая фильтрует последовательность с использованием предиката, но в результате должен также ВКЛЮЧАТЬ первый элемент, для которого предикат возвращает false.

Логика была бы такой, если бы было ключевое слово break в F #

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

Я попробовал комбинации Seq.takeWhile и Seq.skipWhile, что-то вроде этого:

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

... но проблема в том, что первый элемент, который соответствует предикату, теряется между takeWhile и skipWhile

Также обратите внимание, что входная последовательность является ленивой, поэтому любое решение, которое потребляет последовательность и принимает решения после этого, не является жизнеспособным.

Любые идеи?

Спасибо!

РЕДАКТОР: Спасибо ЛОТ за все ответы! Я не ожидал стольких ответов так быстро. Я скоро посмотрю на каждого из них. Теперь я просто хочу дать немного больше контекста. Рассмотрим следующую кодирующую ката, которая реализует оболочку:

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

У этой реализации есть проблема, что она не печатает "До свидания!" когда введена команда q.

Что я хочу сделать, это реализовать функцию processUntilQuit, чтобы она обрабатывала все команды до тех пор, пока "q", включая "q".

4b9b3361

ОТВЕТЫ

Ответ 1

Отсутствие поддержки break в выражениях вычислений немного раздражает. Это не очень хорошо подходит для модели, используемой F # (поэтому она не поддерживается), но в этом случае это было бы действительно полезно.

Если вы хотите реализовать это, используя только одну итерацию по последовательности, я думаю, что самое чистое решение состоит в том, чтобы просто использовать базовую структуру последовательностей и записать ее как рекурсивный цикл, используя IEnumerator<'T>

Это довольно короткая (по сравнению с другими решениями здесь), и это тоже довольно понятный код:

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 }

Ответ 2

Не понимаю, в чем проблема с вашим решением.

Две небольшие поправки:

(1) Используйте выражение последовательности для удобочитаемости.

(2) Используйте Seq.truncate вместо Seq.take, если входная последовательность пуста.

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

Ответ 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

Альтернативная версия duplicateHead, если вам не нравится выражение вычисления здесь:

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

Этот подход основан на построении кортежей текущего и следующего элементов. predicate применяется к текущему элементу, но возвращается следующий.

ПРИМЕЧАНИЕ. не безопасно для случаев, когда predicate не работает на самом первом элементе. Чтобы заставить его работать нормально, вам нужно повторно выполнить duplicateHead, добавив элемент, который, несомненно, пройдет predicate.

Ответ 4

Уродливое нефункциональное решение

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

Ответ 5

Уродливое функциональное решение:):

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, [])

В итоге вы получаете кортеж, из которого первый элемент содержит параметр с первым несогласованным элементом из исходного списка, а второй элемент содержит отфильтрованный список.

Уродливое функциональное ленивое решение (извините, я не читал ваше сообщение правильно в первый раз):

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)

Я недостаточно свободно в F #, чтобы сделать завершающий случай в матче хорошо выглядеть, может быть, некоторые из гуру F # помогут.

Изменить: Не очень-уродливое, чистое решение F #, вдохновленное Томасом Петричеком, отвечает:

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

Ответ 6

Немного лучше.:)

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

Этот параметр принимает дополнительный параметр n, который определяет, сколько добавляемых дополнительных элементов.

ПРИМЕЧАНИЕ: осторожно с однострочным padWithTrue (done ключевым словом)

Ответ 7

Я предполагаю, что вы хотите, чтобы он принял:

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

Ответ 8

Это очень старый, но я думал, что буду способствовать, потому что другие решения не предлагали это...

Как насчет использования Seq.scan для создания двухэлементного стека результатов предикатов и просто взять, пока нижняя часть этого стека, представляющая предыдущий результат предиката элемента, равна true? (заметьте, не протестировали этот код)

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)

Ответ 9

Я понимаю, что это старый вопрос. Но есть более функциональное решение.

Хотя, честно говоря, для этого вопроса мне больше нравится более императивное решение Томаша Петричека.

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

В предпоследней строке |> Seq.filter Option.isSome может быть заменен на |> Seq.tail, поскольку никакие состояния, отличные от initialState, не соответствуют Some (None, _).

Ответ 10

Еще один поздний ответ, но он "функциональный", простой и не читает никаких элементов после последнего в последовательности результатов.

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)