Produce the infinite list [0, 1, -1, 2, -2, ... in Haskell

Question

So suppose we want to produce the list [0, 1, -1, 2, -2, ...in Haskell.

What is the most elegant way of accomplishing this?

I came up with this solution:

solution = [0] ++ foldr (\(a,b) c->a:b:c) [] zip [1..] $ map negate [1..]

But I am sure there must be a better way.

Coffeehouse

Answer 1

This seems like the kind of thing that comprehensions are made for:

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

Ensphere

Answer 2

With iterate

Perhaps a more elegant way to do this, is by using iterate :: (a -> a) -> a -> [a] with a function that generates each time the next item. For instance:

solution = iterate nxt 0
    where nxt i | i > 0 = -i
                | otherwise = 1-i

Or we can inline this with an if-then-else:

solution = iterate (\i -> if i > 0 then -i else 1-i) 0

Or we can convert the boolean to an integer, like @melpomene says, with fromEnum, and then use this to add 1 or 0 to the answer, so:

solution = iterate (\i -> fromEnum (i < 1)-i) 0

Which is more pointfree:

import Control.Monad(ap)

solution = iterate (ap subtract (fromEnum . (< 1))) 0

With (<**>)

We can also use the <**> operator from applicate to produce each time the positive and negative variant of a number, like:

import Control.Applicative((<**>))

solution = 0 : ([1..] <**> [id, negate])

Exscind

iterate (\i -> fromEnum (i < 1) - i)? – Chlorenchyma

Isn't flip (-) subtract? – Chlorenchyma

Excellent use of Applicative! – Ensphere

You also wouldn't need to import Control.Applicative if you used <*> instead of the flipped argument version. – Interflow

You need to flipped version so that id and negate alternate; [id, negate] <*> [1..] applies id to every element of the other list, then applies negate to the same. Since the second list is infinite, you never get the negative numbers. (More briefly, <**> is not just flip <*>.) – Gride

Answer 3

How about

concat (zipWith (\x y -> [x, y]) [0, -1 ..] [1 ..])

or

concat (transpose [[0, -1 ..], [1 ..]])

?

Chlorenchyma

Answer 4

How about:

tail $ [0..] >>= \x -> [x, -x]

On a moment's reflection, using nub instead of tail would be more elegant in my opinion.

Anabranch

nub is going to give you quadratic runtime and leak memory. It has to hold onto all of the earlier elements to check whether they have already occurred. – Ensphere

Right. I confused what nub does; I meant to remove only consecutive duplicates. And the reason I'd favor that was a semantic one. – Anabranch

Answer 5

another primitive solution

alt = 0 : go 1
  where go n = n : -n : go (n+1)

Dagan

Answer 6

You could also use concatMap instead of foldr here, and replace map negate [1..] with [0, -1..]:

solution = concatMap (\(a, b) -> [a, b]) $ zip [0, -1..] [1..]

If you want to use negate instead, then this is another option:

solution = concatMap (\(a, b) -> [a, b]) $ (zip . map negate) [0, 1..] [1..]

Guardianship

Answer 7

Just because no one said it:

0 : concatMap (\x -> [x,-x]) [1..]

Breannebrear

Answer 8

Late to the party but this will do it as well

solution = [ (1 - 2 * (n `mod` 2)) * (n `div` 2) | n <- [1 .. ] ]

Nuriel