Chapter 3 Funcitonal Data Structures

Functional programs do not update variables or modify data structures.

writing and generalizing pure functions.

3.2 Functional Data Structures

A functional data structure is (not surprisingly!) operated on using only pure functions. Remember, a pure function may only accept some values as input and yield a value as output. It may not change data in place or perform other side effects. Therefore, functional data structures are immutable.



In [ ]:

    
// Singly-linked lists
// + means A is covariant
sealed trait List[+A]  // create List data type interface

case object Nil extends List[Nothing] // Nothing is a subtype for evertything
case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {
    // Pattern mathing
    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: _*))

    val example = Cons(1, Cons(2, Cons(3, Nil)))
    val example2 = List(1, 2, 3)
    val total = sum(example)
}



In [ ]:



In [ ]: