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?

Incestuous

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

Lilililia

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.

Mimeograph

You could implement zip too. – Swen

Answer 3

In that case, we usually use an accumulator. An accumulator is an extra parameter that we pass (and update) to reach our goal. We thus can implement a function test' with two parameters: a list l, and an index i, and we define it as follows:

1. in case the list is empty, we return an empty list; and
2. in case the list is not empty, we yield the head of the list i times, and recurse on the tail of the list and an incremented i.

We can implement this like:

test' :: Int -> [a] -> [a]
test' _ [] = []
test' i (x:xs) = rep i
    where rep j | j > 0 = x : rep (j-1)
                | otherwise = test' (i+1) xs

So now we only need to define test in terms of test', here we can say that test with a list l is the same as test' with that list, and 1 as start index:

test :: [a] -> [a]
test = test' 1
    where test' _ [] = []
          test' i (x:xs) = rep i
              where rep j | j > 0 = x : rep (j-1)
                          | otherwise = test' (i+1) xs

We then obtain test results like:

Prelude> test ['1'..'3']
"122333"
Prelude> test [1..3]
[1,2,2,3,3,3]
Prelude> test [1, 4, 2, 5]
[1,4,4,2,2,2,5,5,5,5]
Prelude> test "ia2b"
"iaa222bbbb"

Leman

Answer 4

You can do this without any numbers. Let's work our way up to it. We'll use the accumulator approach, but instead of keeping a number in the accumulator, we'll keep a function that repeats its argument a certain number of times.

test0 :: [a] -> [a]
test0 xs = go rep1 xs
  where
    rep1 :: a -> [a]
    rep1 a = [a]

    go :: (a -> [a]) -> [a] -> [a]
    go _rep [] = []
    go rep (a : as) = rep a ++ go (oneMore rep) as

    oneMore :: (a -> [a]) -> (a -> [a])
    oneMore rep a = a : rep a

We start off calling go with rep1, a really simple function that turns its argument into a singleton list. Then on each recursive call, we modify the repeater function by making it repeat its argument one more time.

test0 works just fine, but it uses the ++ function, and you're not supposed to be using any predefined functions. Using ++ here also means that you have to build up the small lists and put them together, an inefficiency we can remove pretty easily.

Note that every time go calls rep, it immediately appends something else to the result. This suggests the solution: instead of having rep take an element and produce a list, let's have it take an element and a list, and produce a list consisting of the element repeated a certain number of times followed by the given list! So we'll have

rep1 "a" ["b", "c"] = ["a", "b", "c"]
rep2 "a" ["b", "c"] = ["a", "a", "b", "c"]

where rep1 and rep2 are the first two rep functions. Just a few adjustments are needed.

test :: [a] -> [a]
test = go rep1
  where
    rep1 :: a -> [a] -> [a]
    rep1 a as = a : as  -- Note: rep1 can be written as just (:)

    go :: (a -> [a] -> [a]) -> [a] -> [a]
    go _ [] = []
    go rep (a : as) = rep a (go (oneMore rep) as)

    oneMore :: (a -> [a] -> [a])
            -> a -> [a] -> [a]
    oneMore f a as = a : f a as

This really isn't an efficient way to solve the problem, but it's a rather minimalist approach.

Antrum

very nice idea; if we start with the last definition, it practically dictates the oneMore cons a as = a : cons a as definition. – Mimeograph

@WillNess, I struggled a bit with presentation here. Please feel free to edit if you think you can do better. Also, for myself I'd use RankNTypes to explain what's not going on a little better, but the OP would then be quite lost. – Antrum

@WillNess, I'm not sure that really helps; I personally find it confusing and opaque. After pondering some more, I'm thinking the way to start is with a version of test that uses oneMore0 and ++, then show how to eliminate the latter. I'll try to work that up later unless you get to it first – Antrum

btw the trivial tracing of a data structure as a starting point is a technique from Sterling and Shapiro old Prolog book. they call it "program skeleton". – Mimeograph

@WillNess, I reverted your change because I couldn't work out how to integrate it into the structure I decided I wanted. But if you can motivate your technique a bit better, I think you should write your own answer. Thanks for prodding me to improve my explanation. – Antrum

of course, it was too different an approach. about the derivation, good starting point! it is also possible to say that rep a ++ go (oneMore rep) as = ((++).rep) a (go ...) which practically forces us to give the fused rep1' = (++).rep1 definition, and the correspondingly changed oneMore' rep1' a as = ... which must be of the same type as rep1', which again practically writes itself. Just saying "few adjustments needed" is not explaining much. just a thought. – Mimeograph

Let us continue this discussion in chat. – Antrum

Answer 5

Enumerations can produce ordinal numbers given a cardinal number. Indices are ordinal numbers. What this means is the digit in list a is the end number in the enumeration. Each index set (cardinal number set from ordinals) is [0..index]the first, actually zero is [0..1]. If we wanted to us ordinals it would be [1..1], then [1..2] and [1..3] But the function uses zero index out of habit and the cardinal number must be decrimented.

[b|b<-[1,2,3], a<-[0..b-1]]

Enumeration parameters are very much fun. Enumerations can be used as index parameters to other lists of any type. Enumerations can supply parameters to other functions and other enumerations.

Holdup