views:

366

answers:

6

How do I express {2n+3m+1|n,m∈N} in list comprehension form? N is the set of natural numbers, including 0.

+7  A: 

Isn't {2n+3m+1|n,m ∈ ℕ} = ℕ - {0,2}?

vartec
no, 2 is not in the set comprehension.
nominolo
and 2. You can't get 1 from 2*n + 3*m
FryGuy
yeah, you're right. but apart from these two, any x > 2 ∈ N can be expressed as 2n+3m+1
vartec
+8  A: 

Shortly:

1:[3..]
Hynek -Pichi- Vychodil
+3  A: 

[2*n + 3*m +1 | m <- [0..], n <- [0..]] won't work because it starts with m = 0 and goes through all the n, and then has m = 1 and goes through all the n, etc. But just the m = 0 part is infinite, so you will never get to m = 1 or 2 or 3, etc. So [2*n + 3*m +1 | m <- [0..], n <- [0..]] is exactly the same as [2*n + 3*0 +1 | n <- [0..]].

To generate all of them, you either need to realize, like users vartec and Hynek -Pichi- Vychodil, that the set of numbers you want is just the natural numbers - {0,2}. Or you need to somehow enumerate all the pairs (m,n) such that m,n are nonnegative. One way to do that is to go along each of the "diagonals" where m + n is the same. So we start with the numbers where m + n = 0, and then the ones where m + n = 1, etc. Each of these diagonals has a finite number of pairs, so you will always go on to the next one, and all the pairs (m,n) will eventually be counted.

If we let i = m + n and j = m, then [(m, n) | m <- [0..], n <- [0..]] becomes [(j, i - j) | i <- [0..], j <- [0..i]]

So for you, you can just do

[2*(i-j) + 3*j +1 | i <- [0..], j <- [0..i]]

(Of course this method will also produce duplicates for you because there are multiple (m,n) pairs that generate the same number in your expression.)

newacct
dunno what i was drinking when i posted that answer :Pthanks for the explanation though :) and i will delete my useless post
Sujoy
You could always `nub` the list in order to eliminate duplicates, although then it's not strictly a list comprehension only, and it'll use inordinate amounts of memory.
ephemient
+4  A: 

The following Haskell function will give you all pairs from two lists, even if one or both is infinite. Each pair appears exactly once:

allPairs :: [a] -> [b] -> [(a, b)]
allPairs _ [] = []
allPairs [] _ = []
allPairs (a:as) (b:bs) = 
   (a, b) : ([(a, b) | b <- bs] `merge` 
             [(a, b) | a <- as] `merge` 
             allPairs as bs)
  where merge (x:xs) l = x : merge l xs
        merge []     l = l

You could then write your list as

[2 * n + 3 * m + 1 | (n,m) <- allPairs [0..] [0..] ]

To get a feel for how it works, draw an infinite quarter-plane, and look at the results of

take 100 $ allPairs [0..] [0..]
Norman Ramsey
A: 

You can try enumerating all pairs of integers. This code is based in the enumeration described in http://www.cs.berkeley.edu/~wkahan/Math55/pairs.ps (doesn't include 0)

data Pair=Pair Int Int deriving Show

instance Enum Pair where
    toEnum n=let l k=truncate (1/2 + sqrt(2.0*fromIntegral k-1))
                 m k=k-(l k-1)*(l k) `div` 2
             in 
               Pair (m n) (1+(l n)-(m n))
    fromEnum (Pair x y)=x+((x+y-1)*(x+y-2)) `div` 2

But you can use another enumeration.

Then you can do:

[2*n+3*m+1|Pair n m<-map toEnum [1..]]
hiena
A: 

my 0.2:

trans = concat [ f n | n <- [1..]]
 where 
  mklst x = (\(a,b) -> a++b).unzip.(take x).repeat
  f n | n `mod` 2 == 0 = r:(mklst n (u,l))
      | otherwise      = u:(mklst n (r,d))
  u = \(a,b)->(a,b+1)
  d = \(a,b)->(a,b-1)
  l = \(a,b)->(a-1,b)
  r = \(a,b)->(a+1,b)

mkpairs acc (f:fs) = acc':mkpairs acc' fs
                  where acc' = f acc
allpairs = (0,0):mkpairs (0,0) trans          
result = [2*n + 3*m + 1 | (n,m) <- allpairs]
primodemus