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]
7. scala> unfoldRight(10) { x => if (x == 0) None else Some((x, x - 1)) }
8. res0: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
10. scala> unfoldRight("Jesse") { x => if (x.length == 0) None else Some((x, x.drop(1).toString)) }
11. res2: List[java.lang.String] = List(Jesse, esse, sse, se, e)
13. scala> def unfoldLeft[A, B](seed: B)(f: B => Option[(B, A)]) = {
14.      |   def loop(seed: B)(ls: List[A]): List[A] = f(seed) match {
15.      |     case Some((b, a)) => loop(b)(a :: ls)
16.      |     case None => ls
17.      |   }
18.      |
19.      |   loop(seed)(Nil)
20.      | }
21. unfoldLeft: [A,B](B)((B) => Option[(B, A)])List[A]
23. scala> unfoldLeft(1) { x => if (x == 11) None else Some((x + 1, x)) }
24. res0: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
26. // Notice that the result is ordered in the opposite way from unfoldRight
27. // Also notice the order of the list is reversed since the algorithm is the same but
28. // unfoldLeft adds to end of list.
29. scala> unfoldLeft("Jesse")  { x => if (x.length == 0) None else Some((x.drop(1).toString,x)) }
30. res1: List[java.lang.String] = List(e, se, sse, esse, Jesse)