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

Ответ 1

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

Во всяком случае, должен быть способ выразить эту функцию, используя некоторые простые примитивы. Просто кажется, что библиотека 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 #.

Ответ 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 устраняет необходимость в изменении списка.

Ответ 3

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

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

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

(EDIT: исправленная ошибка, отмеченная Johan Kullbom, теперь корректно работает для [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]]

Любые мысли об этом или частичное решение в моем вопросе?

Ответ 4

Я бы предпочел использовать 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)

Ответ 5

"смежный" сразу заставляет меня думать о 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]]

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