SML：如何将列表列表到子列表

Question

我从 CS 217 中找到了这个问题。

将一个列表分成一个或多个子列表，使每个子列表包含非递减（排序）顺序的整数。

[3,5,1,8,9,2,1,0] returns [[3,5],[1,8,9],[2],[1],[0]]

[1,2,3,4,5,6] returns [[1,2,3,4,5,6]]

[5,4,3,2,1] returns [[5],[4],[3],[2],[1]]

以下代码有效：

val Q1 = [ 3, 5, 1, 8, 9, 2, 1, 0 ]

val A1 = foldl (
    fn (x, a) => 
        if x > hd (hd a) then (x::hd a)::tl a
        else [x]::a 
    ) [ [ hd Q1 ] ] (tl Q1)

val A1 = map rev (rev A1)

或者像这样：使用2个临时列表来收集。

fun split l = let
    fun split' tmp subset =
        fn [] => []
        |  [x] => (x::tmp)::subset
        |  (a::(c as b::_)) =>
                if a < b then split' (a::tmp) subset c
                else split' [] ((a::tmp)::subset) c
    in (rev o map rev) (split' [] [] l) end

这个问题有这么多解法，但我仍然想知道如何将其编码为 模式匹配函数 ？可能如下所示：

（不确定是否可行？）

fun split [] = [[]]
|   split [x] = [[x]]
|   split [a, b] = if a < b then (* here *) else (* here *)
|   split (a::b) = if a < hd b then (* here *) else (* here *)

这个问题真的让我很困惑。

Answer 1

假设这是作业，我犹豫是否给出完整的答案，但这里有一些提示：

1) 在空基的情况下，我认为你想要 return [[]] 而不是 []。您的规范没有解决这个问题，但是由于空列表是最长的非递减整数列表，可以从空列表的前面拉出，因此 return 值应该是由空列表组成的列表。这有点类似于空集的幂集（所有子集的集合）是包含空集的集合而不是空集本身。你如何定义这个特殊情况并不重要，因为真正的基础情况是......

2) 在 [x] 的情况下，您确实需要 return [[x]] 而不是 [x]，因为您尝试编写的函数类型是 int list -> int list list

3) 在其余情况下，您可以将模式写成

|    split (x::y::zs) = (* fill this in *)

然后测试是否 x <= y 来决定要做什么。由于 x <= y 和 x > y 都将涉及 split (y::zs) 你可以计算一次，在 let 绑定中给它一个名字并在范围内有 if绑定，虽然这主要是品味问题。

请注意模式在最后一种情况下的工作原理。 hd 的显式使用在使用模式匹配的函数定义中应该很少见（尽管如果你在不使用模式匹配 let 绑定的情况下充实最后一个案例，你将被迫在 at if).

的至少一个分支

关于编辑：由于这不是家庭作业，这里是一个完整的实现：

fun split [] = [[]]
|   split [x] = [[x]]
|   split (x::y::zs) =
    let val first::rest = split (y::zs) in
        if x <= y then
            (x::first) :: rest
        else
            [x]::first::rest
    end;

SML：如何将列表列表到子列表

SML: how to listify list to sublist

sml