Error in nested list comprehension in Haskell code

I am trying to write the following list compre开发者_高级运维hension in Haskell and it doesn't typecheck. I am new at this and can't really figure out why.

something :: Int -> [Int]
something n = [[ 2 * x + 1 | x <- xs]|xs <- [3..n],i <- [1..],j <-[1..] ,xs == i+j+2*i*j,i<=j,i>=1]

This is what I see:

Couldn't match expected type `Int' with actual type `[t0]'
    In the expression: [2 * x + 1 | x <- xs]

NB: There could be a lot more wrong with this piece of code.

Here's what I am really trying to learn to do. From a list of all naturals from 3 to n(which is the Int input to the function), I want to extract just the subset of numbers which can be written as i+j+2*i*j where i, j are integers and the i<=j and i>=1. To this subset list , I want to apply the function 2*x+1 to each element x and output a final list.

Hope that makes sense.

---

First of all you have a nested list comprehension, so you're creating a list of lists, so the return type should be [[Int]] (list of lists of ints) and not [Int] (list of ints).

Second of all xs is a number (because you take it out of a list of numbers), but its name suggests that it's a list and when you do x <- xs you're actually treating it as if it was a list.

In response to your edit: I don't really see why you thought you needed nested list comprehensions for this. If we just remove the nesting from your code, we get something that is pretty close to working (I've also renamed xs to x because calling a number xs is just confusing - I've also removed the condition that i is at least 1 because that's already a given since you take i from the list [1..]):

[ 2 * x + 1 | x <- [3..n], i <- [1..],j <-[1..] ,x == i+j+2*i*j,i<=j]

Now this compiles, but it will loop forever. Why does it loop forever? Because you take i and j from infinite lists. This means it will start with x=3, i=1, j=1 and then try all values for j from 1 to infinity before it will try the next value of i (so in other words it will never try the next value of i).

So what we need to do is to give i and j upper bounds. An easy upper bound to pick is x (if i or j are greater than x (and neither is smaller than 1), i+j+2*i*j can't possibly be equal to x), so you get:

[ 2 * x + 1 | x <- [3..n], i <- [1..x],j <-[1..x], x == i+j+2*i*j, i<=j]

This works, but it can still be simplified a bit by somewhat: If we take j from the list [i..n] instead of [1..n], we guarantee that j is at least i and we don't need the condition i<=j anymore, so we can write:

[ 2 * x + 1 | x <- [3..n], i <- [1..x], j <-[i..x], x == i+j+2*i*j]

PS: Doing it this way (iterating over all x and then iterating over all possible values of i and j for each x) is a bit inefficient, so you might reconsider your approach. On the other hand if all you need is something that works, this is fine.

---

First, a function name must not be upper-case.

xs <- [3..n] means that xs is an Int, but x <- xs uses it as a list.

The rest of the comprehension looks a little bit strange, too. If you care to explain what exactly you want to do, we might be able to help a little bit more. :-)

[Edit]

You get an infinite list of your numbers by using [i+j+2*i*j| j <-[2..], i<-[1..(j-1)]], but it's not sorted. [x| x <-[3..(2*n*n)], j <-[2..n], i<-[1..(j-1)], x==i+j+2*i*j] gives a sorted list of all such numbers smaller than 2n².

---

Let's start with what you've got.

something n = [[ 2 * x + 1 | x <- xs]|xs <- [3..n],i <- [1..],j <-[1..] ,xs == i+j+2*i*j,i<=j,i>=1]

The basic problem here is that you don't need a nested list comprehension.

something n = [ 2 * x + 1 | x <- [3..n], i <- [1..], j <- [1..], x == i+j+2*i*j, i<=j, i>=1]

This will compile. But there is, as you suspect, a lot more wrong with this piece of code.

Let's start with the conditions. Testing for i>=1 is superfluous, given that i <- [1..].

something n = [ 2 * x + 1 | x <- [3..n], i <- [1..], j <- [1..], x == i+j+2*i*j, i<=j]

Similarly, we can get rid of the i<=j condition if we start j off at i instead of at 1.

something n = [ 2 * x + 1 | x <- [3..n], i <- [1..], j <- [i..], x == i+j+2*i*j]

It should be clear that values of j greater than (n - i) `div` (1 + 2 * i) cannot possibly result in an x ≤ n.

something n = [ 2 * x + 1 | x <- [3..n], i <- [1..], j <- [i .. (n - i) `div` (1 + 2 * i)], x == i+j+2*i*j]

Similarly, values of i of n `div` 3 or above cannot possibly result in an x ≤ n.

something n = [ 2 * x + 1 | x <- [3..n], i <- [1 .. (n `div` 3) - 1], j <- [i .. (n - i) `div` (1 + 2 * i)],
                            x == i+j+2*i*j]

At this point we have done enough for something to actually generate results. But there are duplicate values (e.g. when (i,j) is either (1,7) or (2,4) you get x = 22), which I assume you don't want.

We filter them out using nub from Data.List.

something n = nub [ 2 * x + 1 | x <- [3..n], i <- [1 .. (n `div` 3) - 1],
                                j <- [i .. (n - i) `div` (1 + 2 * i)], x == i+j+2*i*j]

There's no need to check that x satisfies a condition when we could construct x to satisfy that condition in the first place. (You will want to satisfy yourself that 3 ≤ x ≤ n still.) This is more efficient.

something n = nub [ 2 * x + 1 | i <- [1 .. (n `div` 3) - 1], j <- [1 .. (n - i) `div` (1 + 2 * i)],
                                let x = i+j+2*i*j]

The results are no longer coming out in ascending order, so let's make sure they do.

something n = sort $ nub [ 2 * x + 1 | i <- [1 .. (n `div` 3) - 1], j <- [1 .. (n - i) `div` (1 + 2 * i)],
                                       let x = i+j+2*i*j]

On a style point, the doubling and adding one is a separate calculation from ensuring that x can be expressed as i+j+2*i*j, so let's split them up.

something n = sort $ map f $ nub [ x | i <- [1 .. (n `div` 3) - 1], j <- [1 .. (n - i) `div` (1 + 2 * i)],
                                   let x = i+j+2*i*j]
  where f x = 2 * x + 1

This allows us to get rid of x from the list comprehension.

something n = sort $ map f $ nub [ i+j+2*i*j | i <- [1 .. (n `div` 3) - 1],
                                               j <- [1 .. (n - i) `div` (1 + 2 * i)]]
  where f x = 2 * x + 1

Done.