2

我理解并在 F# 中编写了一个典型的幂集函数（类似于Wikipedia中的算法部分）

后来我发现这个 powerset 的实现看起来不错而且很紧凑，希望我不明白。

let rec powerset = function
                   | [] -> [[]]
                   | h::t -> List.fold (fun xs t -> (h::t)::t::xs) [] (powerset t);

我将其分解为 1 步非递归函数，以找到 [1;2] 的幂集，并在末尾硬编码 2 的幂集值 [[2]; []]

let right = function
                   | [] -> [[]]
                   | h::t -> List.fold (fun acc t -> (h::t)::t::acc) [] [[2]; []];

输出[[1]; []; [1; 2]; [2]]是正确的。

但是我期待 List.Fold 输出[[1; 2]; []; [1; 2]; [2]]。

由于我不确定't'，我修改了变量名，我确实得到了我所期望的。当然，这不是 [1;2] 的正确幂集。

let wrong  = function
                  | [] -> [[]]
                  | h::t -> List.fold (fun acc data -> (h::t)::data::acc) [] [[2]; []];

对我来说，'t'（有趣而不是 h::t）只是 'fun' 的第二个参数的名称，但显然情况并非如此。那么我写的“正确”和“错误”F#函数有什么区别呢？这里的“不”到底指的是什么？

谢谢 ！（我是 F# 的新手）

4

3 回答 3

2

在您的“正确”示例中，t最初是模式匹配中绑定的值的名称，但它被t传递给的 lambda 表达式中的参数隐藏List.fold。而在您的“错误”示例中，t它被捕获为 lambda 表达式中的闭包。我想也许您不打算进行此捕获，而是您想要：

//now it works as you expect, replaced "t" with "data" in your lambda expression.
let wrong  = function
                  | [] -> [[]]
                  | h::t -> List.fold (fun acc data -> (h::data)::data::acc) [] [[2]; []];
于 2011-05-25T15:39:40.043 回答
1 
let rec powerset = function
                   | [] -> [[]]
                   | h::t -> List.fold (fun xs t -> (h::t)::t::xs) [] (powerset t);

这是代码的理解/英文翻译：

  1. 如果列表（你想要权力）为空，则返回一个列表，其中包含一个空列表

  2. 如果列表是h::t（头部h和其余部分为t，h则元素t也是列表）。然后：

    A.：(powerset t)计算幂集t

    B.(fun xs t -> (h::t)::t::xs)表示您将此功能应用/折叠到(powerset t). 更多细节：xs是一个累加器，它被初始化为[]. xxx::xs意味着你在现有的 powerest 中添加一些东西xs。这里xxx是(h::t)::t，这是要添加到头部的两个元素xs。(h::t)表示add head to t和t表示 中的每个元素(powerset t)。<- 令人困惑的部分在于t，tin(powerset t)是列表的其余部分，而另一个t表示 中的元素(powerset t)。

这是fold函数的命令式翻译：

let h::t = list
let setfort = powerset t
xs <- []
foreach s in setfort do
  xs <- xs.add(t) // t is a valid subset of list
  xs <- xs.add(h::t) // t with h is also a valid subset of list
于 2011-05-25T15:40:39.293 回答
-4

t是由模式匹配绑定的变量。List.fold 是一种避免显式循环的奇特方式。现在，去阅读一些关于 F# 的介绍性教程。

于 2011-05-25T15:31:09.643 回答