Create a mapping operation so each input element produces 1 or more output elements?

Question

Recently I am trying to figure out how to do some programming in Haskell.

I'm trying to do some simple operations. Right now I'm stuck with an operation like in this example:

input = [1,2,3,4]
output = [1,2,2,3,3,3,4,4,4,4]

That is, for each element x in input, produce x elements of x in output. So, for element 1 in input, append [1] to output. Then, for element 2 in input, append elements [2,2] to output. Then, for element 3, append [3,3,3], etc. The algorithm should work only on standard numbers.

I know it's very easy, and it's trivial to perform it in "normal" imperative programming, but as Haskell's functions are stateless, I'm having a problem in how to approach this.

Could anyone please give me some hint how can an absolute Haskell beginner cope with this?

Answer 1

You've just discovered monads!

Here's the general idea of what you're doing:

For each a-element in the input (which is a container-type M a, here [a]), you specify an entire new container M b. But as a final result, you want just a single "flat" container M b.

Well, let's take a look at the definition of the Monad type class:

class (Applicative m) => Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b

which is exactly what you need. And lists are an instance of Monad, so you can write

replicates :: [Int] -> [Int]
replicates l = l >>= \n -> replicate n n

Alternatively, this can be written

replicates l = do
   n <- l
   replicate n n

---

It might be interesting to know that the, perhaps easier to understand, list comprehension

replicates l = [ n | n <- l, _ <- [1..n] ]

as suggested by chi, is actually just syntactic sugar for another monad expression:

     [ n | n <- l, _ <- [1..n] ] ≡ l >>= \n -> [1..n] >>= \_ -> return n

... or least it used to be in some old version of GHC, I think it now uses a more optimised implementation of list comprehensions. You can still turn on that de-sugaring variant with the -XMonadComprehensions flag.

Answer 2

Yet another solution, exploiting list comprehensions:

output = [ n | n <- input , m <- [1..n] ]

Compare the above with the imperative Python code:

for n in input:            -- n <- input
   for m in range(1,n+1):  -- m <- [1..n]    (in Python the second extreme is excluded, hence +1)
      print n              -- the n in [ n | ... ]

Note that m is unused -- in Haskell it is customary to can call it _ to express this:

output = [ n | n <- input , _ <- [1..n] ]