haskell - 列表理解 - 需要基本案例？

Question

我不明白为什么这里需要基本案例:

-- perms :: Ord a => [a] -> [[a]]
perms [] = [[]]
perms xs = [ (x:ps) | x <- xs, ps <- perms (xs \\ [x])]

在我看来它应该是自动从列表理解，但后来我注意到:

[ x:y | x<-[], y<-[] ]

评估为 []，而不是 [[]]，这似乎令人惊讶。

即便如此，我也感到惊讶的是，它在没有基本情况的情况下运行，但总是给出 []，这违反了类型签名。有没有一种简单的方法来跟踪列表理解的执行？ Debug.Trace.trace 似乎是原子的。

Answer 1

可以想到<- as 在左侧的表达式中使用右侧列表中的每个元素。自 []没有元素整个列表理解返回一个空列表。如果[ x:y | x<-[], y<-[] ]就奇怪了返回 [[]]因为:采用元素和列表。所以要生成[[]] y 必须是 []但接下来会是什么 x ？

正如 KennyTM 所说 []类型为 [[a]] .其实[]来自每一种类型: [a] [[a]] [[[a]]]等等。如果不是，则函数无法返回空列表。

无论如何，忘记一些括号是一个非常常见的错误，这就是为什么需要类型注释的原因。