Scala 8 - Parametric Polymorphism

스칼라 튜토리얼, scala의 parametric polymophism에 대해 알아보자

---

Parametric Polymorphism: Functions

• Problem

def id1(x: Int): Int = x
def id2(x: Double): Double = x

Can we avoid DRY(Do not Reapeat Yourself)?

• Parametric Polymorphism(a.k.a. For-all Types)

def id[A](x: A): A = x    // type for definition
val f = (x:Int) => x    // type for value

The type of id is [A](x: A)A.

id is a parametric expression. Only definition can have parametric type(value doesn't allow this, except record typed).

id[T] _ is a value of type T=>T for any type T.

---

Example

What would be the result of the below code?

def id[A](x: A) = x

id(3)        // Q1
id("abc")    // Q2

def applyn[A](f: A => A, n: Int, x: A): A =
    n match {
        case 0 => x
        case _ => f(applyn(f, n - 1, x))
    }

applyn((x:Int)=>x+1,100,3)                 // Q3
applyn((x:String)=>x+"!", 10, "gil")    // Q4
applyn(id[String], 10, "hur")            // Q5

def foo[A,B](f: A=>A, x: (A,B)) : (A,B) =
    (applyn[A](f, 10, x._1), x._2)

foo[String,Int]((x:String)=>x+"!",("abc",10))    // Q6

Answer would be :

//Q1 : 3
//Q2 : abc
//Q3 : 103
//Q4 : gil!!!!!!!!!!
//Q5 : hur
//Q6 : (abc!!!!!!!!!!, 10)

---

Full Polymorphism using Scala's trick

type Applyn = {def apply[A](f: A=>A, n: Int, x: A): A}

object applyn {        // val applyn = new {
    def apply[A](f: A=>A, n: Int, x: A): A =
        n match {
            case 0 => x
            case _ => f(apply(f, n-1, x))
        }
}
applyn((x: String)=> x+"!", 10, "gil")
// applyn.apply[String]((x: String)=> x+"!", 10, "gil")

def foo(f: Applyn): String = {
    val a: String = f[String]((x: String)=> x+"!", 10, "gil")
    val b: Int = f[Int]((x: Int) => x+2, 10, 5)
    a+b.toString()
}

foo(applyn)

Record type has def part.

When you use def, every function value is encoded as type ... = {}

f(A=>B) is actually g = {def apply(x: A)=> B}!

---

Function types vs. Record types

val f = (x: Int)=> x
val g = new {
    def apply(x: Int): Int = x
}
f(10)
g(10)
// It automatically interpret as
// g.apply(10)!

def foo(func:Int => Int): Int = func(10)

foo(f)
// foo(g)
// -> It gives error, since g is not function,
// it is record type!
foo(g.apply) // It works well

---

Parametric Polymorphism: Datatypes

sealed abstract class MyOption[A]
case class MyNone[A]() extends MyOption[A]
case class MySome[A](some: A) extends MyOption[A]

sealed abstract class MyList[A]
case class MyNil[A]() extends MyList[A]
case class MyCons[A](hd: A, tl: MyList[A]) extends MyList[A]

sealed abstract class BTree[A]
case class Leaf[A]() extends BTree[A]
case class Node[A](value: A, left: BTree[A], right: BTree[A]) 
extends BTree[A]

def x: MyList[Int] = MyCons(3, MyNil())
def y: MyList[String] = MyCons("abc", MyNil())    

• Excercise :

/*
BSTree[A] = Leaf
| Node of Int * A * BSTree[A] * BSTree[A]
*/

def lookup[A](t: BSTree[A], k: Int) : MyOption[A] =
    ???
def t : BSTree[String] = 
    Node(5,"My5",
        Node(4,"My4",Node(2,"My2",Leaf(),Leaf()),Leaf()),
        Node(7,"My7",Node(6,"My6",Leaf(),Leaf()),Leaf()))

lookup(t, 7)
lookup(t, 3)

• Solution :

sealed abstract class BSTree[A]
case class Leaf[A]() extends BSTree[A]
case class Node[A](key: Int, value: A, left: BSTree[A], right: 
BSTree[A]) extends BSTree[A]

def lookup[A](t: BSTree[A], key: Int) : MyOption[A] =
t match {
    case Leaf() => MyNone()
    case Node(k,v,lt,rt) =>
        k match {
            case _ if key == k => MySome(v)
            case _ if key < k => lookup(lt,key)
            case _ => lookup(rt, key)
        }
    }

def t : BSTree[String] =
    Node(5,"My5",
        Node(4,"My4",Node(2,"My2",Leaf(),Leaf()),Leaf()),
        Node(7,"My7",Node(6,"My6",Leaf(),Leaf()),Leaf()))

lookup(t, 7)
lookup(t, 3)

• Exercise 2:

sealed abstract class BTree[A]
case class Leaf[A]() extends BTree[A]
case class Node[A](value: A, left: BTree[A], right: BTree[A])
    extends BTree[A]

type BSTree[A] = BTree[(Int,A)]

def lookup[A](t: BSTree[A], k: Int) : MyOption[A] =
    ???

def t : BSTree[String] =
    Node((5,"My5"),
        Node((4,"My4"),Node((2,"My2"),Leaf(),Leaf()),Leaf()),
        Node((7,"My7"),Node((6,"My6"),Leaf(),Leaf()),Leaf()))

lookup(t, 7)

• Solution :

type BSTree[A] = BTree[(Int,A)]

def lookup[A](t: BSTree[A], key: Int) : MyOption[A] =
    t match {
        case Leaf() => MyNone()
        case Node((k,v),lt,rt) =>
            k match {
                case _ if key == k => MySome(v)
                case _ if key < k => lookup(lt,key)
                case _ => lookup(rt, key)
            }
    }

def t : BSTree[String] =
    Node((5,"My5"),
        Node((4,"My4"),Node((2,"My2"),Leaf(),Leaf()),Leaf()),
        Node((7,"My7"),Node((6,"My6"),Leaf(),Leaf()),Leaf()))
lookup(t, 7)
lookup(t, 3)