haskell_fun.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![logo](http://sunscrapers.com/static/images/logo.png)\n",
    "# Haskell Fun\n",
    "### by Paweł M. Święcki\n",
    "\n",
    "* https://github.com/pawelswiecki\n",
    "\n",
    "* http://sunscrapers.com/meet-the-team/pawel\n",
    "\n",
    "* https://www.linkedin.com/in/pawelswiecki\n",
    "\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What I will tell you about?\n",
    "1. What is Haskell? [tl;dr version]\n",
    "2. Basics\n",
    "  * Some Basic Types\n",
    "  * List Type\n",
    "  * Tuple Type\n",
    "  * Function Type\n",
    "  * Conditionals\n",
    "  * \"Where\" Clause\n",
    "3. Patterns\n",
    "  * Pattern Matching\n",
    "  * List Patterns\n",
    "4. List Comprehensions\n",
    "  * Generators\n",
    "  * List Comprehensions\n",
    "5. Recursive Functions\n",
    "6. Summary: QuickSort\n",
    "7. Want more?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What I won't tell you about?\n",
    "* What is functional programming, in-depth? [another talk]\n",
    "* Haskell type system and type inference (types, type variables, typeclasses, etc.) [another talk?]\n",
    "* Currying and partial application\n",
    "* Higher order functions [another talk?]\n",
    "* More advanced stuff like Functors, Applicative Functors, Monoids, Monads...\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# 1. What is Haskell programming language?\n",
    "* general-purpose \n",
    "* purely functional (vs imperative)\n",
    "  * expression-oriented: everything is an expression (yields a value)\n",
    "  * immutability: avoids mutable states\n",
    "  * functions are first-class\n",
    "* lazy\n",
    "* statically typed (with type inference)\n",
    "* developed by some pretty smart people\n",
    "* standard compiler: Glasgow Haskell Compiler [GHC] (https://www.haskell.org/ghc)\n",
    "\n",
    "It is named after logician Haskell Curry (1900–1982)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Basics\n",
    "\n",
    "Notation:\n",
    "\n",
    "    <expression> :: <type>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Some Basic Types"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "b1 :: Bool\n",
    "b1 = True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "b2 :: Bool\n",
    "b2 = b1 && False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "c1 :: Char\n",
    "c1 = 'a'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "f1 :: Float\n",
    "f1 = 1.337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "i1 :: Integer\n",
    "i1 = 1337"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### List Type\n",
    "A sequence of values of the same type. Potentially infinite."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "l1 :: [Bool]\n",
    "l1 = [True, True, False]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "l2 :: [Integer]\n",
    "l2 = [5, 10, 15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "-- string is a list of chars\n",
    "s1 :: [Char]\n",
    "s1 = \"foobarbaz\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "isStringAList :: Bool\n",
    "isStringAList = \"test1\" == ['t', 'e', 's', 't', '1']\n",
    "isStringAList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Two list operators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `(:)` operator (cons)\n",
    "adds one element at the start of the list\n",
    "\n",
    "`(:) :: a -> [a] -> [a]`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "l3 :: [Integer]\n",
    "l3 = 1:[2,3]\n",
    "l3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Btw, `[1,2,3]` is syntactic sugar for `1:2:3:[]`.\n",
    "\n",
    "So `\"Haskell\"`\n",
    "\n",
    "is syntactic sugar for `['H', 'a', 's', 'k', 'e', 'l', 'l']`,\n",
    "\n",
    "which is syntactic sugar for `'H':'a':'s':'k':'e':'l':'l':[]`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `(++)` operator\n",
    "concatenates two lists\n",
    "\n",
    "`(++) :: [a] -> [a] -> [a]`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "l4 :: [Integer]\n",
    "l4 = [1,2,3] ++ [4,5,6]\n",
    "l4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "l5 :: String\n",
    "l5 = \"Haskell\" ++ \" is \" ++ \"fun!\"\n",
    "l5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tuple Type\n",
    "A sequence of values of different, fixed, types. Fixed size."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "t1 :: (String, String, Integer)\n",
    "t1 = (\"John\", \"Smith\", 45)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "t2 :: ((Float, Float), String, Bool)\n",
    "t2 = ((52.2297700, 21.0117800), \"Warsaw\", True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function Types\n",
    "\n",
    "Function is a mapping (`->`) from values of one type to values of another type.\n",
    "\n",
    "Function definition:\n",
    "\n",
    "    <function_name> <param1> <param2> ... = <expression>\n",
    "\n",
    "No commas and no parentheses in function definition and application."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "addOne :: Integer -> Integer\n",
    "addOne n = n + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "addTwoIntegers     :: Integer -> Integer -> Integer\n",
    "addTwoIntegers x y = x + y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "isLetterA   :: Char -> Bool\n",
    "isLetterA c = c == 'A' || c == 'a'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "isLowerCase   :: Char -> Bool\n",
    "isLowerCase c = c >= 'a' && c <= 'z'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "even'   :: Integer -> Bool\n",
    "even' n = n `mod` 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "odd'   :: Integer -> Bool\n",
    "odd' n = not (even' n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conditionals\n",
    "\n",
    "    if <condition> then <true-value> else <false-value>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sign   :: Integer -> Integer\n",
    "sign n = if n < 0 then -1 else if n == 0 then 0 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "-- Guarded equations\n",
    "sign' :: Integer -> Integer\n",
    "sign' n | n < 0     = -1\n",
    "        | n == 0    = 0\n",
    "        | otherwise = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### \"Where\" Clause"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "initials firstname lastname = [f] ++ \". \" ++ [l] ++ \".\"\n",
    "    where f = head firstname\n",
    "          l = head lastname"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Patterns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pattern Matching"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "isOne   :: Integer -> Bool\n",
    "isOne 1 = True\n",
    "isOne _ = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "code     :: Integer -> [Char]\n",
    "code 400 = \"Bad Request\"\n",
    "code 401 = \"Unauthorized\"\n",
    "code 402 = \"Payment Required\"\n",
    "code 403 = \"Forbidden\"\n",
    "code 404 = \"Not Found\"\n",
    "code 405 = \"Method Not Allowed\"\n",
    "code 406 = \"Not Acceptable\"\n",
    "code 407 = \"Proxy Authentication Required\"\n",
    "code 408 = \"Request Timeout\"\n",
    "code 409 = \"Conflict\"\n",
    "code 410 = \"Gone\"\n",
    "code _   = error \"Unknown Status Code\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "t2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "getLatitude                  :: ((Float, Float), String, Bool) -> Float\n",
    "getLatitude ((lat, _), _, _) = lat\n",
    "getLatitude t2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### List Patterns\n",
    "in `(x:xs)` pattern `x` is the first element, `xs` are the rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "head'       :: [t] -> t\n",
    "head' []    = error \"Empty list does not have head!\"\n",
    "head' (x:_) = x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tail'        :: [t] -> [t]\n",
    "tail' []    = error \"Empty list does not have tail!\"\n",
    "tail' (_:xs) = xs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. List Comprehensions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Generators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g1 :: [Integer]\n",
    "g1 = [1..5]\n",
    "g1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g1 == [1,2,3,4,5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g2 :: [Integer]\n",
    "g2 = [0,5..100]\n",
    "g2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g3 :: [Integer]\n",
    "g3 = [1..]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g4 :: String\n",
    "g4 = ['A'..'Z']\n",
    "g4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### List Comprehensions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "l5 :: [Integer]\n",
    "l5 = [x^2 | x <- [1..10]]  -- \"every x^2, such that x is drawn from [1..10]\"\n",
    "l5\n",
    "-- in Python: [x**2 for x in range(1, 11)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "l6 :: [Bool]\n",
    "l6 = [even' x | x <- [1..10]]\n",
    "l6\n",
    "-- in Python: [x % 2 == 0  for x in range(1, 11)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "l7 :: [Integer]\n",
    "l7 = [x | x <- [1..10], odd x]  -- \"every x, such that x is drawn from [1..10], if x is odd\"\n",
    "l7\n",
    "-- in Python: [x for x in range(1, 11) if x % 2 == 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5. Recursive Functions\n",
    "ie. functions that call themselves"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "factorial   :: Integer -> Integer\n",
    "factorial 0 = 1\n",
    "factorial n = n * factorial (n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "product'        :: [Integer] -> Integer\n",
    "product' []     = 1\n",
    "product' (n:ns) = n * product' ns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "length'        :: [a] -> Integer\n",
    "length' []     = 0\n",
    "length' (_:xs) = 1 + length' xs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "zip'               :: [a] -> [b] -> [(a, b)]\n",
    "zip' []     _      = []\n",
    "zip' _      []     = []\n",
    "zip' (x:xs) (y:ys) = (x,y): zip' xs ys"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6. Summary: QuickSort\n",
    "\n",
    "Let's see how this all work in implementation of QuickSort algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "qsort        :: [Integer] -> [Integer]\n",
    "qsort []     = []\n",
    "qsort (x:xs) =\n",
    "    qsort smaller ++ [x] ++ qsort larger\n",
    "    where\n",
    "        smaller = [a | a <- xs, a <= x]\n",
    "        larger  = [b | b <- xs, b > x]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_This is probably the simplest implementation of QuickSort in any programming language._\n",
    "\n",
    "See also: http://learnyouahaskell.com/recursion#quick-sort.\n",
    "\n",
    "Comments / problems:\n",
    "\n",
    "* To make `smaller` and `larger` lists it goes twice through the list.\n",
    "* It's not \"true\" quicksort, since it doesn't work in-place.\n",
    "* The fist element is chosen a pivot, so in worst case (already sorted list) it's runtime is $O(n^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### In Python\n",
    "`def qsort(list):\n",
    "    if list == []: \n",
    "        return []\n",
    "    else:\n",
    "        pivot = list[0]\n",
    "        smaller = qsort([x for x in list[1:] if x < pivot])\n",
    "        larger = qsort([x for x in list[1:] if x >= pivot])\n",
    "        return smaller + [pivot] + larger`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7. Want more?\n",
    "\n",
    "* [course] **_Introduction to Functional Programming_ by Erik Meijer** [https://www.edx.org/course/introduction-functional-programming-delftx-fp101x-0]\n",
    "\n",
    "* [book] **_Learn You a Haskell for Great Good! A Beginner's Guide_ by Miran Lipovača** \n",
    "[http://learnyouahaskell.com]\n",
    "\n",
    "* [book] **_Programming in Haskell_ by Graham Hutton** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Thanks!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "name": "haskell",
   "version": "7.8.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}