SMLNJ 电源设置功能

Question

>我正在尝试打印从下面的功率设置函数创建的列表的大小

fun add x ys = x :: ys;
fun powerset ([])  = [[]]
| powerset (x::xr) = powerset xr @ map (add x) (powerset xr) ;
val it = [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]] : int list list;

我有列表大小功能

fun size xs = (foldr op+ 0 o map (fn x => 1)) xs;

我无法合并这两个函数并获得这样的结果

我需要这样的东西：

[(0,[]),(1,[3]),(1,[2]),(2,[2,3]),(1,[1]),(2,[1,3]),(2,[1,2]),(3,[1,2,3])]

谁能帮我解决这个问题？

Answer 1

您可以使用内置List.length获取列表的长度。

你似乎忘了提到你有一个约束，即你只能使用高阶函数。(我猜你有这个约束，因为现在其他人都在问如何使用这个约束编写 powerset 函数，并且像你一样使用foldr来计数似乎有点结构化。

您的示例表明您正在尝试计算列表列表中的每个列表，而不仅仅是一个列表的长度。为此，您需要将计数功能映射到列表列表中。但这只会给你一个长度列表，你想要的输出似乎是一个包含长度和实际列表的元组列表。

以下是一些提示：

1. 您不妨使用foldl而不是foldr因为加法是关联的。

2. 您不需要先map (fn x => 1)- 这会添加不必要的列表迭代。您可能正在这样做，因为折叠看起来很复杂，而且您刚刚设法编写foldr op+ 0.这是不理解折叠的第一个论点的症状。

   尝试使用匿名函数编写折叠表达式，而不是op+：

   fun size L = foldl (fn (x, acc) => ...) 0 L
   

   将其与op+进行比较，如果像匿名函数一样编写，则如下所示：

   fn (x, y) => x + y
   

   使用op+折叠带有 + 运算符的一些非常隐含的用法：您希望丢弃一个操作数(因为不是它的值，而是它的存在计数)并将另一个操作数用作累加变量(通过调用它来更好地理解它acc而不是y)。

   如果您不确定我所说的累积变量是什么意思，请考虑这个递归版本的size：

   fun size L =
   let fun sizeHelper ([], acc) = acc
   | sizeHelper (x::xs, acc) = sizeHelper (xs, 1+acc)
   in sizeHelper (L, 0) end
   

   它的帮助函数有一个额外的参数，用于通过递归调用携带结果。这使得函数尾递归，折叠是这种技术的一种推广;fold 的辅助函数的第二个参数(作为参数给出)是累加变量。(fold 的帮助函数的第一个参数是单个参数而不是列表，这与上面size的显式递归版本不同。

3. 给定你的size函数(又名List.length)，你只完成了三分之一，因为

   size [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
   

   给你8个而不是[(0,[]),(1,[3]),(1,[2]),(2,[2,3]),...)]

   所以你需要编写另一个函数，(a)size应用于每个元素，这会给你[0,1,1,2,...]，(b)以某种方式将其与输入列表[[],[3],[2],[2,3],...]结合起来。您可以使用zip/map分两步完成此操作，也可以仅使用foldr一步完成此操作。

   尝试编写一个对输入列表不执行任何操作的foldr表达式L：

   foldr (fn (x, acc) => ...) [] L
   

   (就像op+一样，做op::而不是编写匿名函数是作弊。

   然后将每个x视为一个列表。