Repeaters.hs

-- My somewhat-optimized implementation looks like this:

-- Assumes all the Ints are positive
lado' :: [(a, Int)] -> [a]
lado' [] = []
lado' xns = start ++ rest
  where
    start = [x | (x, _) <- xns]
    rest = lado' [(x, n - 1) | (x, n) <- xns, n /= 1]

lado :: [(a, Int)] -> [a]
lado = lado' . filter (\(_, n) -> n > 0)

-- Where's the potential space leak? The `rest` thunk contains a reference to
-- `xns`, which means that it holds references to all those (possibly enormous)
-- values of type `a`. But it doesn't necessarily *need* all of them; some of
-- them have count values of 1, so they will be discarded as `rest` is evaluated.
-- What we'd like to do is discard those values as soon as we're done with them.
-- Here's one way to do it:

lado'' :: [(a, Int)] -> [a]
lado'' [] = []
lado'' xns0 = go xsns0 table0 table0
  where
    -- The type here reflects the fact that we only use the second
    -- copy of the table to force its spine.
    go :: [(a, Int)] -> [(a, Int)] -> [x] -> [a]
    go [] table _sched = lado'' table
    go ((x, n) : xns) table sched
      | n == 1
      = sched `seq` x : go xns table sched
      | sched' <- drop 1 sched
      = sched' `seq` x : go xns table sched'
      
    table0 = [(x, n - 1) | (x, n) <- xns0, n /= 1]
    
-- We use `sched` (a "schedule") to force the construction of
-- table0 as the initial portion is consumed. Working carefully
-- like this (i.e., having the `n == 1` special case) prevents
-- us from constructing more table than we need, which is good
-- if it's not all used.

-- Now here's the "industrial Haskell" version:

-- Here's the "industrial Haskell" version:

industrialLado :: [(a, Int)] -> [a]
-- For fusion
{-# INLINE industrialLado #-}
industrialLado = lado''' . listToIList

-- | @IList a@ is isomorphic to @[(a, Int)]@, but it's a little
-- stricter. This lets us unpack things so that each list cons
-- uses four words of memory rather than eight, and to avoid
-- multiple indirections to get to the contents.
-- Invariant: the Int values are always (strictly) positive.
data IList a
  = ICons a !Int (IL a)
  | INil

listToIList :: [(a, Int)] -> IList a
-- For fusion
{-# INLINE listToIList #-}
listToIList = foldr go INil
  where
    go (a, i) r
      | i <= 0 = r
      | otherwise = ICons a i r

lado''' :: IList a -> [a]
lado''' INil = []
lado''' xns0 = go xsns0 table0 table0
  where
    -- The type here reflects the fact that we only use the second
    -- copy of the table to force its spine.
    go :: IList a -> IList a -> IList x -> [a]
    go INil table _sched = lado''' table
    go (ICons x n xns) table sched
      | n == 1
      = sched `seq` x : go xns table sched
      | sched' <- case sched of
                    INil -> INil
                    ICons _ _ s -> s
      = sched' `seq` x : go xns table sched'
      
    table0 = retable xns
    -- I'm 99.9% sure GHC won't inline this, but let's go with belt
    -- and suspenders.
    {-# NOINLINE table0 #-}
    
    retable :: IList a -> IList a
    retable INil = INil
    retable (ICons x n xns)
      | n == 1 = retable xns
      | otherwise = ICons x (n - 1) (retable xns)

side note: reference: https://stackoverflow.com/questions/64189254/output-an-element-the-number-of-times-i-want/64189269?noredirect=1#comment113528083_64189269.

aha, so that rotation thing did have its merit. applying your deferred-reversal queue idea, inlining and fusing everything, simplistically I'd just express it as

lado ::  [(a,Int)] -> [a]
lado xs = go 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)

Perhaps I should even add this version to my answer, with thanks to your input, criticism, and discussion of course. :)

Hmmm ... This won't work for input that ends in an infinite sequence of 1 counts.

Fixing that is a bit annoying. It requires that we be able to step the table construction from the input side. Hmph. The queue is looking more and more appealing in comparison!