Haskell. Tracking indexes to create a new list

Question

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

I am trying to complete this simple exercise in Haskell:

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

So, the items in the Input list will fall to False in Output , and the odd items will be True ; for each, it repeats as many times as the value in the Input list indicates.

Go to the Input list if the item i & thinsp; ᵗʰ is in a pair position, add to True output I times before Output ; if i & thinsp; ᵗʰ the element is in an odd position, adds False i times to the Output list.

This seems to be a very simple problem, and it is. But for me, without any functional programming, I don’t know how to express this in Haskell.

I tried to track the current index using a λ function in list comprehension.

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

But I don’t understand its behavior, so I ended up 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 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 resolved, because the elements 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 gives only the first of the entries. (Although I think that if it works, it is not very effective in solving this problem.)

How can I achieve the result that I am looking for in Haskellian?

Answer 1

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

You do not need an index for this, and it is better to avoid it - this gives a simpler and usually more efficient code. The fact is that the value alternates, it has a periodic pattern. To build such periodic patterns, Prelude offers 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] 

Well, that is what we need.

Now we can map each element of the input list to the corresponding Bool :

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

We could use zip to create pairs [(2,True), (2,False), ...] , and then use a function that converts the pair into the corresponding sequence of Bool s.

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

So, if the list item type is Int , we can write

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

For an Integer type, we cannot use replicate , but we can use genericReplicate from a Data.List .

Answer 2

It seems you already realized that you can use zip to pair elements with their indices. For each index i and the corresponding element n you want to create n copies of a boolean value (with replicate ), and that boolean depends on whether i odd or even. This means map ping each tuple (i, n) into a list of gates, so you get a list of lists ( [[Bool]] ). The final step is to combine these lists with concat (which can be combined with map in concatMap ).

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

Or if you don't like the zero-point 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 bn : r' (not b) ns r' b [] = [] 

(not verified)

Answer 4

 row :: [Integer] -> [Bool] row xs = row' xs True row' [] _ = [] row' (x:xs) b = (replicate xb) ++ (row' xs (not b)) 

Answer 5

This is how I do it.

 row [] = [] row xs = row' xs 0 where row' xs i | i >= length xs = [] | otherwise = (take (xs !! i) (repeat (isOdd i))) ++ (row' xs (i+1)) isOdd n = n `rem` 2 == 1 

But I do not have ghc on this computer to check it.

Answer 6

I interepret

Moving the input list, if the element i ᵗʰ is in the position of the pair, add True i times to Output to the output; if the element i is is odd, add False i times to the Output list.

I see two ways to interpret this. "For all elements, if the i-th element is even, return True I times. Otherwise, return false I times" or "For all elements, the i-th element containing (v :: Int) should return True v times if I am equal to or False v times if I am odd. " The second one already has a satisfactory answer, so I will give one for the first.

Some people like to reference indexes, but in this case you don't need to worry about pointers. You can determine how many Bool does not count how many items you have passed.

 accum f (x:[]) = [x] accum f (x:xs) = (x):(map f (accum f xs)) 

This function takes a function f and a list. It applies f to every item except the first, then makes a recursive call to the tail of the list, which again applies f to every remaining item, etc. The result is the following:

 accum (+1) [1,1,1,1,1] [2,3,4,5,6] 

The +1 function is applied twice to the second element, three times to the second, etc. Now, how does this help us ask? Ok, we can do this:

 accum (\x -> [head x] ++ x) $ map (\x -> [x]) [2, 4, 1, 1, 2] [[2],[4,4],[1,1,1],[1,1,1,1],[2,2,2,2,2]] 

First we convert each item to a list with one item. We are accum with the lambda that you see above, which combines the head into a list. Now we can directly convert to Bool without further manipulation.

 (map . map) odd $ accum (\x -> [head x] ++ x) $ map (\x -> [x]) [2, 4, 1, 1, 2] [[False],[False,False],[True,True,True],[True,True,True,True],[False,False,False,False,False]] 

You want [Bool] , not [[Bool]] so concat . Note that you can concat first and then map instead of map . map map . map :

 map odd $ concat $ accum (\x -> [head x] ++ x) $ map (\x -> [x]) [2, 4, 1, 1, 2]