CODEWITHSUNDEEP
scalafunctional-programming
Santosh Gokak
Santosh Gokak

Reputation: 3411

Scala confusing compile time error while working with List of Tuples

I am working through Ninety-Nine Scala Problems to learn more Scala. I am on P12 and coded the below solution for the problem.

def decode(l : List[Tuple2[Int,Symbol]]) : List[Symbol] 
            = l foldLeft(List[Symbol]()) { (symbols:List[Symbol], e:Tuple2[Int, Symbol]) => symbols ::: List(e._2) }

And I am getting the below compiler error.

 error: type mismatch;
 found   : (List[Symbol], (Int, Symbol)) => List[Symbol]
 required: Int
                        = l foldLeft(List[Symbol]()) { (symbols:List[Symbol], e:
Tuple2[Int, Symbol]) => symbols ::: List(e._2) }

What is causing the compiler error?

Scala version: Scala code runner version 2.10.0-M3 -- Copyright 2002-2011, LAMP/EPFL.

Upvotes: 0

Views: 285

Answers (3)

kiritsuku
kiritsuku

Reputation: 53358

The solution is already given but I think there is a need for more explanation:

You are only allowed to leave parentheses and the dot if your expression is in operator position. An expression is in operator position if it has the form <object> <method> <param>. This is not the case with methods which contain multiple explicit parameter lists as foldLeft. Thus you have to write <list>.foldLeft(<init>)(<function>). Nevertheless Scala has a special rule to work around this - you can insert another set of parentheses: (<list> foldLeft <init>) (<function>). Furthermore there is another method called /: which is a synonym to foldLeft, defined as def /:[B](z: B)(op: (B, A) => B): B = foldLeft(z)(op). It allows you to write (<init> /: <list>) (<function>). Maybe you just noticed here that the symbols between the first parentheses are swapped - this is because of the rule that each method ending with a colon is right- instead of left-associative (further explanation).

Now I want to give you some hints for further refactorings:

  • Tuple2[A, B] can be written as (A, B)
  • You don't have to write all the types. Some of them can - and should - be left to clear up your code (I know you are a beginner and want to write this. Only as a hint...). But don't leave
  • Lists are mostly named something like xs or ys because this means "lots of x" or "lots of y". This is not very important but common
  • You can patter match on parameters to extract them to easy to read names: ... { case (a, (b,c)) => ...}
  • Your code does not work as it claims the task. You need something like List.fill(<n>)(<elem>)
  • Don't append elements to a list, this is O(n). ::: implicitly is a append operation - look at the sources.
  • For this task foldLeft is not be best solution to come up with. foldRight or the synonym :\ may be more efficient because the ::: operation requires less elements to copy. But I prefer flatMap (see below), which is a map+flatten
    • You can use a for-comprehension to solve this, which often will be easy to read. See this for more information how for-comprehensions are realized internally.

All in all the example solutions:

object Test extends App {
  def decode1(l: List[Tuple2[Int, Symbol]]): List[Symbol] =
    l.foldLeft(List[Symbol]()) { (symbols: List[Symbol], e: Tuple2[Int, Symbol]) => symbols ::: List.fill(e._1)(e._2) }

  def decode2(xs: List[(Int, Symbol)]): List[Symbol] =
    (xs foldLeft List.empty[Symbol]) { case (xs, (n, s)) => xs ::: List.fill(n)(s) }

  def decode3(xs: List[(Int, Symbol)]): List[Symbol] =
    (xs foldRight List.empty[Symbol]) { case ((n, s), xs) => List.fill(n)(s) ::: xs }

  def decode4(xs: List[(Int, Symbol)]): List[Symbol] =
    (List.empty[Symbol] /: xs) { case (xs, (n, s)) => xs ::: List.fill(n)(s) }

  def decode5(xs: List[(Int, Symbol)]): List[Symbol] =
    xs flatMap { case (n, s) => List.fill(n)(s) }

  def decode6(xs: List[(Int, Symbol)]): List[Symbol] =
    for {
      (n, s) <- xs
      ys <- List.fill(n)(s)
    } yield ys

  val xs = List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))
  val ys = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)

  println("start testing")

  val tests = List[List[(Int, Symbol)] => List[Symbol]](decode1, decode2, decode3, decode4, decode5, decode6)

  for (t <- tests)
    assert(t(xs) == ys)

  println("finished")
}

Upvotes: 3

Malte Schwerhoff
Malte Schwerhoff

Reputation: 12852

If you make the call to foldLeft explicit by using l.foldLeft, then the error disappears:

def decode(l: List[Tuple2[Int,Symbol]]): List[Symbol] =
  l.foldLeft(List[Symbol]()){(symbols:List[Symbol], e:Tuple2[Int, Symbol]) =>
      symbols ::: List(e._2)}

Have a look at the first answer of to this question for a very detailed explanation of Scala's call syntax that also covers your case.

Upvotes: 1

Sean Parsons
Sean Parsons

Reputation: 2832

It looks like it's your use of the infix foldLeft call, you just need to change it to:

def decode(l : List[Tuple2[Int,Symbol]]) : List[Symbol] 
        = l.foldLeft(List[Symbol]()) { (symbols:List[Symbol], e:Tuple2[Int, Symbol]) => symbols ::: List(e._2) }

Note the "l.foldLeft" rather than "l foldLeft", I suspect the compiler can't quite determine what is a parameter to what.

Upvotes: 4

Related Questions