Разделение F# перечисляет в подсписки на основе сравнения смежных элементов
Я нашел этот вопрос на hubFS, но это обрабатывает разделение критерии на основе отдельных элементов. Я хотел бы разделить на основе сравнения смежных элементов, таким образом, тип будет похож на это:
val split = ('T -> 'T -> bool) -> 'T list -> 'T list list
В настоящее время я пытаюсь начать с обязательного решения Дона, но я не могу разработать, как инициализировать и использовать 'предыдущее' значение для сравнения. Действительно ли сгиб является лучшим способом пойти?
//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 }
3 ответа
Это интересная проблема! Совсем недавно мне нужно было реализовать именно это на 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#.
Я бы предпочел использовать 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)
Поразмыслив немного над этим, я пришел к следующему решению. Не уверен, что он очень читабельный (кроме меня, написавшего).
ОБНОВЛЕНИЕ Основываясь на примере лучшего соответствия в ответе Томаса, вот улучшенная версия, которая устраняет «запах кода» (см. Правки для предыдущей версии) и немного более читабельна (говорит мне).
Он все еще ломается на этом ( 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]]
Есть какие-нибудь мысли по этому поводу или частичное решение моего вопроса?