Mapping over sublists in Scala

Question

I know that the map function takes each element of a list (a sequence) and applies a function to it. Recursively (and without respect to termination conditions, etc)

map(s, f) = f(s.head) :: map(s.tail, f)

I am looking for a function that does something like

foo(s, f) = f(s) :: map(s.tail, f).

So a 'mapper' where the mapping function gets called on sublists and not individual elements. In lisp terms, I'm looking for a maplist, as opposed to a mapcar. Does something like this exist, or do I have to roll my own (or use recursion)?

Alternatively, I'd take a function that takes as input a sequence and returns a sequence of mid-to-end subsequences, ie

bar(s, f) = s :: bar(s.tail, f)

Schacker

Can you give an example of the desired input and output? I'm having trouble following. – Lazos

I don't know answer to this question, but if you have a need for advanced types and functions, see Scalaz library: code.google.com/p/scalaz – Longeron

Answer 1

/* This approach defines mapList in terms of another useful method called tails. Like Daniel, I'll put it in an implicit extension to List, but that's purely a matter of taste */

implicit def richerList[A](list : List[A]) = new {

/* Here's a method called tails which returns each possible tail in the list. It is tail recursive so it won't blow up on large lists. Note that it differs slightly from a Haskell function of the same name. The Haskell version always adds an empty list on to the result */

  def tails : List[List[A]] = {
    def loop(ls : List[A], accum : List[List[A]]) : List[List[A]] = ls match {
      case _ :: tail => loop(tail, ls :: accum)
      case _ => accum
    }

    loop(list, Nil).reverse
  }

/* This is what using tails looks like

scala> "abc".toList.tails
res0: List[List[Char]] = List(List(a, b, c), List(b, c), List(c))

*/

/* Now we can define mapList based on tails */

  def mapList[B](f : List[A] => B) = tails map f
}

/* And this is what using mapList looks like

scala> "abc".toList mapList (_.reverse.mkString)
res1: List[String] = List(cba, cb, c)

*/

Eldaelden

Answer 2

You've basically defined what you're looking for in pseudocode - so it's easy to add such a method to a Scala list using implicit conversions:

object ExtendedList{
  implicit def List2ExtendedList[A](l:List[A])=new ExtendedList(l)
}
class ExtendedList[A](l:List[A]){
  import ExtendedList._
  def mapList[B](f:List[A]=>B):List[B]=l.length match {
    case 0 => List()
    case _ => f(l)::l.tail.mapList(f)
  }
}

object Test extends Application{
  import ExtendedList._
  val test = List(5,4,3,2,1)
  assert(List(15,10,6,3,1)==test.mapList{l=>(0/:l){_+_}})
}

Is this what you're looking for?

Curlicue

It's O(n) to get the length of a list and your mapList does it n times, for O(n^2) cost. Run this on a large list and you'll be waiting awhile :-) – Eldaelden

The reason I asked is that I'm new to Scala and wanted to know if there was a built-in canonical function (to make my code more readable to others). Alternatively, I wanted to hear "don't do that, the scala way of doing it is ___" – Schacker

Yup, I acknowledge using .length is bad - should have thought about it more! – Curlicue

Answer 3

The other answer is close, but you should never use List#length unless absolutely necessary. In particular, it makes his solution O(n^2) when the problem is inherantly O(n). Here's a cleaned-up version:

implicit def addListSyntax[A](list: List[A]) = new {
  def mapList[B](f: List[A]=>B) = {
    // use inner function to avoid repeated conversions
    def loop(list: List[A]): List[B] = list match {
      case ls @ (_ :: tail) => f(ls) :: loop(tail)
      case Nil => Nil
    }

    loop(list)
  }
}

And, to answer your original question: no, there is no way to do this using standard utility methods. I'm actually a bit curious as to why you would want something like this...

Corkwood

Be careful here since this version is not tail recursive. Large lists will cause stack explosion. – Eldaelden

Indeed, that's a huge mistake. – Longeron

I have a list of sorted timestamps, and I need to map over things like - each timestamp and the y prior timestamps - each timestamp, together with all the timestamps for x minutes preceding it. Again, I know exactly how to code it up in multiple ways (by defining my own mapList, imperatively, using map and then filter inside to generate history, etc) but I wanted to find out how to do this cleanly and the Scala way. – Schacker