F # Разделить список на подсписки на основе сравнения соседних элементов

Question

Я нашел этот вопрос на hubFS, но он обрабатывает критерии разделения, основанные на отдельных элементах. Я хотел бы разделить на основе сравнения смежных элементов, поэтому тип будет выглядеть так:

val split = ('T -> 'T -> bool) -> 'T list -> 'T list list

В настоящее время я пытаюсь начать с императивного решения Дона, но не могу понять, как инициализировать и использовать значение «prev» для сравнения. Является ли сложить лучший способ пойти?

//Don's solution for single criteria, copied from hubFS
let SequencesStartingWith n (s:seq<_>) =
    seq { use ie = s.GetEnumerator()
          let acc = new ResizeArray<_>()
          while ie.MoveNext() do
             let x = ie.Current
             if x = n && acc.Count > 0 then
                 yield ResizeArray.to_list acc
                 acc.Clear()
             acc.Add x
          if acc.Count > 0 then
              yield  ResizeArray.to_list acc }

Answer 1

Это интересная проблема!Мне нужно было реализовать именно это в C # совсем недавно для моей статьи о группировке (поскольку сигнатура функции очень похожа на groupBy, поэтому ее можно использовать в запросе LINQ как group byпункт).Реализация C # была довольно уродливой.

В любом случае, должен быть способом выражения этой функции с помощью некоторых простых примитивов.Просто кажется, что библиотека F # не предоставляет никаких функций, которые подходят для этой цели.Мне удалось придумать две функции, которые кажутся в целом полезными и могут быть объединены вместе для решения этой проблемы, поэтому вот они:

// Splits a list into two lists using the specified function
// The list is split between two elements for which 'f' returns 'true'
let splitAt f list =
  let rec splitAtAux acc list = 
    match list with
    | x::y::ys when f x y -> List.rev (x::acc), y::ys
    | x::xs -> splitAtAux (x::acc) xs
    | [] -> (List.rev acc), []
  splitAtAux [] list

val splitAt : ('a -> 'a -> bool) -> 'a list -> 'a list * 'a list

Это похоже на то, что мы хотим достичь, ноон разбивает список только на две части (что проще, чем разбивать список несколько раз).Затем нам нужно будет повторить эту операцию, что можно сделать с помощью этой функции:

// Repeatedly uses 'f' to take several elements of the input list and
// aggregate them into value of type 'b until the remaining list 
// (second value returned by 'f') is empty
let foldUntilEmpty f list = 
  let rec foldUntilEmptyAux acc list =
    match f list with
    | l, [] -> l::acc |> List.rev
    | l, rest -> foldUntilEmptyAux (l::acc) rest
  foldUntilEmptyAux [] list

val foldUntilEmpty : ('a list -> 'b * 'a list) -> 'a list -> 'b list

Теперь мы можем повторно применять splitAt (с некоторым предикатом, указанным в качестве первого аргумента) к списку ввода, используяfoldUntilEmpty, которая дает нам функцию, которую мы хотели:

let splitAtEvery f list = foldUntilEmpty (splitAt f) list

splitAtEvery (<>) [ 1; 1; 1; 2; 2; 3; 3; 3; 3 ];;
val it : int list list = [[1; 1; 1]; [2; 2]; [3; 3; 3; 3]]

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

Answer 2

Как насчет:

let splitOn test lst =
    List.foldBack (fun el lst ->
            match lst with
            | [] -> [[el]]
            | (x::xs)::ys when not (test el x) -> (el::(x::xs))::ys
            | _ -> [el]::lst
         )  lst [] 

метод foldBack устраняет необходимость переворачивать список.

Answer 3

Подумав об этом немного дальше, я придумала это решение. Я не уверен, что это очень читабельно (за исключением меня, кто это написал).

ОБНОВЛЕНИЕ Опираясь на пример лучшего соответствия в ответе Томаса, вот улучшенная версия, которая устраняет «запах кода» (см. Правку предыдущей версии) и немного более читабельна (говорит мне).

Это все еще ломается (splitOn (<>) []) из-за страшной ошибки ограничения значения , но я думаю, что это может быть неизбежно.

(РЕДАКТИРОВАТЬ: Исправленная ошибка, обнаруженная Йоханом Куллбомом, теперь корректно работает для [1; 1; 2; 3]. Проблема заключалась в том, что в первом совпадении использовались два элемента, это означало, что я пропустил сравнение / проверку .)

//Function for splitting list into list of lists based on comparison of adjacent elements
let splitOn test lst = 
    let rec loop lst inner outer = //inner=current sublist, outer=list of sublists
        match lst with 
        | x::y::ys when test x y -> loop (y::ys) [] (List.rev (x::inner) :: outer)
        | x::xs ->                  loop xs (x::inner) outer
        | _ ->                      List.rev ((List.rev inner) :: outer)
    loop lst [] []

splitOn (fun a b -> b - a > 1) [1]
> val it : [[1]]

splitOn (fun a b -> b - a > 1) [1;3]
> val it : [[1]; [3]]

splitOn (fun a b -> b - a > 1) [1;2;3;4;6;7;8;9;11;12;13;14;15;16;18;19;21]
> val it : [[1; 2; 3; 4]; [6; 7; 8; 9]; [11; 12; 13; 14; 15; 16]; [18; 19]; [21]]

Есть мысли по этому поводу или частичное решение в моем вопросе?

Answer 4

"смежный" немедленно заставляет меня думать о Seq.pairwise.

let splitAt pred xs =
    if Seq.isEmpty xs then
        []
    else
        xs
        |> Seq.pairwise
        |> Seq.fold (fun (curr :: rest as lists) (i, j) -> if pred i j then [j] :: lists else (j :: curr) :: rest) [[Seq.head xs]]
        |> List.rev
        |> List.map List.rev

Пример:

[1;1;2;3;3;3;2;1;2;2]
|> splitAt (>)

Дает:

[[1; 1; 2; 3; 3; 3]; [2]; [1; 2; 2]]

Answer 5

Я бы предпочел использовать List.fold вместо явной рекурсии.

let splitOn pred = function
    | []       -> []
    | hd :: tl -> 
        let (outer, inner, _) =
            List.fold (fun (outer, inner, prev) curr ->
                            if pred prev curr 
                            then (List.rev inner) :: outer, [curr], curr
                            else outer, curr :: inner, curr)
                      ([], [hd], hd)
                      tl
        List.rev ((List.rev inner) :: outer)

Answer 6

Мне нравятся ответы, предоставленные @Joh и @Johan, поскольку эти решения кажутся наиболее идиоматичными и простыми. Мне также нравится идея, предложенная @Shooton. Однако у каждого решения были свои недостатки.
Я пытался избежать:

• Реверсивные списки
• Отключение и объединение временных результатов
• Комплекс match Инструкции
• Даже Seq.pairwise оказался излишним
• Контрольный список на пустоту можно удалить по стоимости использования Unchecked.defaultof<_> ниже

Вот моя версия:

let splitWhen f src =
    if List.isEmpty src then [] else
    src
    |> List.foldBack
        (fun el (prev, current, rest) ->
            if f el prev
            then el , [el]          , current :: rest
            else el , el :: current , rest
        )
        <| (List.head src, [], [])               // Initial value does not matter, dislike using Unchecked.defaultof<_>
    |> fun (_, current, rest) -> current :: rest // Merge temporary lists
    |> List.filter (not << List.isEmpty)         // Drop tail element