Functional Programming in Scala

Paul Chiusano, Runar Bjarnason

Mentioned 4

Helps programmers learn functional programming and apply it to the everyday business of coding. Original.

More on Amazon.com

Mentioned in questions and answers.

I want to implement an infinite list:

abstract class MyList[+T]
case object MyNil extends MyList[Nothing]
case class MyNode[T](h:T,t: => MyList[T]) extends MyList[T]

//error: `val' parameters may not be call-by-name

the problem is the call-by-name is not allowed.

I've heard that it is because val or var constructor parameter is not allowed for call-by-name. For example:

class A(val x: =>Int) 
//error: `val' parameters may not be call-by-name

But the contradiction is that the normal constructor parameter is still val, despite private. For example:

class A(x: =>Int) 
// pass

So the question :

  • Is the problem really about val or var ?
    • If that. Since the point for call-by-name is to defer computation, Why could not val or var computation(or initialization) be deferred?
  • How to get around the cass class to implement an infinite list?

I have also not found why exactly by-name parameters are prohibited in case classes. I guess explanation should be quite elaborate and complex. But Runar Bjarnason in his book "Functional Programming in Scala" provides a good approach to handle this obstacle. He uses the concept of a "thunk" together with memoizing. Here is an example of Stream implementation:

sealed trait Stream[+A]
case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]
object Stream {
 def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
  lazy val head = hd
  lazy val tail = tl
  Cons(() => head, () => tail)
 }
 def empty[A]: Stream[A] = Empty
 def apply[A](as: A*): Stream[A] =
  if (as.isEmpty) empty else cons(as.head, apply(as.tail: _*))
 }
}

As you see, instead of a regular by-name parameter for the case class data constructor they use what they call a "thunk", a function of zero-arguments () => T. Then to make this transparent for the user they declare a smart constructor in the companion object which allows you to provide a by-name parameters and make them memoized.

I have a problem about a "customer invitation" where a person can invite another person and the invitation is only valid if the invited person invitee someone.

To solve this problem, i was thinking to write a Tree algorithm instead a Graph algorithm.

I'm trying to write this tree structure in Scala and here is how i've started:

case class MyNode(key:Int, children:Option[List[MyNode]] = None)

class MyNodeManager {

  def find(key: Int, tree: Option[List[MyNode]]) = tree match {
    case None => None
    case (h :: t) =>
      println("aa")
    /*if(h.key == key)
        Option(h)
      else
        find(h ::: t)
        */
  }  

}

The input will be something like:

val invites = List((1, 2), (1, 3), (3, 6))

I would like to work with Option[List[MyNode]] because children are option and if the node has been invited, i would like to set value an empty list instead None.

Tree is the best structure to solve my problem or should i go to Graph or something like that (a node in a graph can have multiple children?)? And the other question..what's the difference on those lines (h :: t) and (h ::: t)?

The following code has a compile error:

Error:(16, 13) constructor cannot be instantiated to expected type;
   found   : scala.collection.immutable.::[B]
   required: Option[List[MyNode]]
    case (h :: t) =>
        ^

How can i work with Option[List]?

Should be

def find(key: Int, tree: Option[List[MyNode]]) = tree match {
case None => None
case Some(h :: t) =>
  println("aa")
/*if(h.key == key)
    Option(h)
  else
    find(h ::: t)
    */}  

You are match Option object not tuple. This match is not exhaustive because you are missing

case Some(Nil) => ....

I find it will be better to use only list without Optional. This is mostly about semantic. Optional means something is empty. We have value for empty list (Nil) so we don't need to use additional object to mark such situation. Empty list should be enough

::: function adds the elements of a given list in front of your list. Simply this function is used to concatenate two list
:: is function which add element at the begging of the list.
Also in Scala :: is a case class which have head and tail. If you want to know more about List implementation I suggest you to read https://www.amazon.com/Functional-Programming-Scala-Paul-Chiusano/dp/1617290653

I have the following Scala code to answer question 4 (implement dropWhile on a list, which removes elements from the List prefix as long as they match a predicate) of Chapter 3 of Functional Programming In Scala:

