Nested list comprehensions in Haskell

Question

I am following this Haskell tutorial and am on the higher order functions section. It defines a function called chain as:

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

There is an exercise to find number of "chains" that have a length longer than 15. They do so like this:

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

I am trying to come up with a list comprehension that instead of giving me the number of chains gives me a list of chains that are longer than 15 from [1..100]. My closest attempt so far looks like:

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

but I get:

<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]

Am I even close? I do want to solve this problem using a nested comprehension for the sake of learning despite the possible better ways to approach this.

came here at exactly the same place in the tutorial!

JonnyRaa
– JonnyRaa

2017-10-13 12:11:28 +00:00
Commented Oct 13, 2017 at 12:11 — JonnyRaa
– JonnyRaa, Commented Oct 13, 2017 at 12:11

ErikR · Accepted Answer · 2014-12-02 00:10:35Z

5

You're close. You're looking for:

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

The expression

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

has type:

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

which is clearly not what you want, but because of Haskell's polymorphic numeric literals, it could possibly type check if the correct definition were in place.

In this case b is inferred to be a list of some type, and that is why you see the error:

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

Here is a complete run down on how the types are inferred.

from b <- [1..100] we can infer Enum b is a constraint
from the call chain b we can infer Integral b is a constraint
from a <- chain b we can infer a and b have the same type
from length a we can infer a is a list of something, e.g. a ~ [t]

So from (3) and (4) we can infer that b ~ [t] and so we need both Integral [t] and Enum [t] for some type t.

To further elaborate on (3), we know chain b is a list, e.g. [t] where t is the type of b. From a <- chain b we know a has the same type as the elements of chain b, i.e. the type of a is also t.

edited Dec 2, 2014 at 0:10

answered Dec 1, 2014 at 23:54

ErikR

52.2k9 gold badges78 silver badges136 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

AJF Over a year ago

@MattVaughan - Just to make it clear, nested list comprehensions are possible, but your types got a bit mixed up.

Matt Vaughan Over a year ago

When you write a let expression, does it act as an alias and end up having to evaluate it twice, or does it evaluate the expression and then use that value everywhere else. For example, in [ a | b <- [1..10], let a = chain b, length a > 15 ] does it have to evaluate chain b everywhere it sees a?

ErikR Over a year ago

It will only be evaluated once.

Collectives™ on Stack Overflow

Nested list comprehensions in Haskell

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related