Elegant way to reverse a list using foldRight?

Question

I was reading about fold techniques in Programming in Scala book and came across this snippet:

def reverseLeft[T](xs:List[T]) = (List[T]() /: xs) {
    (y,ys) => ys :: y
}

As you can see, it was done using foldLeft or /: operator. Curious how it would look like if I did it using :\, I came up with this:

def reverseRight[T](xs:List[T]) = (xs :\ List[T]()) {
    (y,ys) => ys ::: List(y)
}

As I understand it, ::: doesn't seem to be as fast as :: and has a linear cost depending on the size of the operand list. Admittedly, I don't have a background in CS and no prior FP experience. So my questions are:

• How do you recognise/distinguish between foldLeft/foldRight in problem approaches?
• Is there a better way of doing this without using :::?

Answer 1

Since foldRight on List in the standard library is strict and implemented using linear recursion, you should avoid using it, as a rule. An iterative implementation of foldRight would be as follows:

def foldRight[A,B](f: (A, B) => B, z: B, xs: List[A]) =
  xs.reverse.foldLeft(z)((x, y) => f(y, x))

A recursive implementation of foldLeft could be this:

def foldLeft[A,B](f: (B, A) => B, z: B, xs: List[A]) =
  xs.reverse.foldRight(z)((x, y) => f(y, x))

So you see, if both are strict, then one or the other of foldRight and foldLeft is going to be implemented (conceptually anyway) with reverse. Since the way lists are constructed with :: associates to the right, the straightforward iterative fold is going to be foldLeft, and foldRight is simply "reverse then foldLeft".

Intuitively, you might think that this would be a slow implementation of foldRight, since it folds the list twice. But:

1. "Twice" is a constant factor anyway, so it's asymptotically equivalent to folding once.
2. You have to go over the list twice anyway. Once to push computations onto the stack and again to pop them off the stack.
3. The implementation of foldRight above is faster than the one in the standard library.

Answer 2

Operations on a List are intentionally not symmetric. The List data structure is a singly-linked list where each node (both data and pointer) are immutable. The idea behind this data structure is that you perform modifications on the front of the list by taking references to internal nodes and adding new nodes that point to them -- different versions of the list will share the same nodes for the end of the list.

The ::: operator which appends a new element on to the end of the list has to create a new copy of the entire list, because otherwise it would modify other lists that share nodes with the list you're appending to. This is why ::: takes linear time. Scala has a data structure called a ListBuffer that you can use instead of the ::: operator to make appending to the end of a list faster. Basically, you create a new ListBuffer and it starts with an empty list. The ListBuffer maintains a list completely separate from any other list that the program knows about, so it's safe to modify it by adding on to the end. When you're finished adding on to the end, you call ListBuffer.toList, which releases the list into the world, at which point you can no longer add on to the end without copying it.

foldLeft and foldRight also share a similar assymmetry. foldRight requires you to walk the entire list to get to the end of the list, and keep track of everywhere you've visited on the way there, so that you an visit them in reverse order. This is usually done recursively, and it can lead to foldRight causing stack overflows on large lists. foldLeft on the other hand, deals with nodes in the order they appear in the list, so it can forget the ones it's visited already and only needs to know about one node at a time. Though foldLeft is also usually implemented recursively, it can take advantage of an optimization called tail recursion elimination, in which the compiler transforms the recursive calls into a loop because the function doesn't do anything after returning from the recursive call. Thus, foldLeft doesn't overflow the stack even on very long lists. EDIT: foldRight in Scala 2.8 is actually implemented by reversing the list and running foldLeft on the reversed list -- so the tail recursion issue is not an issue -- both data structures optimize tail recursion correctly, and you could choose either one (You do get into the issue now that you're defining reverse in terms of reverse -- you don't need to worry if you're defining your own reverse method for the fun of it, but you wouldn't have the foldRight option at all if you were defining Scala's reverse method.)

Thus, you should prefer foldLeft and :: over foldRight and :::.

(In an algorithm that would combine foldLeft with ::: or foldRight with ::, then you need to make a decision for yourself about which is more important: stack space or running time. Or you should use foldLeft with a ListBuffer.)