object Chapter3 {

    sealed trait List[+A]

    case object Nil extends List[Nothing]
    case class Cons[+A](head: A, tail: List[A]) extends List[A]

    object List {

        def apply[A](as: A*): List[A] =
            if (as.isEmpty) Nil
            else Cons(as.head, apply(as.tail: _*))

        def dropWhile[A](l: List[A], f: A => Boolean): List[A] = 
            l match {
                case Nil => sys.error("cannot drop from empty list")
                case Cons(h, t) if f(h) => dropWhile(t, f)
                case _ => l
            }

    }

    def main(args : Array[String]) {
        def smallerThanThree(i: Int): Boolean = i < 3
        println( List.dropWhile(List(1, 2, 3, 4, 5), smallerThanThree) )

        // How can I call this directly on the list with anonymous function like below?
        println( List(1, 2, 3, 4, 5).dropWhile(i => i < 3) )
        // => Should return List(3, 4, 5) or Cons(3, Cons(4, Cons(5, Nil))).

    }
}

What I want to do is twofold:

  1. Call dropWhile on the list object (List(1,2,3,4,5).dropWhile([f: A => Boolean])) instead of using List.dropWhile([List[A]], [f: A => Boolean])
  2. Pass an anonymous method (i => i < 3), instead of defining the function smallerThanThree and passing this.

Now this gives the error:

error: value dropWhile is not a member of Main.List[Int]

And the anonymous function does not work also. When I do

println( List.dropWhile(List(1, 2, 3, 4, 5), i => i < 3) )

it gives the error:

error: missing parameter type

Can anyone explain if the above two points can be accomplished, and if so, how?

For you to be able to call dropWhile on an instance of the trait List, that trait must declare this function. The fact that the object by the same name contains this function does not automatically "add" this method to the trait.

You can easily add such a function to List trait by changing the trait definition to:

 sealed trait List[+A] {
   def dropWhile(f: A => Boolean): List[A] = List.dropWhile(this, f)
 }

Then, your suggested code works as expected.

As for passing an anonymous function - in this case the compiler can't infer the Int type on its own, so you must explicitly write the type, as follows:

println( List.dropWhile(List(1, 2, 3, 4, 5), (i: Int) => i < 3) )

I've placed the following code into an object.Scala file within Eclipse, and simply want to know what the value for "x" is (it should be 3). The code won't compile if I place the value anywhere other than within the List object; at the same time, while within the List object, running the file yields no output.

package work

object Work extends App {
  // These 3 lines define a simplified List type
  sealed trait List[+A]
  case object Nil extends List[Nothing]
  case class Cons[+A](head: A, tail: List[A]) extends List[A]

  // This companion object contains basic operations for the List type
  object List {
    def sum(ints: List[Int]): Int = ints match {
      case Nil => 0
      case Cons(x,xs) => x + sum(xs)
    }

    def product(ds: List[Double]): Double = ds match {
      case Nil => 1.0
      case Cons(0.0, _) => 0.0
      case Cons(x,xs) => x * product(xs)
    }

    def apply[A](as: A*): List[A] =
      if (as.isEmpty) Nil
      else Cons(as.head, apply(as.tail: _*))

    // The next line is the value that I want to return. 
    val x = List(1,2,3,4,5) match {
      case Cons(x, Cons(2, Cons(4, _))) => x
      case Nil => 42
      case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y 
      case Cons(h, t) => h + sum(t)
      case _ => 101
     }

  }
}

I initially placed everything inside the object Work extends App in order for it to compile, as otherwise the compiler complains that I'm missing a Main method. But, to have "x" returned, I tried ditching the Work object and instead added a Main method to the expression I want to see evaluated, as follows:

def main(args: Array[String]) {
      val x = List(1,2,3,4,5) match {
        case Cons(x, Cons(2, Cons(4, _))) => x
        case Nil => 42
        case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y case Cons(h, t) => h + sum(t)
        case _ => 101
      }
}

However, I then get the following error:

List has a main method with parameter type Array[String], but work.List will not be a runnable program. Reason: companion is a trait, which means no static forwarder can be generated.

