Work on list of tuples in Scala - part 3

Question

I'm new to Scala, and trying to understand how to work on lists of tuples, so I've created a fictive list of people:

val fichier : List[(String, Int)] = List(("Emma Jacobs",21), ("Mabelle Bradley",53), ("Mable Burton",47), ("Ronnie Walton",41), ("Bill Morton",36), ("Georgia Bates",30), ("Jesse Caldwell",46), ("Jeffery Wolfe",50), ("Roy Norris",18), ("Ella Gonzalez",48))

I'm trying to isolate people who got even ages:

  def separate(list: List[(String, Int)]) : List[(String, Int)] =//(List[(String, Int)] , List[(String, Int)]) =
list match {
 case (name, age)::t if age%2==0 => {(name, age)::separate(t)}
 case (name, age)::t if age%2!=0 => Nil
 }

The result is an empty list.

What am I doing wrong?

NB: I'm trying to write my own function that does the job, not to use scala pre existing methods

Answer 1

In practice, I would suggest filter too, because it is more compact, without being cryptic.

fichier.filter {case (name, age) => (age %2 == 0)}

since name isn't used on the RHS (right hand side, most of the time: right of the equal sign, here: right to the case expression)), we can indicate that:

fichier.filter {case (_, age) => (age %2 == 0)}

more compact is using the positional value, but it is less self documenting. In contrast to every other element with position, like List, Vector, String ..., counting starts here at 1, not 0.

fichier.filter (_._2 %2 == 0)

However, your exercise, you mentioned, was, to implement it yourself, which is a reasonable learning procedure. So why not implement filter yourself, once and for all?

Let's start concrete, only filtering touples with second element int, for example.

Stop reading, and first try yourself.

What is that filter thingy in this context?

 fichier.filter {case (name, age) => (age %2 == 0)}

It operates on a List of heterogenous tuples, but we don't like start by Adam and Eve for now, so let's take List as an additional parameter. Writing a basic List implementation wouldn't be too hard too, but for now ... . We start with a specific tuple, and make it stepwise more general. The list is a List of tuples, the function takes an Int and returns a Boolean. A function, which takes an Int and returns a Boolean looks like this: f: (Int => Boolean))

scala> def tfilter (tl: List [(String, Int)], f: (Int => Boolean)) : List[(String, Int)] = tl match {
     |     case Nil => Nil
     |     case t :: tt => if (f (t._2)) t :: tfilter (tt, f) else tfilter (tt, f) 
     | }
tfilter: (tl: List[(String, Int)], f: Int => Boolean)List[(String, Int)]

