[Haskell-cafe] list comprehension doesn't work

[Richard A. O'Keefe]

On 15/05/2013, at 2:57 AM, John wrote:

> Hi,
> 
> I have to write a function which returns a list of all pairs (x,y) where x,
> y ∈ N AND:
> –  x is the product of two natural numbers (x = a · b, where a, b ∈ N) AND
> –  x is really bigger than 5 but really smaller than 500, AND
> –  y is a squer number (y = c² where c ∈ N) NOT greater than 1000, AND
> –  x is a divisor of y.

Step 1.  If   a >= 0 and b >= 0 & x = a*b & x < 500 & x > 5
         then a > 0 and a < 500
          and b > 0 and b < 500.

This suggests something like

    xs = [x |
          a <- [1..499],
          b <- [1..499],
          let x = a*b,
          5 < x, x < 500
         ]

Step 2.
However, that will generate duplicates.  If a*b = x then b*a = x, and
non-square values of x will be generated twice.
Let's just filter [6..499].
If x is in that range, and a is a number in the range [1..x-1],
and x `mod` a is zero, then x = a*b for some integer b, and b will
_have_ to be in the range you are looking for.

    xs = [x |
          x <- [6..499],
          or [x `mod` a == 0 | a <- [1..x-1]]
         ]

xs has 494 elements.  At first I was surprised to see that 7 was in
the list.  However, if x = 7, a = 7, b = 1, then indeed a and b are
natural numbers and x is there product, so _every_ number in the
range 6..499 qualifies.

Step 3.  If   c >= 0 and y = c*c and y <= 1000
         then c >= 0 and c <= 31

This gives us

    ys = [c*c | c <- [0..31]]

or even

    ys = map (^2) [0..31]

which of course has 32 elements.

Step 4.

Now all that's left to test is whether x divides some y:

    [(x,y) | x <- xs, y <- ys, y `mod` x == 0

pairs :: [(Int,Int)]

pairs = [(x,y) | x <- xs, y <- ys, y `div` x == 0]
  where xs = [x | x <- [6..499], or [x `mod` a == 0 | a <- [1..x-1]]]
        ys = [c*c | c <- [0..31]]

This has 641 elements.

If the definition was supposed to be that x is a *composite* number
with factors a, b, then we need to search for "a" in the range [2..x1].

Using

pairs = [(x,y) | x <- xs, y <- ys, y `div` x == 0]
  where xs = [x | x <- [6..499], or [x `mod` a == 0 | a <- [2..x-1]]]
        ys = [c*c | c <- [0..31]]                       --  ^

xs has 402 elements and pairs has 546 elements.

> listPairs :: [(Int, Int)]
> listPairs = [(x,y) | x<-[0..], y<-[0..], x<-[0..]*[0..], x > 5, x < 500,
> (y*y) < 1001, mod y x == 0]
> 
> However it doesn't work unfortunatly 
> 
> Could anyone tell me where my mistake is?

One mistake is that [0..]*[0..] is a type error.
* wants a pair of numbers, and [0..] is not a number.
(There are modules that make lists "numbers", but then
 as*bs is usually the same as zipWith (*) as bs, which
 is not what you want anyway.)

The main mistake is that

[x | x <- [0..], x > 5, x < 500]

is equivalent to

    for (x = 0; true; x++) if (x > 5 && x < 500) yield x

That is, the [0..] part is happy to keep on generating
increasing integers, it neither knows, nor does it care,
that there is an x < 500 test downstream.

If you really want an infinite set searched, by all means
use [0..].  But if you only want a finite range, put BOTH
bounds in the interval so that it will stop.