{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programming in Haskell\n",
    "\n",
    "## Chapter 5 - List Comprehensions\n",
    "\n",
    "### Set comprehensions\n",
    "\n",
    "In mathematics, the comprehension notation can be used to construct new sets from old sets.\n",
    "\n",
    "$ \\{x^2 | X \\in \\{1...5\\}\\} $\n",
    "\n",
    "The set {1,4,9,16,25} of all numbers $x^2$ such that x is an element of the set {1...5}.\n",
    "\n",
    "### Lists Comprehensions\n",
    "\n",
    "In Haskell, a similar comprehension notation can be used to construct new lists from old lists\n",
    "\n",
    "$ [X^2 | x \\leftarrow [1..5]] $\n",
    "\n",
    "The list [1,4,9,16,25] of all numbers x^2 such that x is an element of the list [1..5].\n",
    "\n",
    "#### Note\n",
    "\n",
    "- The expression x $\\leftarrow$ [1..5] is called a generator, as it states how to generate values for x.\n",
    "- Comprehensions can have multiple generators, seperated by commas. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[(x,y) | x <- [1,2,3], y <- [4,5]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Changing the order of the generators changes the order of the elements in the final list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[(x,y) | y <- [4,5], x <- [1,2,3]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Multiple generators are like nested loops, with later generators as more deeply nested loops whose variables change value more frequently\n",
    "\n",
    "- For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[(x, y) | y <- [4,5], x <- [1,2,3]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "x $\\leftarrow$ [1,2,3] is the last generator, so the value of the x component of each pair changes most frequently\n",
    "\n",
    "### Dependent Generators\n",
    "\n",
    "Later generators can depend on the variables that are introduced by earlier generators."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[(x, y) | x <- [1..3], y <- [x..3]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The list [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)] of all pairs of number (x,y) such that x,y are elements of the list [1..3] and  $y \\geq x$\n",
    "\n",
    "Using a dependant generator we can define the library function that concatenates a list of lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "concat :: [[a]] -> [a]\n",
    "concat xss = [x | xs <- xss, x <- xs]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,2,3,4,5,6]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "concat [[1,2,3], [4,5], [6]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Guards\n",
    "\n",
    "List comprehensions can use guards to restrict the values produced by earlier generators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4,6,8,10]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[x | x <- [1..10], even x]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The list [2,4,6,8,10] of all numbers x such that x is an element of the list [1..10] and x is even\n",
    "\n",
    "Using a guard we can define a function that maps a positive integer to its list of factors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "factors :: Int -> [Int]\n",
    "factors n = \n",
    "    [x | x <- [1..n], n `mod` x == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,3,5,15]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "factors 15"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A postive integer is prime if its only factors are 1 and itself. Hence, using factors we can define a function that decides if a number is prime:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "prime :: Int -> Bool\n",
    "prime n = factors n == [1,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "prime 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "prime 15"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using a guard we can now define a function that returns the list of all primes up to a given limit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "primes :: Int -> [Int]\n",
    "primes n = [x | x <- [1..n], prime x]\n",
    "\n",
    "-- notice how you can get the same results\n",
    "-- even if you do primes n = [x | x <- [2..n], prime x]\n",
    "-- because we know 1 is not a prime and we do not have to always check for that"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,3,5,7,11,13,17,19,23,29,31,37]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "primes 40"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Zip function\n",
    "\n",
    "A useful library function is zip, which maps two lists to a list of pairs of their corresponding elements.\n",
    "\n",
    "``` haskell\n",
    "zip :: [a] -> [b] -> [(a,b)]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a',1),('b',2),('c',3)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "zip ['a', 'b', 'c'] [1,2,3,4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using zip we can define a function returns the list of all pairs of adjacent elements from a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "pairs :: [a] -> [(a,a)]\n",
    "pairs xs = zip xs (tail xs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1,2),(2,3),(3,4),(4,5)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "pairs [1,2,3,4,5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using pairs we can define a function that decides if the elements in a list are sorted:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted :: Ord a => [a] -> Bool\n",
    "sorted xs = and [x <= y | (x,y) <- pairs xs]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sorted [1,2,3,4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sorted [1,2,45,3,7]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using zip we can define a function that returns the list of all position of a value in a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "positions :: Eq a => a -> [a] -> [Int]\n",
    "positions x xs =\n",
    "    [i | (x', i) <- zip xs [0..], x == x']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,2,4,7]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "positions 0 [1,0,0,1,0,1,1,0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### String Comprehensions\n",
    "\n",
    "A string is a sequence of characters enclosed in double quotes. Internally, however, strings are represented as lists of characters.\n",
    "\n",
    "``` haskell\n",
    "\"abc\" :: String\n",
    "```\n",
    "\n",
    "Means ['a','b','c'] :: Char\n",
    "\n",
    "Because strings are just special kinds of lists, any polymorphic function that operates on lists can also be applied to strings. For example:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "length \"abcde\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"abc\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "take 3 \"abcde\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a',1),('b',2),('c',3)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "zip \"abc\" [1,2,3,4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Similarly, list comprehensions can also be used to define functions on strings, such as counting how many times a character occurs in a string:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "count :: Char -> String -> Int\n",
    "count x xs = length [x' | x' <- xs, x' == x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "count 's' \"Mississippi\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercises\n",
    "\n",
    "1. A triple (x,y,z) of positive integers is called pythagorean if $x^2 + y^2 = z^2$. Using a list comprehension, define a function\n",
    "\n",
    "``` haskell\n",
    "pyths :: Int -> [(Int, Int, Int)]\n",
    "```\n",
    "\n",
    "That maps an integer n to all such triples with components in [1..n]. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "pyths :: Int -> [(Int, Int, Int)]\n",
    "pyths x = [(x',y,z) | x' <- [1..x], y <- [1..x], z <- [1..x], x'^2 + y^2 == z^2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(3,4,5),(4,3,5)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "pyths 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. A positive integer is perfect if it equals the sum of all of its factors, excluding the number itself. Using a list comprehension, define a function\n",
    "\n",
    "``` haskell\n",
    "perfects :: Int -> [Int]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "perfects :: Int -> [Int]\n",
    "perfects x = [x' | x' <- [1..x], sum (factors x') - x' == x']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6,28,496]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "perfects 500"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. The scalar product of two lists of integers $xs$ and $ys$ of length n is given by the sum of the products of the corresponding integers:\n",
    "\n",
    "$ \\sum ^{n-1}_{i=0} (xs_i * ys_i) $\n",
    "\n",
    "Using a list comprehension, define a function that returns the scalar product of two lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><div class=\"suggestion-name\" style=\"clear:both;\">Use uncurry</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">fst xys * snd xys</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">uncurry (*) xys</div></div>"
      ],
      "text/plain": [
       "Line 2: Use uncurry\n",
       "Found:\n",
       "fst xys * snd xys\n",
       "Why not:\n",
       "uncurry (*) xys"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "scalarproduct :: [Int] -> [Int] -> Int\n",
    "scalarproduct xs ys = sum [fst xys * snd xys | xys <- zip xs ys]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "scalarproduct [1,2,3] [1,2,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "mimetype": "text/x-haskell",
   "name": "haskell",
   "pygments_lexer": "Haskell",
   "version": "8.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}