progfun2-4-4.md

% Higher-Order Givens
%
%

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 = ...

summon[D]
~~~

Recursive Given Instances
=========================

~~~
trait A
given loop(given a: A): A = a

summon[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