{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Haskell Cheat Sheet as a Jupyter Notebook
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Even once Jupyter is installed, and Haskell, getting Haskell to talk to Jupyter was an adventure. But some information on the web made it possible. Don't forget to install ncurses. Linux install was easier than MacOS."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The obligatory first example. "
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"hello"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"putStrLn \"hello\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here is a simple function definition. There is a type signature, and then the function's definition."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"-- It's good to have explicit function signatures\n",
"increment :: Int -> Int -- but all functions have signatures\n",
"increment x = x+1 -- as well as definitions"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"increment 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In Haskell, lists are used all the time. A list is made up of zero or more elements, separated by commas, wrapped in square brackets"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"mySum :: [Integer] -> Integer\n",
"mySum [] = 0\n",
"mySum (x:xs) = x+mySum(xs)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"17"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"mySum[2,3,5,7]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The ellipsis notation can be used in several contexts, including as a way of defining useful lists."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"-- sum is builtin, but \n",
"sum1toN :: Integer -> Integer\n",
"sum1toN n = sum [1..n]"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"55"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"sum1toN 10"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Useful insight: mapping a function to a list can be used instead of for loops, and is sometimes if not usually faster."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"fact :: Integer -> Integer\n",
"fact 0 = 1\n",
"fact n = n*fact(n-1)\n",
"\n",
"fact2 :: Integer -> Integer\n",
"fact2 0 = 1\n",
"fact2 n = product[1..n] -- but using the builtin product function should be faster"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"3628800"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"fact 10"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"3628800"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"fact2 10"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"These two functions seem to give the same answer. In general, a user-defined function will be slower than a builtin function that does the same thing, \n",
"\n",
"But how can we tell which is faster? Haskell has a number of ways to do this, but there is a method that grabs the value of a CPU timer. Details at the Haskell Wiki, https://wiki.haskell.org/Timing_computations \n",
"\n",
"We can create a \"test\" function that measures the execution time of fact and fact2. We'll look at the implementation of test shortly. For now, we assume that it is available to help us measure the performance of Haskell functions."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"Not in scope: ‘test’"
],
"text/plain": [
"Not in scope: ‘test’"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"test 10000"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"Not in scope: ‘test’"
],
"text/plain": [
"Not in scope: ‘test’"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"test 20000"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"Not in scope: ‘test’"
],
"text/plain": [
"Not in scope: ‘test’"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"test 40000"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What the heck is going on? One would expect fact2 to be faster than fact for every value of n. But it usually is not, and when it is faster it's not by much. One also notices that the time to compute fact n OR fact2 n grows faster than the value of n, even though both are of O(n) in terms of asymptotic complexity."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We'll look at other examples of recursion and high order functions, with the goal of evaluating runtime performance."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import Data.Ratio\n",
"ratioTest :: Integer -> Integer -> Rational\n",
"ratioTest x y = 1 % x + 1 % y"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5 % 6"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"ratioTest 2 3"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We now introduce another form of function definition, namely the use of patterns. This is very powerful! "
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"and1 :: Bool -> Bool -> Bool \n",
"and1 x y =\n",
" if x==True && y==True then True else False\n",
"\n",
"and2 :: Bool -> Bool -> Bool -- two Bool input args\n",
"and2 True True = True -- and pattern matching\n",
"and2 _ _ = False -- with underscore as a wildcard"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"and1 True False"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"and2 True True"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"-- quadratic formula\n",
"--roots :: Float -> Float -> Float -> (Float, Float)\n",
"roots a b c = \n",
" if discrim<0 then (0,0) -- this example ignores complex roots\n",
" else (x1, x2) where\n",
" discrim = b*b - 4*a*c\n",
" e = -b/(2*a)\n",
" x1 = e + sqrt discrim / (2*a)\n",
" x2 = e - sqrt discrim / (2*a)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(-1.0,-1.0)"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"roots 1 2 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In Haskell type signatures, stipulations can be made about the input arguments. For example, to run any kind of sort function, there must be ordering functions such as < and > defined on the input arguments. "
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"qsortP :: Ord a => [a] -> [a]\n",
"qsortP [] = []\n",
"qsortP (x:xs) = qsortP lowerHalf ++ [x] ++ qsortP upperHalf\n",
" where\n",
" lowerHalf = [a | a <- xs, a <= x] \n",
" upperHalf = [b | b <- xs, b > x]"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[]"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"[4,5,10,15,25]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"qsortP []\n",
"qsortP [10,5,25,15,4]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The general form for working with lists is shown. Do one thing for an empty list, and then consider a list that contains a first element x, and the possibly empty rest of the list, referred to as xs."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The example above also introduces list comprehensions, which are also very useful!"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"--- finding the length of a list\n",
"listLen1 :: [a] -> Int\n",
"listLen1 [] = 0\n",
"listLen1 (x:xs) = 1 + listLen1(xs) "
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"listLen1 [3,4,5]"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"-- here's another (faster?) way to do listLen\n",
"listLen2 :: [a] -> Int\n",
"listLen2 = sum . map (const 1) -- . is explicit function composition"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"listLen2 [4,5,6,7]"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"-- yet another way to do list length, using a list comprehension\n",
"listLen3 :: [a] -> Int\n",
"listLen3 aList = sum [1 | x <- aList]"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"listLen3 [5,6,7,8,9]"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"head [3,4,5]"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[4,5]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"tail [3,4,5]"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"[3,4,5,6,7] !! 2"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[7,6,5,4,3]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"reverse [3,4,5,6,7]"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[1,2,3,4,5,6]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"[1,2,3] ++ [4,5,6]"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import Text.Printf\n",
"import Control.Exception\n",
"import System.CPUTime\n",
" \n",
"time :: IO t -> IO t\n",
"time a = do\n",
" start <- getCPUTime\n",
" v <- a\n",
" end <- getCPUTime\n",
" let diff = (fromIntegral (end - start)) / (10^12)\n",
" printf \"Computation time: %0.3f sec\\n\" (diff :: Double)\n",
" return v\n",
" \n",
"test n = do\n",
" putStrLn \"Starting test 1\"\n",
" time $ fact n `seq` return ()\n",
" putStrLn \"Done.\"\n",
" putStrLn \"Starting test 2\"\n",
" time $ fact2 n `seq` return ()\n",
" putStrLn \"Done.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There is a lot of new Haskell here. The import command expands the name space, more or less as the same import command does in Java.\n",
"\n",
"The type signature of the time function deserves more explanation than can be given at this point. But note that the function test is not a pure function. Instead, it has the side effect of changing the machine state, namely by performing IO. \n",
"\n",
"By the way, the do construct is a generalization of the seq operator, and is used for creating a sequence of function invocations. \n",
"\n",
"The getCPUTime method is part of the System.CPUTime package. It seems to return an integer. When the CPU time is grabbed before and after the calculation being measured, the difference between those times is still an integer (or an integer-like object of infinite precision?) and divided by 10 to the 12 th power to scale it to seconds.\n",
"\n",
"Those who know about I/O in C will welcome the printf command. Note that we need to stipulate that diff is a double before it is usable with the f format code.\n",
"\n",
"The time function is invoked in the function called test, which takes a single integer as an input argument. Note that Haskell was able to deduce test's signature. The $ operator forces the rest of the line to be treated as the operand of the time function. The seq operator reminds me of the UNIX shell pipe, in the sense that the output of the factorial function is fed into an anonymous function which ignores the numerical input, and returns a null object. This is an example of how Haskell's strict type checking forces you to do the non-obvious."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"When a function takes more than one input argument, Haskell regards it as akin to a pair of functions, each taking one argument. This is your first look at the idea of currying in functional languages. You can look up the mathematician Haskell Curry on Wikipedia, if you like."
]
}
],
"metadata": {
"celltoolbar": "Raw Cell Format",
"kernelspec": {
"display_name": "Haskell",
"language": "haskell",
"name": "haskell"
},
"language_info": {
"codemirror_mode": "ihaskell",
"file_extension": ".hs",
"name": "haskell",
"version": "7.10.3"
}
},
"nbformat": 4,
"nbformat_minor": 0
}