# Haskell: Efficient and clear list concatenation

I'm trying to write a function explodeBy:

explodeBy :: Int -> [Int] -> [Int]
explodeBy n arr = foldr (\x acc-> (take n.repeat) x ++ acc ) [] arr


This works as follows:

λ> explodeBy 2 [1,2,3]
[1,1,2,2,3,3]


The above uses list concatenation, so I tried writing a more efficient version:

explodeBy2 n arr = foldr (\x acc -> f n x acc) [] arr

f 0 _ rest = rest
f rep val rest = f  ( rep -1) val (val:rest)


Though this looks ugly, I expected it would work better. Reason: here we are using the (:) operator. Since rest is larger than (take n.repeat) x, I believe the second approach should have always been faster.

Surprisingly:

λ> sum $explodeBy2 500 [2..1001] 250750000 (0.48 secs, 199527400 bytes) λ> sum$ explodeBy 500 [2..1001]
250750000
(0.14 secs, 102259320 bytes)


explodeBy2 is consuming more time and memory!

Is there something wrong with this code or my understanding of (++)? Are there also any tips on how to write explodeBy better?

PS: This is where I got the impression ++ isn't efficient. Is this outdated?

• Chris Smith's answer on the question you linked might help clear up the efficiency issue. – Michael Shaw Apr 3 '15 at 20:05

GHCi is frequently significantly slower than compiled code even if you compile without any optimizations turned on, consider the timing information that GHCi gives you with great suspicion. Compile your code with -O2 and then time and the difference should largely disappear.

One of the nice things about the Haskell Prelude is that there is very little magic going on behind the scenes. Haskell lists use some privileged constructor names ((:) and []) but besides that they are a data type like any other. So let's peek behind the curtain and take a look at how (++) is defined.

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys


You should recognize the similarity to your function f. There is no way around the fact that growing a list by n elements takes n cons operations. When you want to add one element to the front of a list, you use (:) and that's it, you're done. When you want to add one element to the back of a list there's no constructor for that, you have to consider that element to be a new list of length one, and prepend your original list in front of it, causing you to have to walk down every single element of the original list. That is “slower” than the other case, but if the ordering of elements in your list is important you gotta do what you've gotta do, right?

Take some time to familiarize yourself with the functions available in Prelude and Data.List. There are many easier ways to write explodeBy.

As always, consider the types and use Hoogle. Looking at take n . repeat \$ x think about the type you would give that function on its own. n is an Int, and x is any type a. So you'd have a type like func :: Int -> a -> [a]. The first hit is for replicate, which does exactly what you want.

Next consider what easy intermediate values you can construct that get you closer to the result you want. The first step would be to replicate each element in the original list n times. That sounds like a job for map.

map (replicate n) xs :: [[a]]


Now we need :: [[a]] -> [a], which we could also search for. But this is of course list concatenation. There's one more trick you might not find by searching though, so here is when it comes in handy to have read through the documentation for Prelude. concatMap handles mapping and list concatenation in one go.

explodeBy :: Int -> [a] -> [a]
explodeBy n = concatMap (replicate n)

• Thanks!. This is interesting. It means given two lists m ++ n. Complexity = O(m) and not O(min(n,m)). – GeneralBecos Apr 3 '15 at 20:02
• Yes that is exactly correct! – bisserlis Apr 3 '15 at 22:00
• Is it not O(1) due to laziness? (I believe the answer is no, but I don't understand why?) – arya Nov 15 '20 at 17:31
• No, think of it this way. Laziness means that you pay for what you use when you need it. If you never use the result of a function, sure, you can consider calling it to have been a free operation. But when you actually use the result (say, finding the length m + 1th element of m ++ n) you still have to execute the list deconstruction and reconstruction steps of the (++) function. There are length m many of those plus the cost of finding the element at index length m + 1. Laziness only means the list extension instructions are executed near in time to the indexing instructions. – bisserlis Nov 21 '20 at 23:04