{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style=\"float: left;\"><a href=\"upper-type-bounds.ipynb\" target=\"_blank\">Previous</a></p>\n",
    "<p style=\"float: right;\"><a href=\"inner-classes.ipynb\" target=\"_blank\">Next</a></p>\n",
    "<p style=\"text-align:center;\">Tour of Scala</p>\n",
    "<div style=\"clear: both;\"></div>\n",
    "\n",
    "# Lower Type Bounds\n",
    "\n",
    "While [upper type bounds](upper-type-bounds.ipynb) limit a type to a subtype of another type, *lower type bounds* declare a type to be a supertype of another type. The term `B >: A` expresses that the type parameter `B` or the abstract type `B` refer to a supertype of type `A`. In most cases, `A` will be the type parameter of the class and `B` will be the type parameter of a method.\n",
    "\n",
    "Here is an example where this is useful:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "attributes": {
     "classes": [
      "tut"
     ],
     "id": ""
    }
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "cmd0.sc:2: covariant type B occurs in contravariant position in type B of value elem\n",
      "  def prepend(elem: B): Node[B]\n",
      "              ^cmd0.sc:6: covariant type B occurs in contravariant position in type B of value elem\n",
      "  def prepend(elem: B): ListNode[B] = ListNode(elem, this)\n",
      "              ^cmd0.sc:12: covariant type B occurs in contravariant position in type B of value elem\n",
      "  def prepend(elem: B): ListNode[B] = ListNode(elem, this)\n",
      "              ^Compilation Failed"
     ]
    },
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "Compilation Failed"
     ]
    }
   ],
   "source": [
    "trait Node[+B] {\n",
    "  def prepend(elem: B): Node[B]\n",
    "}\n",
    "\n",
    "case class ListNode[+B](h: B, t: Node[B]) extends Node[B] {\n",
    "  def prepend(elem: B): ListNode[B] = ListNode(elem, this)\n",
    "  def head: B = h\n",
    "  def tail: Node[B] = t\n",
    "}\n",
    "\n",
    "case class Nil[+B]() extends Node[B] {\n",
    "  def prepend(elem: B): ListNode[B] = ListNode(elem, this)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This program implements a singly-linked list. `Nil` represents an empty element (i.e. an empty list). `class ListNode` is a node which contains an element of type `B` (`head`) and a reference to the rest of the list (`tail`). The `class Node` and its subtypes are covariant because we have `+B`.\n",
    "\n",
    "However, this program does _not_ compile because the parameter `elem` in `prepend` is of type `B`, which we declared *co*variant. This doesn't work because functions are *contra*variant in their parameter types and *co*variant in their result types.\n",
    "\n",
    "To fix this, we need to flip the variance of the type of the parameter `elem` in `prepend`. We do this by introducing a new type parameter `U` that has `B` as a lower type bound."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "attributes": {
     "classes": [
      "tut"
     ],
     "id": ""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mNode\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mListNode\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mNil\u001b[39m"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trait Node[+B] {\n",
    "  def prepend[U >: B](elem: U): Node[U]\n",
    "}\n",
    "\n",
    "case class ListNode[+B](h: B, t: Node[B]) extends Node[B] {\n",
    "  def prepend[U >: B](elem: U): ListNode[U] = ListNode(elem, this)\n",
    "  def head: B = h\n",
    "  def tail: Node[B] = t\n",
    "}\n",
    "\n",
    "case class Nil[+B]() extends Node[B] {\n",
    "  def prepend[U >: B](elem: U): ListNode[U] = ListNode(elem, this)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can do the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "attributes": {
     "classes": [
      "tut"
     ],
     "id": ""
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mBird\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mAfricanSwallow\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mEuropeanSwallow\u001b[39m\n",
       "\u001b[36mafricanSwallowList\u001b[39m: \u001b[32mListNode\u001b[39m[\u001b[32mAfricanSwallow\u001b[39m] = \u001b[33mListNode\u001b[39m(AfricanSwallow(), Nil())\n",
       "\u001b[36mbirdList\u001b[39m: \u001b[32mNode\u001b[39m[\u001b[32mBird\u001b[39m] = \u001b[33mListNode\u001b[39m(AfricanSwallow(), Nil())\n",
       "\u001b[36mres1_5\u001b[39m: \u001b[32mNode\u001b[39m[\u001b[32mBird\u001b[39m] = \u001b[33mListNode\u001b[39m(\n",
       "  EuropeanSwallow(),\n",
       "  \u001b[33mListNode\u001b[39m(AfricanSwallow(), Nil())\n",
       ")"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trait Bird\n",
    "case class AfricanSwallow() extends Bird\n",
    "case class EuropeanSwallow() extends Bird\n",
    "\n",
    "\n",
    "val africanSwallowList= ListNode[AfricanSwallow](AfricanSwallow(), Nil())\n",
    "val birdList: Node[Bird] = africanSwallowList\n",
    "birdList.prepend(new EuropeanSwallow)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `Node[Bird]` can be assigned the `africanSwallowList` but then accept `EuropeanSwallow`s.\n",
    "<p style=\"float: left;\"><a href=\"upper-type-bounds.ipynb\" target=\"_blank\">Previous</a></p>\n",
    "<p style=\"float: right;\"><a href=\"inner-classes.ipynb\" target=\"_blank\">Next</a></p>\n",
    "<p style=\"text-align:center;\">Tour of Scala</p>\n",
    "<div style=\"clear: both;\"></div>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala (2.13)",
   "language": "scala",
   "name": "scala213"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.13.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}