How do I express {2n+3m+1|n,m∈N} in list comprehension form? N is the set of natural numbers, including 0.
views:
366answers:
6[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.)
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..]
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..]]
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]