Tuesday, September 22, 2009

UnfoldLeft and Right

Todays topic does not introduce anything new, it just a useful example of using a function to create a list of objects. This is NOT part of the standard library.

The methods are called unfoldRight and unfoldLeft because they are more or less the inverse of foldLeft and foldRight. foldLeft and Right run a function on each element in a list producing some result. unfoldLeft and right produce a list from a function and a seed value. The List is created from executing the function repeatedly with the result from the previous execution (or the seed value). Each function call returns a result which is the element in the list. The list is done when the function returns None rather than Some(x).

This sample is directly derived from the samples: http://paste.pocoo.org/show/140865/

Remember the performance differences between the two. Adding an element to the head of scala list is a constant operation but adding an element to the end(tail) of the list is linear time based on the size of the list. So unfoldLeft will typically suffer from worse performance.
  1. scala> def unfoldRight[A, B](seed: B)(f: B => Option[(A, B)]): List[A] = f(seed) match {
  2.      |   case Some((a, b)) => a :: unfoldRight(b)(f)
  3.      |   case None => Nil
  4.      | }
  5. unfoldRight: [A,B](B)((B) => Option[(A, B)])List[A]
  6. scala> unfoldRight(10) { x => if (x == 0) None else Some((x, x - 1)) }
  7. res0: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
  8. scala> unfoldRight("Jesse") { x => if (x.length == 0) None else Some((x, x.drop(1).toString)) }
  9. res2: List[java.lang.String] = List(Jesse, esse, sse, se, e)
  10. scala> def unfoldLeft[A, B](seed: B)(f: B => Option[(B, A)]) = {
  11.      |   def loop(seed: B)(ls: List[A]): List[A] = f(seed) match {
  12.      |     case Some((b, a)) => loop(b)(a :: ls)
  13.      |     case None => ls
  14.      |   }
  15.      |
  16.      |   loop(seed)(Nil)
  17.      | }
  18. unfoldLeft: [A,B](B)((B) => Option[(B, A)])List[A]
  19. scala> unfoldLeft(1) { x => if (x == 11) None else Some((x + 1, x)) }
  20. res0: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
  21. // Notice that the result is ordered in the opposite way from unfoldRight
  22. // Also notice the order of the list is reversed since the algorithm is the same but
  23. // unfoldLeft adds to end of list.
  24. scala> unfoldLeft("Jesse")  { x => if (x.length == 0) None else Some((x.drop(1).toString,x)) }
  25. res1: List[java.lang.String] = List(e, se, sse, esse, Jesse)

4 comments:

  1. unfoldLeft looks to be implemented without adding an element to the end of a list. It looks pretty efficient. unfoldRight can blow the stack

    ReplyDelete
  2. Shouldn't unfoldRight construct the list from right to left? They seem reversed to me.

    ReplyDelete
  3. The name is ambiguous. When I wrote this post I viewed it as the resulting list flows left to right with regard to the elements coming from the function in the same way a stream flows.

    But I certainly understand where you are coming from and if I wrote it now I might have written it in that fashion as well.

    ReplyDelete
  4. @steshaw. Neither example is ideal but unfoldRight could be rewritten to be tail recursive.

    ReplyDelete