Операции над списками

Question

В настоящее время я задаюсь вопросом о подходе к разделению списка в подсписках в соответствии с заданными критериями.Из-за дидактической цели этой работы я не использую встроенные функции.IE, следующая программа должна, при наличии списка, вернуть список списков, где каждый подсписок не имеет дубликатов и находится в порядке возрастания:

increment [4;4;10;20;5;30;6;10] = [[4;10;20];[5;30];[6;10]]
increment [5;6;4;3;2;1] = [[5;6];[4];[3];[2];[1]]

Моя лучшая попытка на данный момент основана на этомкусок кода, который я произвел:

let rec increment li [lo] = 
    match li with
        |[]         ->  [lo]
        |[x]        ->  [x]::[lo]
        |x::y::xs   ->  if x = y then
                            increment (y::xs) [lo]
                        elif x < y then
                            x::(increment (y::xs) [lo])
                        else
                            (x::(increment xs [lo]))::[lo]

К сожалению, мне не удается создать список списков.Принцип верен.Он основан на функции, которую я построил, которая правильно изолирует возрастающий список, если он присутствует:

let rec incrementAux li = 
    match li with
        |[]         ->  []
        |[x]        ->  [x]
        |x::y::xs   ->  if x = y then
                            incrementAux (y::xs)
                        elif x < y then
                            x::(incrementAux (y::xs))
                        else
                            x::(incrementAux [])

Любое предложение будет высоко оценено!

Answer 1

Если вы хотите сделать это без использования встроенных функций в модуле List (чисто как учебное упражнение), вам просто нужно понять map и fold, чтобы вы могли реализовать их самостоятельно.Я бы начал с этой статьи в Википедии .Удобно, вы можете легко реализовать rev в терминах fold, так что это не должно быть проблемой.Как только вы поймете, что делает каждая функция, вы можете сами реализовать их следующим образом:

let rec fold f state = function
| [] -> state
| head::tail -> fold f (f state head) tail

let map f list =
    [for item in list -> f item]

let rev list = 
    fold (fun acc cur -> cur::acc) [] list

Затем вы можете просто заменить свои собственные функции на встроенные функции в решении Szer:

let input = [4;4;10;20;5;30;6;10]
let output = [[4;10;20];[5;30];[6;10]]

let increment = 
    fold (fun (last::rest as total) x ->
        match last with
        | [] -> [x] :: rest
        | h::_ as last ->
        if x > h then (x::last)::rest
        else if x = h then total
        else [x]::total) [[]]
    >> map rev
    >> rev

let testOutput = increment input
testOutput = output

Обратите внимание, что эта реализация fold отличается от того, как это делает F # List.Это основано на простом примере на Haskell в статье в Википедии.Функциональность та же, но реализация совершенно иная, поскольку F # на самом деле использует изменяемый аккумулятор и цикл for.

Answer 2

Вы можете сделать это без рекурсии.List.fold с небольшим объемом памяти может помочь:

let input = [4;4;10;20;5;30;6;10]
let output = [[4;10;20];[5;30];[6;10]]

let increment = 
    List.fold (fun (last::rest as total) x ->
        match last with
        | [] -> [x] :: rest
        | h::_ as last ->
        if x > h then (x::last)::rest
        else if x = h then total
        else [x]::total) [[]]
    >> List.map List.rev
    >> List.rev

let testOutput = increment input
testOutput = output // true