子列表上的操作 [英] Operations on sublists

问题描述

我目前正在考虑一种根据给定条件在子列表中拆分列表的方法.由于这项工作的<教学目的>，我不使用内置函数. 在IE中，以下程序应给定一个列表，然后返回一个列表列表，其中每个子列表没有重复项，并且按升序排列:

I am currently wondering on an approach to split a list in sub-lists according to a given criteria. Because of the didactic purpose of this work, I do not use built-in functions. IE, the following program should, given a list, return a list of lists, where each sub-list does not have duplicates and is in ascending order:

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]]

到目前为止，我最好的尝试是基于我生成的这段代码:

My best attempt so far is based on this chunk of code I produced:

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]

不幸的是，我无法创建列表列表.该原则是正确的.它基于我构建的功能，可以正确隔离升序列表(如果存在):

Unfortunately, I fail in creating the list of lists. The principle is correct. It is based on the function I built, that correctly isolates an ascending list if present:

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 [])

任何建议将不胜感激！

推荐答案

如果您不想在List模块上使用内置函数(纯粹是学习练习)来执行此操作，那么您只需要了解map和fold，因此您可以自己实现它们.我将从此Wikipedia文章开始.方便地，您可以根据fold轻松实现rev，所以这不成问题.一旦了解了每个函数的功能，就可以自己实现它们，如下所示:

If you want to do this without using the built-in functions on the List module (purely as a learning exercise), then you just need to understand map and fold so you can implement them yourself. I would start with this wikipedia article. Conveniently, you can easily implement rev in terms of fold, so that shouldn't be a problem. Once you understand what each function does, you can implement them yourself like so:

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解决方案中的内置功能:

Then, you can just substitute your own functions for the built-in functions in Szer's solution:

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循环.

Note, this implementation of fold is different from how F# List does it. This is based on the simple Haskell example in the wikipedia article. The functionality is the same, but the implementation is quite different, as F# actually uses a mutable accumulator and a for-loop.

这篇关于子列表上的操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！