一些 sml 代码，但我不知道它是如何工作的

Question

fun map f nil = nil
 | map f (hd::tl) = f(hd) :: map f tl;


fun everywhere e nil = [[e]]
  | everywhere e (y::ys) =
    (e::y::ys) :: (map (fn u => y::ys) (everywhere e ys));

我不知道那些 sml 代码是如何工作的。

我知道地图函数。

但是关于无处不在的代码，我不知道我是怎么想的。

请告诉我

谢谢

Answer 1

首先，我想应该修复“everywhere”以获得其名称所期望的行为：

fun everywhere e nil = [[e]]
  | everywhere e (y::ys) =
    (e::y::ys) :: (map (fn u => y::u) (everywhere e ys));

本修改版提供列表列表。例如，

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

因此，您可能知道“everywhere e xs”列举了所有可能的列表，这些列表是通过将项目“e”插入原始列表 xs 的某处而形成的。

那么，如何枚举插入呢？分为两种情况：

在顶部插入：[1,2,3] -> [4, 1,2,3]
在第一个和第二个或后面插入：[1, 4 ,2,3], [1,2, 4 ,3],...

情况 1 仅由 (e::y::ys) 实现。

案例2进一步分为两步：

A) 获取将“e”插入到第二个和以下项目的子列表“ys”中的所有可能性：[4, 2, 3], [2, 4, 3], ...
B) 将原始列表的第一项“y”添加到步骤 A 的结果的每个中： 1::[4,2,3], 1::[2,4,3], ...

步骤 2A 可以通过将子列表作为参数调用“everywhere”本身来完成。然后，将项目“y”附加到每个（到处都是 e ys），您就完成了步骤 2B。为此（对物品做同样的事情），你可以使用“地图”。

一些 sml 代码，但我不知道它是如何工作的

Some sml codes but i don't know how that work

analysis

sml