Insert function using foldl/foldr

Question

I have been working on a separate function that returns a list that inserts element x after each k elements of list l (counting from the end of the list). For example, separate (1, 0, [1,2,3,4]) should return [1,0,2,0,3,0,4]. I finished the function and have it working as follows:

fun separate (k: int, x: 'a, l: 'a list) : 'a list = 
  let
    fun kinsert [] _ = []
      | kinsert ls 0 = x::(kinsert ls k)
      | kinsert (l::ls) i = l::(kinsert ls (i-1))
  in
     List.rev (kinsert (List.rev l) k)
  end 

Im now trying to simplify the function using foldl/foldr without any recursion, but I cant seem to get it working right. Any tips/suggestions on how to approach this? Thank You!

Answer 1

These are more or less the thoughts I had when trying to write the function using foldl/foldr:

• foldl/foldr abstracts away the list recursion from the logic that composes the end result.

• Start by sketching out a function that has a much similar structure to your original program, but where foldr is used and kinsert instead of being a recursive function is the function given to foldr:

  fun separate (k, x, L) =
      let fun kinsert (y, ys) = ...
      in foldr kinsert [] L
      end
  

  This isn't strictly necessary; kinsert might as well be anonymous.

• You're using an inner helper function kinsert because you need a copy of k (i) that you gradually decrement and reset to k every time it reaches 0. So while the list that kinsert spits out is equivalent to the fold's accumulated variable, i is temporarily accumulated (and occasionally reset) in much the same way.

• Change kinsert's accumulating variable to make room for i:

  fun separate (k, x, L) =
      let fun kinsert (y, (i, xs)) = ...
      in foldr kinsert (?, []) L
      end
  

  Now the result of the fold becomes 'a * 'a list, which causes two problems: 1) We only really wanted to accumulate i temporarily, but it's part of the final result. This can be circumvented by discarding it using #2 (foldr ...). 2) If the result is now a tuple, I'm not sure what to put as the first i in place of ?.

• Since kinsert is a separate function declaration, you can use pattern matching and multiple function bodies:

  fun separate (k, x, L) =
      let fun kinsert (y, (0, ys)) = ...
            | kinsert (y, (i, ys)) = ...
      in ... foldr kinsert ... L
      end
  

• Your original kinsert deviates from the recursion pattern that a fold performs in one way: In the middle pattern, when i matches 0, you're not chopping an element off ls, which a fold would otherwise force you to. So your 0 case will look slightly different from the original; you'll probably run into an off-by-one error.

• Remember that foldr actually visits the last element in the list first, at which point i will have its initial value, where with the original kinsert, the initial value for i will be when you're at the first element.

• Depending on whether you use foldl or foldr you'll run into different problems: foldl will reverse your list, but address items in the right order. foldr will keep the list order correct, but create a different result when k does not divide the length of L...

• At this point, consider using foldl and reverse the list instead:

  fun separate (k, x, L) =
      let fun kinsert (y, (?, ys)) = ...
            | kinsert (y, (i, ys)) = ...
      in rev (... foldl kinsert ... L)
      end
  

  Otherwise you'll start to notice that separate (2, 0, [1,2,3,4,5]) should probably give [1,2,0,3,4,0,5] and not [1,0,2,3,0,5].