Haskell - repeat elements of a list according to their list-index

Question

I´m still a beginner in Haskell. I try to do some pattern matching. I want to repeat each element of a list n-times. N is determined by the index-place of every element in a list. For example ['1', '2', '3'] should give me: ['1', '2', '2', '3', '3', '3']. It´s an exercise and I shouldn´t use prebuild-list-functions.

I tried something like that:

test [] = []
test (first:[]) = [first] 
test (first:second:rest) = first : second : test (second:rest)

But it just doubled each element after the first element. I thought about elemIndex and replicate but I shouldn´t use these functions. My idea was to use elemIndex and with that using it as the my "n" and to use replicate or something similar after that with the "n" and recursion. I need something like that in Pattern matching. But I think, that I´m thinking too complicated. Has there anyone an idea?

Answer 1

A big part of Haskell is breaking things down into smaller problems. So let's break your problem down.

One of the things you'll need to be able to do is repeat an element. As you've already found, this functionality exists in Haskell in the form of the replicate function. But you can implement it yourself just as easily.

repeatNTimes :: Int -> a -> [a]
repeatNTimes 0 _ = []
repeatNTimes n x = x : repeatNTimes (n - 1) x

If we're repeating something zero times, return the empty list. Otherwise, put the element at the front and recurse.

Now we can repeat things. Let's write a function that keeps track of our list position. It'll look like this.

testImpl :: Int -> [a] -> [a]

It'll take an integer (the current position) and the tail of the list and return the result given that particular piece of the list. As before, we'll have two cases: one where the list is empty and one where it's not. The first case is simple; if the list is empty, return the empty list. If the list is nonempty, repeat the first element, and then recurse.

testImpl :: Int -> [a] -> [a]
testImpl _ [] = []
testImpl n (x:xs) = repeatNTimes n x ++ testImpl (n + 1) xs

++ is a built-in function which concatenates two lists. You could also implement that yourself if you really want to. Now, to start with, we consider the first element to be element 1, since we want to repeat it one time, so we'll begin the recursion by passing 1 to testImpl.

test :: [a] -> [a]
test = testImpl 1

Complete example:

repeatNTimes :: Int -> a -> [a]
repeatNTimes 0 _ = []
repeatNTimes n x = x : repeatNTimes (n - 1) x

testImpl :: Int -> [a] -> [a]
testImpl _ [] = []
testImpl n (x:xs) = repeatNTimes n x ++ testImpl (n + 1) xs

test :: [a] -> [a]
test = testImpl 1

Answer 2

List comprehensions to the rescue:

test xs = [x | (i,x) <- zip [1..] xs, _ <- [1..i]]

Unless of course you count zip among "prebuilt-list-functions", which you well might.