仅使用地图和折叠在ML中实现powerset函数 [英] Implementing powerset function in ML using only map and folds

问题描述

我需要在ML中实现一个幂集函数，该函数需要一个具有以下约束的整数列表:

I need to implement a powerset function in ML that takes a list of ints with the following contraints:

1)切勿调用除map，foldr和foldl之外的内置库函数.
2)永远不要递归.所有递归都发生在map和fold
3)切勿包含let或本地表达式

1) Never call built in library functions except map, foldr, and foldl.
2) Never be recursive. All recursion occur within map and fold
3) Never contain let or local expressions

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

I've already implemented the function without these constraints using normal recursion of the form:

Powerset(x :: xs)= powerset(xs)@ x.powerset(xs)

Powerset(x::xs) = powerset(xs) @ x.powerset(xs)

我在想办法将这种类型的实现转换为仅使用地图和折叠的实现时遇到麻烦.

I'm having trouble thinking of a way to translate this type of implementation into one that uses only maps and folds.

我并不一定要有人为我实施它，但我希望朝着正确的方向前进，或者对此有任何帮助.

I'm not necessarily asking for someone to implement it for me, but I would appreciate a nudge in the right direction or any help for that matter.

Thakns

推荐答案

这是解决折痕问题的方法.

Here's how I go about solving problems with folds.

考虑要获取的最终值.在您的情况下，这就是输入列表的功能集.现在的关键问题是:插入新元素后，是否可以重新计算列表的幂集?也就是说，给定 P(S)，即某些项 S 的幂集，就有可能计算 P(S∪{x}) P(S)和 x 来表示?

Think about the final value you want to obtain. In your case, this would be the powerset of the input list. The crucial question is now this: can the powerset of a list be recomputed after inserting a new element? That is, given P(S), the powerset of some set of items S, it is possible to compute P(S ∪ {x}) in terms of only P(S) and x?

我相信您已经在上面肯定地回答了这个问题.也许不是显式的，但是如果您重做 Powerset 函数，您会发现其中隐藏了正确的想法.您将需要将此代码打包为一个小辅助函数:

I believe you've already answered this question definitively above. Not explicitly, perhaps, but if you rework your Powerset function, you'll find that the right idea is hidden in it. You'll want to package up this code into a little helper function:

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}. *)
  ...

太好了，现在您如何将它插入折叠呢?好吧，在弃牌的每一步，您都会得到两件事:

Great, now how do you plug that into a fold? Well, at each step of the fold, you are given two things:

1. 列表的下一个元素，
2. 从所有先前元素计算出的一些值(将此视为先前元素的摘要")

作为回报，您必须计算稍大的摘要:除了所有先前的元素之外，它还应总结下一个元素.这难道不是很相似吗? extendPowerset 函数基本上可以完全满足您的需要，其中先前元素的摘要"是这些元素的幂集.我把剩下的留给你.

In return, you must compute a slightly larger summary: it should summarize the next element in addition to all previous. Doesn't this feel vaguely similar? The extendPowerset function is basically doing exactly what you need, where the "summary" of the previous elements is the powerset of those elements. I'll leave the rest to you.

在旁边:请注意，您还可以在两个列表之间添加折叠.作为提示，请尝试计算出 foldl op :: [1,2] [3,4] 计算出的值.并不太像附加 [1,2] 和 [3,4] ，但是很接近...

Aside: note that you can also append two lists with a fold. As a hint, try working out what value is computed by foldl op:: [1,2] [3,4]. It's not quite like appending [1,2] and [3,4], but it's close...

这篇关于仅使用地图和折叠在ML中实现powerset函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！