sml - 标准 ML 扩展列表

Question

Directions

Function expand that receives a list of any type and an integer number n, and returns a list in which each item of input list is replicated n times. For example, expand [1,2,3] 3 must be evaluated to [1,1,1,2,2,2,3,3,3].The type of the function must be ‘a list→int→‘a list.

这是我的解决方案，我通过使用两个函数来绕过需求。当我移动到列表中的下一项时，我正在努力将 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);

Answer 1

定义辅助函数不是“作弊”，而是好的。
你用错误的类型定义了一个函数是一个更大的问题 - expand 的类型对练习来说比你最终得到的函数的数量更重要(注意描述说明了类型“必须是”，但并不是说您不能定义辅助函数)。

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

如果我们有一个函数可以将某些内容重复 k 次，我们就可以将它应用于每个列表元素。

我们可以写repeat: int * 'a -> 'a list，但这需要一个数字和一个东西，而且不方便映射到任何地方。
如果我们可以动态“修复”数字并获得一个函数 '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 structure有一个函数可以帮助: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