Haskell. Keeping track of indices in order to generate a new list

Question

I decided to learn Haskell and also learn to think in a more functional way, so I'm trying to solve very simple exercises trying to use a good approach in this paradigm.

I'm trying to achieve this simple exercise in Haskell:

Input: [2, 4, 1, 1, 2]
Output: [True, True, False, False, False, False, True, False, True, True]

So, the elements in the Input list will fall to be False in the Output list, and the odd elements will be True; for each one repeated as much times as the value on the Input list indicates.

Traverse the Input list, if the i ᵗʰ item is in a pair position, append to output True i times to Output; if the i ᵗʰ item is in an odd position, append False i times to the Output list.

It seems to be a very simple problem, and it is. But for me, without any functional programming background, I don't know how to express that in Haskell.

I tried to keep track of the current index by using a λ-function within the list comprehension.

    row :: [Integer] -> [Bool]
    row xs = [ (last $ zipWith (\i x -> x) [1..] [0..i]) `mod` 2 == 0
                | j <- xs, i <- [0..j-1] ]

But I'm not understanding its behavior, so I ended using findIndices as a quick alternative:

    row :: [Integer] -> [Bool]
    row xs = [ (head $ findIndices (==j) (xs)) `mod` 2 == 0
                | j <- xs, i <- [0..j-1] ]

Using this last approach it seems OK:

    > let xs = [ 1, 4, 3, 2 ]
    > print $ row xs
    [True,False,False,False,False,True,True,True,False,False]

but the problem is not solved, for the items are not necessarily unique:

    > let xs = [ 2, 2, 4, 3]
    > print $ row xs
    [True,True,True,True,True,True,True,True,False,False,False]

because head findIndices only gives the first of the occurrences. (Though I think, event that if worked, that's not a very efficient way of solving this problem.)

How can I achieve the result I'm looking for in a Haskellian way?

Answer 1

You want to transform each element in the input list into a sequence of as many equal Bools as the element says, and you want the Bool be True if the index of the number in the input list is even, and False if the index is odd.

For that, you don't need the index, and it is better avoided - that gives simpler and usually more efficient code. The point is that the value alternates, it has a periodic pattern. To construct such periodic patterns, the Prelude offers the useful

cycle :: [a] -> [a]

Prelude> take 10 $ cycle [1,2,3]
[1,2,3,1,2,3,1,2,3,1]
Prelude> take 10 $ cycle [True,False]
[True,False,True,False,True,False,True,False,True,False]

Neat, that's exactly what we need.

Now, we can pair up each element of the input list with the corresponding Bool:

[  2,    2,   4,   3]
[True,False,True,False,...

We could use zip to produce pairs, [(2,True), (2,False), ...] and then use a function that transforms the pair into the appropriate sequence of Bools.

But that pattern is so common that we have a special higher-order function for that, zipWith.

So if the type of list elements is Int, we can write

row :: [Int] -> [Bool]
row xs = concat $ zipWith replicate xs (cycle [True,False])

For the type Integer, we can't use replicate, but we can use genericReplicate from Data.List.

Answer 2

It seems you already figured out that you can use zip to pair the elements with their indices. For each index i and the corresponding element n, you want to produce n copies of a boolean value (with replicate) and this boolean value depends on whether i is odd or even. This means mapping each tuple (i, n) to a list of booleans, so you get a list of lists ([[Bool]]). The last step is merging those lists with concat (which can be combined with the map into concatMap).

row = concatMap (\(i, n) -> replicate n (odd i)) . zip [1..]

Or if you don't like the pointfree style:

row xs = concatMap (\(i, n) -> replicate n (odd i)) (zip [1..] xs)

Answer 3

Another solution

row :: [Integer] -> [Bool]
row ns = r' True ns
    where
        r' :: Bool -> [Integer] -> [Bool]
        r' b (n:ns) = replicate b n : r' (not b) ns
        r' b   []   = []

(Not tested)