哈斯克尔 - 帮助理解函数

Question

我有我无法理解这个谜底功能：

mystery :: [a] -> [[a]] 
mystery [] = [[]] 
mystery (x:xs) = sets ++ (map (x:) sets) 
       where sets = mystery xs 

这里有一些输入，结果：

mystery [1,2] returns [[],[2],[1],[1,2]] 
mystery [1,2,3] returns [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]] 

通过看结果，我可以看到它计算列表中所有可能的数字组合，但不是所有可能的permuations ...我想。

我遇到的麻烦实际上是通过递归和理解函数如何获得这些结果。

我想我得到了它的开始 - >映射（1 :)到[2]上，产生[1,2]，但是在这一点上，我很困惑递归如何工作，以及我是否仍然映射（1 :)或现在（2 :)，然后到什么。

如果任何人都可以通过逐步解释（使用提供的示例之一）来帮助我解决这个函数如何工作（使用地图并设置递归），这将不胜感激！

谢谢！

Answer 1

您的神秘功能是计算其输入的power set。

Answer 2

Haskell将执行所谓的懒惰评估，这意味着它只会处理事情，因为它需要从左到右（通常）。所以，把你的mystery [1, 2]例如，哈斯克尔将执行以下操作：

sets ++ (map (x:) sets) 

计算结果为：

mystery (2:[]) ++ (map (1:) sets) 

在这一点上，我们称之为mystery (2:[])

mystery ([]) ++ (map (2:) sets) ++ (map (1:) sets) 

mystery ([])将返回空列表清单

[[]] ++ (map (2:) sets) ++ (map (1:) sets) 
[[]] ++ (map (2:) mystery []) ++ (map (1:) sets) 

所以现在哈斯克尔将尝试应用功能(2:)含一个空列表

[[]] ++ (2:[[]]) ++ (map (1:) sets) 
[[]] ++ [[2]] ++ (map (1:) sets) 
[[], [2]] ++ (map (1:) sets) 

这就是事情变得有点更加混乱名单上。

[[], [2]] ++ (map (1:) mystery (2:[])) 

这最后sets将评估mystery (2:[])

[[], [2]] ++ (map (1:) (sets ++ (map (2:) sets))) 
[[], [2]] ++ (map (1:) (mystery [] ++ (map (2:) sets)) 
[[], [2]] ++ (map (1:) ([[]] ++ (map (2:) mystery [])) 
[[], [2]] ++ (map (1:) ([[]] ++ (2:[[]])) 
[[], [2]] ++ (map (1:) ([[]] ++ [[2]]) 

现在(1:)将被应用到其中包含一个空列表列表，包含2列表：

[[], [2]] ++ (map (1:) ++ [[], [2]]) 
[[], [2]] ++ [[1], [1, 2]] 
[[], [2], [1], [1, 2]] 

实手术的肉在最后两节中。 Haskell创建一个列表，如[[], [2]]，然后在每个列表的头部添加一个表格以形成[[1], [1, 2]]。