Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is a good way to generate a infinite list of all integers in Haskell

Tags:

haskell

I wrote the following function in haskell, as it will enumerate every integer:

integers = (0:)$ concat $ zipWith (\x y -> [x,y]) [1..] (map negate [1..])

I wonder if there are better ways to do it, it does seem a bit too complicated.

Also, I wonder are there standard implementations to list all elements in the integer lattice of dimension $k$.

like image 787
Chao Xu Avatar asked Mar 17 '12 12:03

Chao Xu


3 Answers

integers = 0 : concat [[x,(-x)] | x <- [1..]]

(or, alternatively, as in @DanielWagner's solution in the comment below that works better I think)

like image 141
Riccardo T. Avatar answered Apr 28 '23 07:04

Riccardo T.


import Control.Applicative

integers = 0 : zipWith (*) ([1..] <* "mu") (cycle [1,-1])

Of course you can take the path of the non-monk as well:

integers = 0 : [y | x <- [1..], y <- [x,-x]]

But then you won't understand the true meaning of mu.

like image 24
Landei Avatar answered Apr 28 '23 07:04

Landei


map fun [0 .. ]
  where
    fun n
      | even n = n `quot` 2
      | otherwise = (1 - n) `quot` 2

There aren't any standard implementations to list all points in ℤk. Not even for k == 1, really. But with any enumeration of ℤ and a cartesian product of two lists that outputs any pair at a finite index even if the lists are infinite (some possible implementations here), you can roll your own.

integers :: [Integer]
integers = -- whatever is your favourite implementation

-- get all pairs at finite index, even for infinite input lists
-- 
cartesian :: [a] -> [b] -> [(a,b)]
cartesian xs ys = ???

-- enumDim k enumerates the points in ℤ^k, to avoid type problems, the points
-- are represented as lists of coordinates, not tuples
enumDim :: Int -> [[Integer]]
enumDim k
  | k < 0     = error "Can't handle negative dimensions"
  | k == 0    = [[]]
  | otherwise = map (uncurry (:)) $ cartesian integers (enumDim (k-1))
  -- alternative:
  {-
  | k == 1    = map return integers
  | otherwise = map (uncurry (++)) $ cartesian (enumDim h) (enumDim (k-h))
    where
      h = k `quot` 2
  -}
like image 40
Daniel Fischer Avatar answered Apr 28 '23 08:04

Daniel Fischer