列表理解 - 需要基础案例？

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

你可以想到<-使用左边表达式右边列表中的每个元素.由于[]没有元素,整个列表理解返回一个空列表.如果[ x:y | x<-[], y<-[] ]返回[[]]因为:获取元素和列表,那将是奇怪的.所以要生成[[]]y必须[]但是接下来会是x什么？

正如KennyTM所说[]的那样[[a]].实际上[]是来自这种类型的所有类型: [a] [[a]] [[[a]]]等等.如果不是那么函数就没有办法返回一个空列表.

无论如何,忘记一些括号是一个非常常见的错误,这就是为什么类型注释是必要的.