I'm not really sure what this means. I'm also pretty confused about how to properly implement a Main method. I tried to add a Main method directly under the List object, encapsulating all of List's definitions and val x, and it resulted in even more errors than above. I'm confused, and still searching the net for answers, but nothing seems to address my particular issue so far.

Any help would be greatly appreciated.

Below is my original post, containing more information, including the text for the exercise that I'm working on. To work on the exercise, I need to see how expressions evaluate. I normally work within a Scala Worksheet for precisely this reason, as I can see my results within seconds, but this particular exercise involves using a trait and companion object, and their addition has complicated things tremendously for me, as while I understand how they are used in the code, I don't know how to properly implement them.


Original Post


I put the following code into Eclipse IDE's Scala Worksheet, and then spent about two hours trying different ways to make it

  1. compile without errors, and
  2. display evaluated results on the righthand side.

I'm still struggling a lot with (2).

package fpinscala.datastructures
// The following three lines define a simplified List type and behavior
sealed trait List[+A] 
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

// The companion object List defines basic List operations
object List { 
  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0 
    case Cons(x,xs) => x + sum(xs) 
  }

  def product(ds: List[Double]): Double = ds match {
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x,xs) => x * product(xs)
  }

  def apply[A](as: A*): List[A] = 
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))
}

When I run the code above, it outputs a standard error saying that a main argument is missing. Though I'm not very clear about how the def main(args: Array[String) {} or object some_object extends App {} actually work, I do know that they allow the code to actually compile and run. At the same time, the Scala Worksheet never required that I have a Main method in the past, though in the past I also wasn't using classes or traits in the same file. I know I must be missing something.

I've tried

  • extending the List object with App
    • or adding a def main argument underneath it
  • creating an object called "Classes" for the sealed trait and adding the main argument to it
    • or extending it with App
  • creating a larger object "Worksheet" that I then added all of the following to under a def main argument
    • or extending "Worksheet" with App
  • in another Eclipse IDE file, creating a New Scala Trait, adding the trait and class code in it, and then trying to import it into the worksheet, realizing that the companion object List needs to exist in the same file
  • putting all of the above code into a different file, trying to import that file into worksheet, and trying to make any of the list operations work (the problem here is I don't actually know which type of Scala file in the Eclipse IDE the code below would belong to, object, class, or trait)

Some of these have compiled, others have not, but none of them so far have resulted in the worksheet actually producing evaluated results on the righthand side.

Here's the exercise requiring the code above that I've been trying to work on, if only I could actually see how my code evaluated:

Let’s try implementing a few different functions for modifying lists in different ways. You can place this, and other functions that we write, inside the List companion object.

3.2 Implement the function tail for removing the first element of a List. Note that the function takes constant time. What are different choices you could make in your implementation if the List is Nil? We’ll return to this question in the next chapter.

from Functional Programming in Scala.

Thanks so much for your time.

I am not sure why you mention that placing the val x outside the List object prevents you from compiling.

The following compiles and produces the expected output = 3

object Work extends App {
  // These 3 lines define a simplified List type
  sealed trait List[+A]
  case object Nil extends List[Nothing]
  case class Cons[+A](head: A, tail: List[A]) extends List[A]

  // This companion object contains basic operations for the List type
  object List {
    def sum(ints: List[Int]): Int = ints match {
      case Nil => 0
      case Cons(x,xs) => x + sum(xs)
    }

    def product(ds: List[Double]): Double = ds match {
      case Nil => 1.0
      case Cons(0.0, _) => 0.0
      case Cons(x,xs) => x * product(xs)
    }

    def apply[A](as: A*): List[A] =
      if (as.isEmpty) Nil
      else Cons(as.head, apply(as.tail: _*))
  }

  // The next line is the value that I want to return.
  val x = List(1,2,3,4,5) match {
    case Cons(x, Cons(2, Cons(4, _))) => x
    case Nil => 42
    case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
    case Cons(h, t) => h + List.sum(t)
    case _ => 101
  }

  println(x)
}