标准 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

Here's my solution where I cheated around the requirements a bit by having two functions.

这不是问题。在编写标准 ml 时使用 helper 函数很好。特别地，这里的辅助函数是尾递归，它将优化堆栈框架。有时（不是这里）模式的嵌套案例是一种替代方法，但由于没有尾递归，因此需要更多的内存。

How do I go about removing the need for s?

我不知道你为什么不喜欢额外的 s。但是我有一个解决方案：使用闭包来隐式保存它。

紧凑型：

fun expand [] n =  []
    | expand (node::list) n =
      let   fun n_times f n x = if n = 0 then x else f (n_times f (n-1) x) 
      in    n_times (fn list => case list of node::list => node::[node]) n [node] @ expand list n end

更具可读性的风格：

fun expand [] n =  []
  | expand (node::list) n =
    let
        fun n_times f n x =
            if n = 0
            then x
            else f (n_times f (n-1) x)
    in
        n_times (fn list => case list of node::list => node::[node]) n [node]
        @
        expand list n
    end

这个闭包(fn list => case list of node::list => node::[node])不包含额外的s，但它的作用是帮助n_times完成n次cons。我想这就是你想要的

顺便说一句，要求 expand [1,2,3] 3 和 ‘a list→int→‘a list 要求您使用 curry 函数而不是 tuple/non-curry 函数（标准 ml 中的所有参数只是一个元组）。因此，我上面给出的解决方案使用 curry function(expand [] n and n_times f n x) 。您还可以使用一个帮助函数将非 curry 函数转换为 curry 函数：

fun curry_helper f x y z = f (x, y, z)

有不明白的地方欢迎留言。

Answer 2

定义辅助函数不是"cheating"，很好。
这是一个更大的问题，你用错误的类型定义了一个函数 - expand 的类型对练习来说比你最终得到的函数数量更重要（请注意，描述说明了 "must be"，但并不是说你不能定义辅助函数）。

您遇到问题是因为您试图一次 "attack" 整个输入列表。
当你遇到"do X with each element of a list"问题时，首先要做的是思考"write a function that does X with one thing and then List.map it".

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

我们可以写 repeat: int * 'a -> 'a list，但那需要一个数字和一个东西，而且在任何地方 map 都不方便。
如果我们可以动态 "fix" 数字并得到一个函数 'a -> 'a list.
就好了如果您以方便的顺序提供参数，柯里化就可以做到这一点。

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 并得到一个接受 "something" 并重复四次的函数。

让我们使用它：

- 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

几乎正确 - 列表应该是 "flat"。

幸运的是，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

Answer 3

这是一个使用标准库函数的解决方案：

fun expand (xs, n) =
    List.concat (List.map (fn x => List.tabulate (n, fn _ => x)) xs)

还有一个：

fun expand (xs, n) =
    List.foldr (fn (x, acc) => List.tabulate (n, fn _ => x) @ acc) [] xs

标准 ML 扩展列表

Standard ML Expand List

sml