4

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)
TrebledJ
  • 8,713
  • 7
  • 26
  • 48
wwww
  • 99
  • 5
  • 1
    if it's lazy (in its list argument), it must only be right fold. `take 10 . intercalate [0] $ repeat [1..3]` must work, as does the original. – Will Ness Mar 24 '19 at 09:47

2 Answers2

6

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

TrebledJ
  • 8,713
  • 7
  • 26
  • 48
  • 1
    `foldr1` "accumulates from the right, and prepends values to the accumulator" ***only if*** the reducer function is strict. Here it processes the list left-to-right, splicing the recursive result (not "accumulator", so `r` or similar is the correct mnemonic, not `acc`) in-place on the fly. and left fold is ***absolutely the wrong tool here***, it destroys laziness: `take 10 . intercalate [0] $ repeat [1..3]` must work, as the original does. – Will Ness Mar 24 '19 at 09:55
  • @WillNess "only if the reducer function is strict" – Ah, so due to laziness, the result will end up being a whole chain of `elem0 ++ x ++ elem1 ++ x + elem2 ++ x ++ ... ++ x ++ elemN` and then that gets evaluated when it's needed? (Good catch, btw.) – TrebledJ Mar 24 '19 at 09:58
  • 1
    with the right fold, yes. and no, not even that: actually it will be `elem0 ++ x ++ (foldr (...) x [elem1....])`. it's a good mnemonic to write it like you did but it is even lazier than that. (you still have the wrong explanation there about `foldr` "accumulating" btw..., and the use of left fold must be discouraged much more strongly, IMO) – Will Ness Mar 24 '19 at 10:00
  • 1
    the `n` in `foldr g n xs` is *not* the initial term, but a final one, if `g` is not strict in its second argument. the `r` in `foldr` does not mean it folds ***from*** the right -- that is decided by the semantics of `g` alone. at the most we can say that foldr folds *on* the right or *to* the right. when `g` is lazy (like in this answer) "folds beginning from the last element" is wrong. Instead, it "folds ending on the last element". `foldr g n (x:xs) == g x (foldr g n xs)`, and that's that. – Will Ness Mar 24 '19 at 10:12
  • @WillNess Ach semantics. I guess I still have loads to learn. Thanks for eagerly evaluating my answer. :D – TrebledJ Mar 24 '19 at 10:25
  • 3
    I'm sorry to be pestering you, but: `foldl` does *not* "perform eager evaluation". in fact it's its major drawback that it isn't (`foldl'` does that, and should be used instead "almost always"). `foldl` does consume the input list eagerly though (and it doesn't evaluate the reducer functions chain that it builds until the whole list has been traversed). ---- yeah, you'll get there with time, and effort. :) – Will Ness Mar 24 '19 at 10:25
  • Haha, no worries. The precision is all good. Also makes for a good learning experience. – TrebledJ Mar 24 '19 at 10:29
1

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
Mateen Ulhaq
  • 24,552
  • 19
  • 101
  • 135