Haskell中的嵌套列表解析

Question

我正在关注这个Haskell tutorial，我在高阶函数部分。它定义了一个函数调用链：

chain :: (Integral a) => a -> [a] 
chain 1 = [1] 
chain n 
    | even n = n:chain (n `div` 2) 
    | odd n = n:chain (n * 3 + 1) 

有一项工作，发现有一个长度大于15长，他们这样做这样的“链”的数量：

numLongChains :: Int 
numLongChains = length (filter isLong (map chain [1..100])) 
    where isLong xs = length xs > 15 

我想提出一个列表理解，而不是给我链条的数量给我一个从[1..100]超过15的链列表。我最近尝试到目前为止是这样的：

[ [ a | a <- chain b, length a > 15] | b <- [1..100]] 

，但我得到：

<interactive>:9:14: 
No instance for (Integral [a0]) arising from a use of `chain' 
Possible fix: add an instance declaration for (Integral [a0]) 
In the expression: chain b 
In a stmt of a list comprehension: a <- chain b 
In the expression: [a | a <- chain b, length a > 15] 

<interactive>:9:45: 
    No instance for (Enum [a0]) 
     arising from the arithmetic sequence `1 .. 100' 
    Possible fix: add an instance declaration for (Enum [a0]) 
    In the expression: [1 .. 100] 
    In a stmt of a list comprehension: b <- [1 .. 100] 
    In the expression: 
     [[a | a <- chain b, length a > 15] | b <- [1 .. 100]] 

<interactive>:9:46: 
    No instance for (Num [a0]) arising from the literal `1' 
    Possible fix: add an instance declaration for (Num [a0]) 
    In the expression: 1 
    In the expression: [1 .. 100] 
    In a stmt of a list comprehension: b <- [1 .. 100] 

难道我还差得远？尽管可能有更好的方法来解决这个问题，但我仍然想用嵌套理解来解决这个问题。

Answer 1

你很近。您正在寻找：

[ a | b <- [1..10], let a = chain b, length a > 15 ] 

表达

[ [ a | a <- chain b, length a > 15] | b <- [1..100]] 

具有类型：

Integral [a] => [[[a]]] 

这是不是你想要的，但因为Haskell的多态数字文本的，很显然，它可能可能键入检查是否有正确的定义。

在这种情况下b被推断为某种类型的列表，这就是为什么你看到的错误：

No instance for (Integral [a0]) ... 

这里是关于类型如何推断出一个完整的运行下去。

1. 从b <- [1..100]我们可以推断Enum b一个来自呼叫chain b约束
2. 我们可以推断Integral b从a <- chain b约束
3. 我们可以推断a和b从length a具有相同类型的
4. 我们可以推断出a是一些东西，例如a ~ [t]

所以从（3）和（4）我们可以推断，b ~ [t]，所以我们需要某种类型的t两个Integral [t]和Enum [t]。

为了进一步阐述（3），我们知道chain b是一个列表，例如， [t]其中t是b的类型。从a <- chain b我们知道a具有与chain b的元素相同的类型，即a的类型也是t。