Writing Data.List's intersperse

Question

Learn You a Haskell shows the intersperse function:

ghci> intersperse '.' "MONKEY"  
"M.O.N.K.E.Y"  
ghci> intersperse 0 [1,2,3,4,5,6]  
[1,0,2,0,3,0,4,0,5,0,6] 

Note that the interspersed element only appears inside of the elements.

list elem ... item ... list elem ..... item .. list elem

Originally, I tried to write this function in terms of a fold.

intersperse' :: [a] -> a -> [a]
intersperse' ys i = foldl (\acc x -> acc ++ [x] ++ [i]) [] ys

But, my approach failed since interspersed item was getting appended to the last element. Also, the lambda appended (++) to the acc each time, which isn't good.

So I decided to use pattern matching:

is' :: [a] -> a -> [a]
is' [] _ = []
is' (x:xs) i
  | null xs = [x]
  | otherwise = x : (i : (is' xs i))

Could the fold approach have worked? If so, how? Also, how's my is' implementation?

Answer 1

Could the fold approach have worked? If so, how?

intersperse' i = foldr (\x ys -> x : if null ys then [] else i : ys) []

In the fold, we cannot access the rest of the input, only the rest of the output. However, if and only if the input was empty, the output will be empty. So null ys happens to works here.

Interesting aspects:

1. I changed the argument order to match the standard intersperse. This happens to work better with the foldr-based definition. More importantely, I feel that intersperse is more often partially applied with an element than with a list, so the element should go first.

2. I use foldr instead of foldl to increase laziness and avoid the accumulator construction. Note how I don't need acc ++ [x] because I only add elements to the front of lists.

3. I make sure that intersperse' produces the first (:) cell before the null check.

Answer 2

Just include some "special handling" for the first element:

intersperse' x (y:zs) = y : foldr (\z acc -> x : z : acc) [] zs 

//or shorter 
intersperse' x (y:zs) = y : concat [[x,z] | z <- zs]

//or monadic madness
intersperse' x (y:ys) = y : (ys >>= (x:).return)