The method is somehow pretty empty. It takes List, takes the first element t, tests it with f(t._2) (we know the second part of the tuple is an Int, and the function returns true or false for a given Int. If true, return the element and the rest of the list, tt, filtered by the same means. Therefor we have to pass the function along.

Invocation:

scala> tfilter (fichier, (_ % 2 == 0))
res107: List[(String, Int)] = List((Bill Morton,36), (Georgia Bates,30), (Jesse Caldwell,46), (Jeffery Wolfe,50), (Roy Norris,18), (Ella Gonzalez,48))

The inner parenthesis define our function. It is a placeholder, to be filled by the function, since it is called by an parameter, and returns whether the modulo 2 on that value equals to 0. Here are two notation variations.

tfilter (fichier, (i:Int => i % 2 != 0))
tfilter (fichier, ((i:Int) => i % 2 != 0))

But what, if our next tuple is the other way round, and has int in the second position? Position 1 is hard coded in our method, which is a bad thing.

Again, try yourself first. Changing the Sequence of Parameters is complicated. We better go instantly in parametrizing the Type we expect, and in consequence, what we return, and hence, what the predicate, the function which returns a Boolean expects.

We just name, what has been a tuple (String, Int), to X:

scala> def tfilter (tl: List [X], f: (X => Boolean)) : List[X] = tl match {
     |     case Nil => Nil
     |     case t :: tt => if (f (t)) t :: tfilter (tt, f) else tfilter (tt, f) 
     | }
<console>:8: error: not found: type X
       def tfilter (tl: List [X], f: (X => Boolean)) : List[X] = tl match {
                                                            ^

3 Changes in the header, and one on the test f(t). But the REPL is not happy.

We have to Type annotate the whole method:

scala> def tfilter [X] (tl: List [X], f: (X => Boolean)) : List[X] = tl match {
     |     case Nil => Nil
     |     case t :: tt => if (f (t)) t :: tfilter (tt, f) else tfilter (tt, f) 
     | }
tfilter: [X](tl: List[X], f: X => Boolean)List[X]

Now the REPL is happy. Whatever X is, we promise to pass a List of X and a method, which can transform a single X into a boolean, and we will return a List of X.

We can now go in small steps. Write a method, which takes a tuple and a function Int => Boolean, and performs the function on the Int part, here part 2, of the tuple:

def tuple2bool (si: (String, Int), f: (Int => Boolean)) : Boolean = f (si._2)

Very trivial, the unused notation aside. Tiny test for a single tuple:

tuple2bool (fichier(0), (i:Int) => (i % 2 == 0))
Boolean = false

tuple2bool (fichier(5), (i:Int) => (i % 2 == 0))
Boolean = true

How can we invoke it on the whole list? Well, first we introduce the concept of two paramter lists.

def (a: Int, b:Int, c:Int) = ... 

is pretty much the same as

def (a: Int) (b:Int, c:Int) = ... 

The function can operate on a, b, c inside. However, for implicits it is only possible to have a whole parameterlist implicit, so if we want to have only some elements implicit, we group them into an own parameterlist. For the compiler and coder, it is more easy to figure out, what is left out. Here, for me, it is more easy too, to separate List and function call in different parameter lists:

def tfilter [X] (tl: List [X]) (f: (X => Boolean)) : List[X] = tl match {
    case Nil => Nil
    case t :: tt => if (f (t)) t :: tfilter (tt)(f) else tfilter (tt)(f) 
}

It's a bit scary, to have function calls with two parameter lists, but either you do it rarely, or you get used to it fast. Now, let's call our

tfilter (fichier) (si => tuple2bool (si, _ % 2 == 0 ))
List[(String, Int)] = List((Bill Morton,36), (Georgia Bates,30), (Jesse Caldwell,46), (Jeffery Wolfe,50), (Roy Norris,18), (Ella Gonzalez,48))

The first parameter is our fichier, the second a function, which takes an si, an identifier to bind our tuple2bool param 1, and then the function to perform on the Int, which will be extracted. _ is the placeholder for that unbound Int.

But we don't want to write such intermediate functions over and over again. We can immediately write:

 tfilter (fichier) (si => (si._2 % 2 == 0 ))
 List[(String, Int)] = List((Bill Morton,36), (Georgia Bates,30), (Jesse Caldwell,46), (Jeffery Wolfe,50), (Roy Norris,18), (Ella Gonzalez,48))

and forget the tuple2bool-fun altogether.

And we are super flexible now. If we decide, to write a class Personne, and change order age/name:

val personnes: List [Personne] = List (Personne(21, "Emma Jacobs"), Personne(54, "Mabelle Bradley")) 
personnes: List[Personne] = List(Personne(21,Emma Jacobs), Personne(54,Mabelle Bradley))

tfilter (personnes) (p => (p.age % 2 == 0 ))
List[Personne] = List(Personne(54,Mabelle Bradley))

I reduced the list for smaller results and varied the age of Mabelle, to have a real effect on filtering.

We can not only filter with int functions now:

tfilter (personnes) (p => (p.name.contains ('a')))
List[Personne] = List(Personne(21,Emma Jacobs), Personne(54,Mabelle Bradley))

with fichier, it works the same way:

tfilter (fichier) (p => (p._1.contains ('a')))

And we can nest our function, to pass the tuples through a second filter:

tfilter (tfilter (fichier) (p => (p._1.contains ('a'))))(p => p._2 < 30)
List[(String, Int)] = List((Emma Jacobs,21))

The original, sequential style in the scala libs, is surely more elegant, better to parse for us coders, mainly: 

fichier.filter (p => (p._1.contains ('a'))).filter (p => p._2 < 30)

At least, we can adopt the syntax, introduced before, with 'case':

tfilter (fichier)({case (name, _) => (name.length > 13)})

Answer 2

You have an incomplete function, because when the age is odd, it is terminating, but it should traverse further in the list.

Try this:

def separate(list: List[(String, Int)]) : List[(String, Int)] = list match {
    case (name, age)::t if age%2==0 => (name, age)::separate(t)
    case (name, age)::t if age%2!=0 => separate(t)
    case Nil => Nil
}

No need to add this "(name, age)::separate(t)" in curly braces.

Answer 3

My question is: why does it find Unit and not a List?

Because

val liste = (name, age)::separate(t)

is an assignment. An assignment has a return type of unit, if you want to return that value go ahead and do

case (name, age)::t if age%2==0 => {(name, age)::separate(t)}

As a way to get the even aged people, I'd suggest you use collect. So,

val fichier : List[(String, Int)] = List(("Emma Jacobs",21), ("Mabelle Bradley",53), ("Mable Burton",47), ("Ronnie Walton",41), ("Bill Morton",36), ("Georgia Bates",30), ("Jesse Caldwell",46), ("Jeffery Wolfe",50), ("Roy Norris",18), ("Ella Gonzalez",48))

fichier.collect {
   case (name, age) if age % 2 == 0 => (name, age)
}

Or you can use filter to avoid having to state your tuple again:

fichier.filter(_._2 % 2 == 0)
res1: List[(String, Int)] = List((Bill Morton,36), (Georgia Bates,30), (Jesse Caldwell,46), (Jeffery Wolfe,50), (Roy Norris,18), (Ella Gonzalez,48))

What am I doing wrong?

The other thing Im seeing wrong here and why you're getting an empty list is that you're matching against the entire list itself. So when you do

list match {
 case (name, age)::t if age%2==0 => {val liste = (name, age)::separate(t)}
 case (name, age)::t if age%2!=0 => Nil
 }

The (name, age) is only the head of your list. So that's Emma Jacobs, 21. So the match falls into the second case and you get an empty list because you don't call separate(t) to continue the recursion. However, if you try to do this without any other change you'll get an error:

scala>  def separate(list: List[(String, Int)]) : List[(String, Int)] =//(List[(String, Int)] , List[(String, Int)]) =
     | list match {
     |  case (name, age)::t if age%2==0 => {(name, age)::separate(t)}
     |  case (name, age)::t if age%2!=0 => separate(t)
     |  }
separate: (list: List[(String, Int)])List[(String, Int)]

scala> separate(fichier)
scala.MatchError: List() (of class scala.collection.immutable.Nil$)
  at .separate(<console>:12)
  at .separate(<console>:13)
  at .separate(<console>:13)
  at .separate(<console>:13)
  at .separate(<console>:13)
  at .separate(<console>:13)
  at .separate(<console>:13)
  ... 43 elided

Because you haven't handled the case where this is no head of the list, you can do that pretty easy:

scala>  def separate(list: List[(String, Int)]) : List[(String, Int)] =//(List[(String, Int)] , List[(String, Int)]) =
     | list match {
     |  case (name, age)::t if age%2==0 => {(name, age)::separate(t)}
     |  case (name, age)::t if age%2!=0 => separate(t)
     |  case Nil => Nil
     |  }
separate: (list: List[(String, Int)])List[(String, Int)]

scala> separate(fichier)
res2: List[(String, Int)] = List((Bill Morton,36), (Georgia Bates,30), (Jesse Caldwell,46), (Jeffery Wolfe,50), (Roy Norris,18), (Ella Gonzalez,48))

And things will work as you expect them to. However you're doing a lot of recursion here so you might want to annotate the method with tailrec and update appropriately to avoid any Stack overflows from large lists. Or better yet, drop the recursion entirely and just simplify your code to use .filter

Also, if separate is any indication of what you're trying to do overall, you could look into the partition method to get both even and odd numbered people:

val (evens, odds) = fichier.partition(_._2 % 2 == 0)

Answer 4

You need to return a result with your match but you are assigning a value instead.

Unless you need liste for something else, remove the assignment entirely.

case (name, age)::t if age%2==0 => (name, age)::separate(t)

Otherwise return it like so:

case (name, age)::t if age%2==0 => {
     val liste = (name, age)::separate(t)
     liste
     }