Intercalate using fold

Question

Can someone explain me how to write the intercalate function using fold? Additionally, I've heard of foldr or foldl; which of these is the most appropriate to use in this context?

Here's my attempt with recursion:

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

Answer 1

Using foldr1:

intercalate' :: [a] -> [[a]] -> [a]
intercalate' _ [] = []
intercalate' x xs = foldr1 (\a acc -> a ++ x ++ acc) xs

This will intercalate values from the right with x between each element. (Albeit it does this lazily. – The entire fold isn't evaluated until needed.)

Both foldr1 and foldr are similar in that they fold from the right. The difference lies in that the former doesn't require us to provide a final term while the latter does require a final term to be provided. This requires us to pattern match for the empty list, otherwise an exception would be thrown.

Indeed, foldl1 can also accomplish intercalation. However, this is strongly discouraged as the left fold will consume input eagerly.

intercalate' :: [a] -> [[a]] -> [a]
intercalate' _ [] = []
intercalate' x xs = foldl1 (\acc a -> acc ++ x ++ a) xs

---

To further emphasise the preference over the right fold, consider the following composition:

take 10 . intercalate' [0] $ repeat [1..3]

Looks harmless. But using foldl1 will eagerly consume the infinite list, not stopping the process.

However, using foldr1 will evaluate lazily and give the correct result of [1,2,3,0,1,2,3,0,1,2]. (intercalate' will temporarily evaluate [1..3] ++ [0] ++ (foldr (...) [0] [elem1 ... elemN]) before take 10 asks for the leading terms and evaluates the fold.)

Kudos to Will.

Useful Reading:
foldl versus foldr behaviour with infinite lists

Answer 2

Let's remind ourselves about the signature of foldl:

foldl :: (b -> a -> b) -> b -> t a -> b

A simple rewrite of what you wrote:

intercalate :: [a] -> [[a]] -> [a]
intercalate s [] = []
intercalate s [x] = x
intercalate s (x:xs) = foldl (\acc y -> acc ++ s ++ y) x xs