Output an element the number of times I want

Question

I have this code:

lado ::  [([Char],Int)] -> [[Char]]
lado xs = [a | (a,b) <- xs]

I need to output this:

> lado [("A",3),("B",2),("C",1)]
["A","B","C","A","B","A"]

I have to output "A" 3 times, then "B" 2 times then "C" 1 time but I only get this ["A","B","C"] with this code.

Answer 1

You can use recursion to accomplish this:

lado :: [(a, Int)] -> [a]
-- base case
lado [] = []
-- take each of the non-zero elements then recurse
lado xs = map fst nonzero ++ lado subtracted
    where
        -- find elements with non-zero count
        nonzero = filter (\x -> snd x > 0) xs
        -- subtract one from the count for each of those elements
        subtracted = map (\(x, n) -> (x, n - 1)) nonzero

Answer 2

You already use list comprehensions in your attempt. Use them some more.

lado ::  [([Char],Int)] -> [[Char]]
lado xs = [a | (a,b) <- xs, b <- [1..b]]

testing:

> lado [("A",3),("B",2),("C",1)]
["A","A","A","B","B","C"]

As your question is saying,

I have to output "A" 3 times, then "B" 2 times then "C" 1 time

But if it is really ["A","B","C","A","B","A"] you want, then

lado ::  [(a,Int)] -> [a]
lado []        = []
lado ((a,1):b) = a : lado b
lado ((a,n):b) = a : lado (b ++ [(a,n-1))])

which can be coded with unfoldr :: (b -> Maybe (a, b)) -> b -> [a] from Data.List,

lado ::  [(a,Int)] -> [a]
lado xs = unfoldr g $ xs
  where
  g []        = Nothing
  g ((a,1):b) = Just (a, b)
  g ((a,n):b) = Just (a, b ++ [(a,n-1)])

which can be emulated with Prelude's iterate :: (a -> a) -> a -> [a] etc., as

lado ::  [(a,Int)] -> [a]
lado xs = map (fst . head) . takeWhile ( ... ) . iterate g $ xs
  where
  g []            = []
  g ((a, ... ):b) = b
  g ((a,  n  ):b) = b ++ [(a, ... )]

Testing:

> lado [("A",3),("B",2),("C",1)]
["A","B","C","A","B","A"]

Fill in the blanks ... to make it work.

---

as @dfeuer notes, the repeated singleton-appending at list's end is detrimental to overall efficiency. With big thanks to his input and discussion, including the two answers and comments here and even a github gist, this can be remedied by the usual FP paradigm (not to say "trick") of building a list in reverse, as

lado ::  [(a,Int)] -> [a]
lado xs = go (filter ((> 0) . snd) xs) []
  where
  go []       []  =  []
  go []        r  =  go (reverse r) []
  go ((a,1):b) r  =  a : go b r
  go ((a,n):b) r  =  a : go b ((a,n-1):r)

With the reverse cost amortized over all the output this will add only a constant overhead per each output item.