Что эквивалентно Seq.Span Scala в F #?

Question

Цитировать Документация Scala :

def span(p: (A) => Boolean): (Seq[A], Seq[A])

Разбивает эту итеративную коллекцию на пару префикс / суффикс в соответствии с предикатом.

Примечание: c span p эквивалентен (но, возможно, более эффективен, чем) (c takeWhile p, c dropWhile p), при условии, что оценка предиката p не вызывает никаких побочных эффектов.

Примечание: может возвращать разные результаты для разных прогонов, если только не упорядочен базовый тип коллекции.

• p - тестовый предикат
• return - пара, состоящая из самого длинного префикса этой итерируемой коллекции, все элементы которой удовлетворяют p, и остальная часть этой итерируемой коллекции.
• Определение классов - IterableOps → IterableOnceOps
• Примечание. Повторное использование: после вызова этого метода следует отказаться от итератора, для которого он был вызван, и использовать только те итераторы, которые были возвращены. Использование старого итератора не определено, может изменяться и может также привести к изменениям в новых итераторах.

---

При просмотре F # документации для Seq, я не вижу эквивалента.

groupBy, partition, splitAt, ни один из них не соответствует тому, что я пытаюсь сделать. Это похоже на одновременное выполнение takeWhile и skipWhile, но вместо двух итераций вам нужна только одна, где функция будет возвращать кортеж (takeWhile, skipWhile).

Выход должен соответствовать следующей функции

module List
let span (predicate: 'a -> bool) (list: 'a list): ('a list * 'a list) =
    (list |> List.takeWhile predicate, list |> List.skipWhile predicate)

Но нужна только одна итерация, поскольку моя последовательность может быть бесконечной.

[1;2;3;4] |> List.span (fun i -> i % 2 = 1) => ([1], [2;3;4])

Answer 1

Ваше объяснение не то, что Seq.span делает в Scala: он разбивает одну последовательность на две, помещая все входные элементы в первое значение кортежа, пока функция предиката возвращает true. Как только функция вернет false, все оставшиеся элементы будут помещены во второе значение кортежа.

Пример в F # будет выглядеть так:

[1;2;3;4] |> Seq.span (fun i -> i % 2 = 1) => ([1], [2;3;4])

Этого можно достичь довольно легко, используя взаимно рекурсивные функции:

module Seq

open System.Collections.Generic

let span (predicate: 'a -> bool) (seq: 'a seq): ('a seq * 'a seq) =
    let rec insertLeft predicate (e: IEnumerator<'a>) (left: ResizeArray<'a>) (right: ResizeArray<'a>) =
        if e.MoveNext() then
            if predicate e.Current then
                left.Add e.Current
                insertLeft predicate e left right
            else
                // once predicate returned false, all consecutive elements land in right list
                right.Add e.Current 
                insertRight e right
    and insertRight (e: IEnumerator<'a>) (right: ResizeArray<'a>) =
        if e.MoveNext() then 
            right.Add e.Current
            insertRight e right
    let left = ResizeArray<_>()
    let right = ResizeArray<_>()
    use enumerator = seq.GetEnumerator()
    insertLeft predicate enumerator left right
    (upcast left, upcast right)

Answer 2

У меня есть вспомогательная функция, которую я нахожу весьма полезной для такого рода вещей:

module Seq =
    let groupAdjacentBy f xs =
        let mutable prevKey, i = None, 0
        xs
        |> Seq.groupBy (fun x ->
            let key = f x
            if prevKey <> Some key then
                i <- i + 1
                prevKey <- Some key
            (i, key))
        |> Seq.map (fun ((_, k), v) -> (k, v))

Обратите внимание, что в реализации он использует локальную мутацию, поскольку это самый простой способ повторно использовать существующую Seq.groupBy.

Это на самом деле функция группировки, но она помещает элементы в одну группу, только если они находятся рядом друг с другом. На мой взгляд, это очень общий способ решения проблем, который требует нескольких вариантов использования takeWhile и skipWhile, но проще, потому что все это делается за один проход. Функция группировки возвращает групповой ключ любого типа, а не просто логический, что добавляет больше гибкости.

Вот пример использования с функцией группировки, которая возвращает логическое значение:

[ 1; 2; -1; -2; 3; 4; -5 ]
|> Seq.groupAdjacentBy (fun x -> x > 0) // positive?
|> Seq.map snd
// seq [seq [1; 2]; seq [-1; -2]; seq [3; 4]; seq [-5]]

В этом примере первые две строки возвращают группы с их ключами (true, false, true, false соответственно). Затем вы можете использовать эти ключи в своей логике, но если вас это не волнует, Seq.map snd откажется от них. И у вас остается seq<seq<int>>, как показано выше.

Answer 3

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

module Seq

let span (predicate: 'a -> bool) (sequence: 'a seq): ('a seq * 'a seq) =
    let enumerator = sequence.GetEnumerator()
    let isNotDone = ref (enumerator.MoveNext())
    let first = seq {
        let e = enumerator
        if !isNotDone then
            while (!isNotDone && predicate e.Current) do
                yield enumerator.Current
                isNotDone := e.MoveNext() }
    let second = seq {
        use e = enumerator
        if !isNotDone then
            yield e.Current
            while e.MoveNext() do
                yield e.Current }
    let eagerFirst = List.toSeq (Seq.toList first)
    (eagerFirst, second)

Answer 4

Похоже, что вы хотите что-то вроде следующего, вы просто передаете одно и то же Seq (или List или что-то еще) на filter дважды следующим образом:

//Returns a tuple of seq<'a> * seq<'a> (which looks like what you want).
let scalaSpanTuple test sq = (Seq.filter test sq, Seq.filter (test>>not) sq)

или

//Returns a list of 2 lists of 'a
let scalaSpanList test ls = [List.filter test ls; List.filter (test>>not) ls]

и т.д.