5
\$\begingroup\$

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?

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

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)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks!. This is interesting. It means given two lists m ++ n. Complexity = O(m) and not O(min(n,m)). \$\endgroup\$ – GeneralBecos Apr 3 '15 at 20:02
  • \$\begingroup\$ Yes that is exactly correct! \$\endgroup\$ – bisserlis Apr 3 '15 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.