即使在附加标准 ML 后列表也是空的

Question

我有一个函数，它接受一个列表，然后根据条件将元素放入两个不同的列表中。但是，当我检查返回的列表时，它们总是空的。为什么会这样？

fun divide_list(l1: type list): (type list, type list) = 
  let
    val count = ref 0 
    and list1 = nil 
    and list2 = nil
  in
    while !count <> 8 do (
      if !count % 2 = 0 then 
        list1 @ [List.nth(l1, !count)]
      else 
        list2 @ [List.nth(l1, !count)];
      count := !count + 1
    );
    (list1, list2)
  end

我在运行之后得到的输出如下：

val it = ([],[]) : type list * type list

Answer 1

您不是在修改列表，而是在创建被丢弃的新列表。为了实现您想要的效果，您还需要将列表包装在引用中：and list1 = ref [] and list2 = ref []。然后，在您打算修改它们的每个实例中，您使用 :=（就像您修改 count 一样）。请注意，您将重写要返回的元组以获取每个引用所持有的值：(!list1, !list2).

作为旁注，很遗憾 Standard ML 没有告知您这一点。例如，在 OCaml 中，排序表达式 e ; e' 的输入规则确保 e 的计算结果为 () : unit 由于它的脱糖方式 (let () = e in e')。因此，与您的代码类似的 OCaml 甚至不会进行类型检查。

我会完全放弃基于 ref 的解决方案，并使用带有索引的折叠来做一些事情：

fun divide xs =
  let
    fun choose (x, ((l, r), i)) =
      (if i mod 2 = 0 then (x :: l, r) else (l, x :: r), i + 1)
    
    val (l, r) =
      #1 (List.foldl choose (([], []), 0) xs)
  in
    (List.rev l, List.rev r)
  end

我向后构建列表分区，然后在末尾反转以避免为每个元素追加到末尾的二次爆炸。如果你希望有 8 约束的长度，那么你可以将上述函数的用法与基础库中的 List.take 结合使用。

Answer 2

@contificate 给出了很好的解释。

如果您要实现列表分区功能。

没有理由不考虑将决定如何对列表进行分区的函数。这个函数只需要接受一个值和return一个布尔值。

这很容易通过折叠实现。据我所知，没有必要跟踪索引。

fun partition f lst =
  let
    val (a, b) = List.foldl (fn (x, (a, b)) => if f x then (x::a, b) else (a, x::b)) ([], []) lst
  in
    (List.rev a, List.rev b)
  end;

partition (fn x => x mod 2 = 0) [1, 2, 3, 4, 5];

产量：

([2, 4], [1, 3, 5])

如果您只想根据 index

进行拆分

如果我们的目标是根据索引将一个列表分成两个列表：

[4, 7, 1, 9, 8]

变为：

([4, 1, 8], [7, 9])

这完全可以通过简单的模式匹配和递归在功能上完成。

let rec split lst (acc1, acc2) =
  match lst with
  | [] -> (acc1, acc2)
  ...

这里我们传入要拆分的列表，以及一个包含两个列表的累加器。显然，如果列表为空，则结果只是累加器。如果列表中只有一个元素怎么办？

let rec split lst (acc1, acc2) =
  match lst with
  | []  -> (acc1, acc2)
  | [x] -> (x::acc1, acc2)
  ...

好吧，它在第一个列表中。如果元素多于一个怎么办？

let rec split lst (acc1, acc2) =
  match lst with
  | []  -> (acc1, acc2)
  | [x] -> (x::acc1, acc2)
  | x::y::tail -> split tail (x::acc1, y::acc2)

嗯，那我们匹配前两个元素和尾部。我们更新累加器以将前两个元素放入各自的列表中，并使用尾部和更新后的累加器再次调用 split。

utop # split [4; 7; 1; 9; 8] ([], []);;
- : int list * int list = ([8; 1; 4], [9; 7])

糟糕。由于我们构建累加器的方式，它们是倒退的。我们可以使用 List.rev 来解决这个问题，但是因为我们不想做两次，所以当有一个元素时，我们将在一个空列表上调用 split。

let rec split lst (acc1, acc2) =
  match lst with
  | []  -> (List.rev acc1, List.rev acc2)
  | [x] -> split [] (x::acc1, acc2)
  | x::y::tail -> split tail (x::acc1, y::acc2)

utop # split [4; 7; 1; 9; 8] ([], []);;
- : int list * int list = ([4; 1; 8], [7; 9])

最后，您可以隐藏 split 以消除显式传递空列表元组的需要。

let rec split lst (acc1, acc2) =
  match lst with
  | []  -> (List.rev acc1, List.rev acc2)
  | [x] -> split [] (x::acc1, acc2)
  | x::y::tail -> split tail (x::acc1, y::acc2)

let split lst = split lst ([], [])

即使在附加标准 ML 后列表也是空的

Empty list even after appending Standard ML

functional-programming

list

append

sml

如果您要实现列表分区功能。

如果您只想根据 index