Skip to content
Snippets Groups Projects
progfun2-4-4.md 2.2 KiB
Newer Older
% Higher-Order Givens
Martin Odersky's avatar
Martin Odersky committed
%
%

Higher-Order Given Instances (1)
================================
Martin Odersky's avatar
Martin Odersky committed

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)
================================
Martin Odersky's avatar
Martin Odersky committed

~~~
given listOrdering[A](given Ordering[A]): Ordering[List[A]] = ...
Martin Odersky's avatar
Martin Odersky committed
~~~

Higher-Order Given Instances (3)
================================
Martin Odersky's avatar
Martin Odersky committed

~~~
given listOrdering[A]
  (given ord: Ordering[A]): Ordering[List[A]] = { (xs0, ys0) =>

Martin Odersky's avatar
Martin Odersky committed
  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
Martin Odersky's avatar
Martin Odersky committed
  }
  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)
================================
Martin Odersky's avatar
Martin Odersky committed

~~~
def sort[A](xs: List[A])(given Ordering[A]): List[A]
given listOrdering[A](given Ordering[A]): Ordering[List[A]]
Martin Odersky's avatar
Martin Odersky committed

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))
Martin Odersky's avatar
Martin Odersky committed
~~~

Higher-Order Given Instances (5)
================================
Martin Odersky's avatar
Martin Odersky committed

An arbitrary number of given instances can be combined
until the search hits a “terminal” instance:
Martin Odersky's avatar
Martin Odersky committed

~~~
given a: A = ...
given aToB(given A): B = ...
given bToC(given B): C = ...
given cToD(given C): D = ...
Martin Odersky's avatar
Martin Odersky committed

Martin Odersky's avatar
Martin Odersky committed
~~~

Recursive Given Instances
=========================
Martin Odersky's avatar
Martin Odersky committed

~~~
trait A
given loop(given a: A): A = a
Martin Odersky's avatar
Martin Odersky committed

      ^
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.
Martin Odersky's avatar
Martin Odersky committed
~~~

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