How to implement a custom tail recursive map for lists in Scala

Question

I want to implement a function called map that receives a list and a function and the yields the result of applying the function to each element of the input list. So I have this so far:

def map(list: List[Int], function: (Int) => Int): List[Int] = {
  def loop(list: List[Int], acc: List[Int]): List[Int] = {
    list match {
      case Nil => acc
      case head :: tail => loop(list.tail, function(head) :: acc)
    }
  }
  loop(list.reverse, Nil)
}

This code works and gives me the expected result, but I cannot help thinking there is a more elegant and efficient way that doesn't involve using reverse or another list method that isn't head or tail.

No, it is not. You had three options: 1) Two tail-recursive traverses over the list (what you did, however it is more common to reverse the list at the end). 2) Traverse the list once with a non-tail recursive function that can blow up your stack. 3) Use mutation and a standard while loop to achieve stack safety and only one traverse (that is what the implementation of the standard library does). - Well, you can also implement map in terms of other functions, like flatMap, foldLeft, foldRight. But, all of these converge to the previous three cases. — Luis Miguel Mejía Suárez
– Luis Miguel Mejía Suárez, Commented Apr 24, 2019 at 20:38

Mike Allen · Accepted Answer · 2019-04-25 03:55:28Z

As far as rolling your own implementation of a purely functional map function, without using any mutable state or built-in List higher-order functions, you've done a great job! Having to reverse the list does seem unnecessary, but it's worth it because prepending to a list is a very efficient operation.

As well as the other methods suggested in the comments, you could make acc a scala.collection.mutable.ListBuffer (which supports efficient append and prepend operations), then converting it to a list when you're done. However, the conversion process isn't a great improvement over reverse.

Otherwise, there are a few minor things you can do to improve your map function:

By using curried arguments, you can use map more elegantly.
Functions that need to be tail-recursive should always be decorated with the scala.annotation.tailrec attribute. The Scala compiler then knows your intention, and will issue an error if the function cannot be optimized to use tail recursion.
It's trivial to make this function generic, which will make it far more widely useful.
It's generally more idiomatic to perform the reverse operation on the result. It makes no difference for a map operation, but if you were to write a filter operation, for example, then it would be more efficient to reverse the potentially smaller set of filtered elements.

Here's how that would then look:

import scala.annotation.tailrec

def map[A, B](list: List[A])(function: (A) => B): List[B] = {

  @tailrec
  def loop(rem: List[A], acc: List[B]): List[B] = rem match {
    case Nil => acc.reverse
    case head :: tail => loop(tail, function(head) :: acc)
  }
  loop(list, Nil)
}

jwvh · Accepted Answer · 2019-04-24 22:25:50Z

4

Because head :: tail is the most efficient way to deconstruct and reconstruct a List, what you've done is a pretty common pattern. The .reverse is unfortunate but usually amounts to a minor performance penalty.

As mentioned in the comments, map can also be implemented via other Standard Library methods. Here it's done with foldRight:

def map(list :List[Int], function :Int => Int) :List[Int] = 
  list.foldRight(List.empty[Int])(function(_) :: _)

edited Apr 24, 2019 at 22:25

answered Apr 24, 2019 at 21:21

jwvh

51.3k7 gold badges42 silver badges70 bronze badges

Collectives™ on Stack Overflow

How to implement a custom tail recursive map for lists in Scala

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related