CODEWITHSUNDEEP
scala
ps0604
ps0604

Reputation: 1071

Building a list from tuples

I'm trying to solve problem 12 taken from here

To summarize, given a list of tuples:

List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))

the result should be a list containing each element in _2 repeated _1 times

The result would be List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)

This is my attempt (see code online)

object P12 extends App  {

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

    println(ls2)
    println(decode(ls2))   

    def decode[A] (list: List[(Int,A)]): List[A] = {
        list.foldLeft(List[A]()) { (result, elem) => for ( n <- 1 to elem._1) result :+ elem._2 }
    }

}

I get the following error:

Main.scala:9: error: type mismatch;
 found   : Unit
 required: List[A]
list.foldLeft(List[A]()) { (result, elem) => for ( n <- 1 to elem._1) result :+ elem._2 }

how to fix this?

Upvotes: 0

Views: 81

Answers (3)

elm
elm

Reputation: 20405

This recursive function denotes (or lists) the semantics concisely in two cases,

def decode( xs: List[(Int,Symbol)] ): List[Symbol] = xs match {
  case Nil => Nil
  case (x :: xss) => List.fill(x._1)(x._2) ++ decode(xss) 
}

An empty list results in an empty list, else for the head element of a non empty list, expand it into a list of repeated elements and prepend it to the rest of the decoded list.

Upvotes: 1

Aivean
Aivean

Reputation: 10882

Your for cycle does nothing, are you are using it in imperative way with immutable collection. On each iteration you create new collection from result with appended element and then just discard it. The result of your for is Unit, hence the error.

The correct functional way to perform your task is this:

def decode[A] (list: List[(Int,A)]): List[A] = {
  list.foldLeft(List[A]()) { case (result, (count, el)) =>
    result ::: (1 to count).map(_ => el).toList
  }
}

UPD: Also please note, that append operation on List takes linear time, so the whole decode becomes O(n2).

There is more efficient and concise way to perform your task, using flatMap:

def decode[A](list: List[(Int, A)]): List[A] =
  list.flatMap { case (count, el) => (1 to count).map(_ => el) }

Upvotes: 1

marcospereira
marcospereira

Reputation: 12214

Use List.fill and a flatMap:

val l = List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))
l.flatMap { t => List.fill(t._1)(t._2) }

Upvotes: 3

Related Questions