如何在不使用Haskell中的map或lambda的情况下制作powerset？

我正在尝试在Haskell中创建一个powerset（我对它很陌生），并且我无法弄清楚为了让一个没有地图而需要做什么。 WITH map and lambda，I found this solution：如何在不使用Haskell中的map或lambda的情况下制作powerset？

powerset :: Set a -> Set (Set a) 
powerset [] = [[]] 
powerset (head:tail) = powerset tail >>= \set ->[set, head:set] 
powerset (x:xs) = map (x:) (powerset xs) ++ powerset xs

这不是我想要的。我查看了其他问题，无法找到我正在寻找的答案。帮助将不胜感激！

编辑：这是我到目前为止..它显然不工作，但我试图！

powerset :: Set a -> Set (Set a) 
powerset [] = [[]] 
powerset (x:xs) = [x + (powerset xs)] + powerset xs

来源

2016-09-14 TurboCrackers

您还有什么感兴趣的其他方式？列表解析？另外我想你忘了说你已经定义了'type Set a = [a]'，并且你没有使用['containers']中的那个（https://hackage.haskell.org/package/containers-0.5 .7.1/docs/Data-Set.html） – epsilonhalbe

你没有告诉我们的错误部分是由于'（+）'只处理数字类型而不是列表 - 你应该使用'（++）'代替。 – epsilonhalbe

@epsilonhalbe是的，我想使用列表解析！也是的，我在创建我的功能之前做了这个：type Set a = [a] 同样我会改为++ :) – TurboCrackers

你几乎没有 - 如果你想使用列表理解，这相当于map在这种情况下，你只需要一小步：

powerset (x:xs) = [x:ps | ps <- powerset xs] ++ powerset xs

_{我什么好奇 - 为什么你想避免map，它是你会发现的最重要的函数编程模式之一！但我想这不是我答案的一部分 - 只是一个附注。}

来源

2016-09-14 23:04:16 epsilonhalbe

OMG非常感谢你！你让一切都变得更有意义。我以前看过列表解析，但我并没有真正理解它们。这是超级有用的:)另外，我的导师希望我们使用列表解析，以便我们确切地理解发生了什么。这是TAMU的编码语言课程！我完全同意地图很重要。 – TurboCrackers

从评论：

a' with [a]' a' is a rigid type variable bound by the type signature for powerset :: Set a -> Set (Set a) at assignment2.hs:71:1 In the first argument of (++)', namely x' In the expression: x ++ (powerset xs) In the first argument of (++)', namely `[x ++ (powerset xs)]'

这是因为powerset返回Set (Set a)其中Set仅仅是列出的别名。请注意，(++)将两个相同类型的列表连接起来。由于x是Set a，因此它不能与Set (Set a)级联。相反，您应该使用cons运算符(:)，它将一个元素附加到列表的开头。

x : powerset xs

来源

2016-09-14 23:09:42

我也发现在第二行切换[[]]和[]可以修复一切！它现在可以工作，用@epsilonhalbe的解决方案！感谢您的帮助！ – TurboCrackers

@LauraAdams'在第二行切换[[]]和[]固定所有内容'这可能会修复编译器错误，但是现在你有一个逻辑错误，因为你只会得到一个大的长列表，而不是列表需要。 –

如何在不使用Haskell中的map或lambda的情况下制作powerset？

回答

相关问题