Newer
Older
Higher-Order Given Instances (1)
================================
Consider how we order two `String` values:
- `"abc" < "abd"`?
\vspace{3cm}
-> We compare the characters of each string, element-wise.
-> **Problem**: How to generalize this process to sequences of any
element type `A` for which there is an implicit `Ordering[A]`
instance?
Higher-Order Given Instances (2)
================================
given listOrdering[A](given Ordering[A]): Ordering[List[A]] = ...
Higher-Order Given Instances (3)
================================
given listOrdering[A]
(given ord: Ordering[A]): Ordering[List[A]] = { (xs0, ys0) =>
def loop(xs: List[A], ys: List[A]): Boolean = (xs, ys) match {
case (x :: xsTail, y :: ysTail) => ord.lt(x, y) && loop(xsTail, ysTail)
case (xs, ys) => xs.isEmpty && ys.nonEmpty
}
loop(xs0, ys0)
}
~~~
~~~
scala> sort(List(List(1, 2, 3), List(1), List(1, 1, 3)))
res0: List[List[Int]] = List(List(1), List(1, 1, 3), List(1, 2, 3))
~~~
Higher-Order Given Instances (4)
================================
def sort[A](xs: List[A])(given Ordering[A]): List[A]
given listOrdering[A](given Ordering[A]): Ordering[List[A]]
val xss: List[List[Int]] = ...
sort(xss)
~~~
->
~~~
sort[List[Int]](xss)
~~~
->
~~~
sort[List[Int]](xss)(given listOrdering)
sort[List[Int]](xss)(given listOrdering(given Ordering.Int))
Higher-Order Given Instances (5)
================================
An arbitrary number of given instances can be combined
until the search hits a “terminal” instance:
given a: A = ...
given aToB(given A): B = ...
given bToC(given B): C = ...
given cToD(given C): D = ...
Recursive Given Instances
=========================
given loop(given a: A): A = a
^
error: no implicit argument of type A was found for parameter x of method the.
I found:
loop(/* missing */summon[A])
But method loop produces a diverging implicit search when trying to match type A.
~~~
Summary
=======
In this lecture, we have seen:
- given instance definitions can also have given clauses
- an arbitrary number of given instances can be chained
until a terminal instance is reached