仅使用映射和折叠在 ML 中实现幂集函数

Question

我需要在 ML 中实现一个 powerset 函数，它采用具有以下限制的整数列表：

1) 除 map、foldr 和 foldl 外，切勿调用内置库函数。
2）永远不要递归。所有递归都发生在 map 和 fold
中 3) 永远不要包含 let 或局部表达式

我已经使用以下形式的正常递归在没有这些约束的情况下实现了函数：

幂集(x::xs) = 幂集(xs) @ x.powerset(xs)

我想不出一种方法来将这种类型的实现转换为仅使用贴图和折叠的实现。

我不一定要找人为我实施它，但我会很感激在正确的方向上推动或任何帮助。

他康

Answer 1

下面是我如何解决折叠问题。

想想你想要获得的最终价值。在您的情况下，这将是输入列表的幂集。现在的关键问题是：插入新元素后能否重新计算列表的幂集？也就是说，给定 P(S)，某些项目集 S 的幂集，可以仅根据 P(S) 和 x?

我相信你已经在上面明确地回答了这个问题。也许不是很明确，但是如果您修改 Powerset 函数，您会发现其中隐藏着正确的想法。您需要将此代码打包成一个小辅助函数：

fun extendPowerset (PS : 'a list list, x : 'a) : 'a list list =
  (* PS is the powerset of some set S. This function
   * should return the powerset of S ∪ {x}. *)
  ...

太好了，现在如何将其插入折叠？好吧，在折叠的每一步，你都会得到两件事：

列表的下一个元素，并且
根据所有先前元素计算的一些值（将其视为先前元素的 "summary"）

在 return 中，您必须计算一个稍大的摘要：它应该总结下一个元素除了之前的所有元素。是不是有种隐隐约约的相似感？ extendPowerset 函数基本上完全满足您的需求，其中前面元素的 "summary" 是这些元素的幂集。剩下的就交给你了。

旁白：请注意，您还可以使用折叠附加两个列表。作为提示，请尝试计算 foldl op:: [1,2] [3,4] 计算出的值。这不太像附加 [1,2] 和 [3,4]，但它很接近...

Answer 2

就像你已经做的那样，我也将首先使用显式递归编写一个 powerset 函数。然后我会尝试发现高阶函数模式并在之后替换它们，一次一个模式。

例如，您可以打开辅助函数

fun consMany (x, []) = []
  | consMany (x, L::Ls) = (x::L) :: consMany (x, Ls)

进入表达式

map (fn L => x::L) Ls

您可以删除一个 let 表达式（对于重复使用一次计算值两次很有用）

fun foo (x::xs) =
    let val rest = foo xs
    in ... x ... rest ... rest ...
    end

使用函数：

fun foo (x::xs) =
    bar (x, foo xs)

and bar (x, rest) = ... x ... rest ... rest ...

尽管如此，这也可能是一个匿名函数：

fun foo (x::xs) =
    (fn rest => ... x ... rest ... rest ...) (foo xs)

你可能会转一个列表递归函数
```
fun derp [] = ...
  | derp (x::xs) = g (x, derp xs)
```
折叠：
```
fun derp xs = foldr g (...) xs
```
但如果结果的顺序无关紧要，foldl is tail-recursive.

仅使用映射和折叠在 ML 中实现幂集函数

Implementing powerset function in ML using only map and folds

recursion

sml

fold

ml

powerset