sml - 标准 ML 展开列表

Question

方向

expand接收任何类型的列表和整数的函数n，并返回一个列表，其中输入列表的每个项目都被复制n次数。例如，expand [1,2,3] 3 必须计算为 [1,1,1,2,2,2,3,3,3]。函数的类型必须是'a list→int→'一个列表。

这是我的解决方案，我通过具有两个功能来绕过要求。n当我转到列表中的下一个项目时，我正在努力解决的问题是重置为原始值。我在我的实现中通过保存从未更改的原始n值来做到这一点。s我该如何消除对 的需求s？

fun duplicate([], n, s) = [] |
    duplicate(l, n, s) = 
    if n > 1 then hd l::duplicate(l, (n-1), s)
    else hd l::duplicate(tl l, s, s);

fun expand([], n) = [] |
    expand(l, n) = duplicate(l, n, n);

标签： sml

Answer 1

定义辅助函数不是“作弊”，这很好。
这是一个更大的问题，你定义了一个错误类型的函数——类型expand对于练习来说比你最终得到的函数的数量更重要（请注意，描述说明了类型“必须是”，但不是你'不允许定义辅助函数）。

您遇到问题是因为您试图一次“攻击”整个输入列表。
当您遇到“对列表的每个元素执行 X”问题时，要做的第一件事就是考虑“编写一个函数，先对一个事物执行 X，然后再执行List.map它”。

如果我们有一个可以重复某件事的函数k，我们可以将它应用于每个列表元素。

我们可以写repeat: int * 'a -> 'a list，但这需要一个数字和一个东西，而且在map任何地方都不方便。
如果我们可以动态地“修复”数字并获得一个函数，那就太好了'a -> 'a list。
如果您以方便的顺序给出参数，Currying 可以让您完全做到这一点。

fun repeat 0 i = []
  | repeat n i = i :: repeat (n - 1) i;

加载和测试：

val repeat = fn : int -> 'a -> 'a list
val it = () : unit
- repeat 3 4;
val it = [4,4,4] : int list

到目前为止看起来不错。
我们现在可以编写repeat 4并获得一个接受“某物”并重复四次的函数。

让我们使用它：

- fun expand xs n = List.map (repeat n) xs;
val expand = fn : 'a list -> int -> 'a list list

类型看起来不太好。让我们看看我们刚刚创建了什么。

- expand [1,2,3] 3;
val it = [[1,1,1],[2,2,2],[3,3,3]] : int list list

几乎正确 - 列表应该是“扁平的”。

幸运的是，List 结构有一个函数可以帮助：concat: 'a list list -> 'a list，它接受一个列表并将它们附加在一起，所以我们可以将结果传递给它：

- fun expand xs n = List.concat (List.map (repeat n) xs);
val expand = fn : 'a list -> int -> 'a list

这样看起来更好。

- expand [1,2,3] 3;
val it = [1,1,1,2,2,2,3,3,3] : int list