# Learn You a Haskell for Great Good

An Introductory Haskell tutorial from Learn You a Haskell for Great Good!.

# Learn You a Haskell for Great Good!

• Modules is a collection of related functions, types and typeclasses.
• Prelude module is imported by default.
import <module name>
• nub is a function defined in Data.List that take a list and weeds out duplicate elements.
• The following are equivalent
length.nub
\xs -> length (nub xs)
• To import module in GHCI (interpreter), use
:m + Data.List Data.Map Data.set
• To use, or hide a specific function.
import Data.List (nub, sort)
import Data.List hiding (nub)
• To resolve conflict in namespace, use qualified to ensure that import module still need to use the module name to call each function such as
import qualified Data.Map
Data.Map.filter
import qualified Data.Map as M
M.filter

## Data.List

• Data.List module contain function about List.
• intersperse take an element and a list and then puts that element in between each pair of element in the list.
intersperse '.' "MONKEY"
"M.O.N.K.E.Y"
• intercalate takes a list of lists and a list and inserts the list in between the list of lists and flatten the list of lists.
intercalate [0,0] [[1,2],[3,4],[5,6]]
[1,2,0,0,3,4,0,0,5,6]
• transpose transposes a list of lists like a 2D matrix.
• concat flatten a list of lists into a list of elements.
• The following are equivalent
concat (map (replicate 4) [1..3])
concatMap (replicate 4) [1..]
• and, or follow the predicate logic
• any and all take a predicate and then check if any or all the elements in a list satisfy the predicate.
• iterate take a function and a starting value and applies the function to the starting value and then apply the function to the result and use the result as new starting value
fromList[3,5,7]
Set.map (+1) $Set.fromList [3,4,5,6,7,2,3,4] fromList [3,4,5,6,7,8] ## Making our own modules • To make your own modules • create a file with a new module name (e.g. Geometry.hs) • Specify module name and functions at the top • implement each function below it • to use the module, use import but the module file must be in the same folder. module Geometry ( sphereVolume , sphereArea , cubeVolume , cubeArea , cuboidArea , cuboidVolumne ) where sphereVolume :: Float -> Float sphereVolume radius = (4.0 / 3.0) * pi * (radius ^ 3) ... ## Other commands • additional explanation of fold here. foldr (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..5]) "(1+(2+(3+(4+(5+0)))))" foldl (\x y -> concat ["(",x,"+",y,")"]) "0" (map show [1..5]) "(((((0+1)+2)+3)+4)+5) Advertisements # Chapter 6: Higher Order Functions # Learn You a Haskell for Great Good! ## Curried functions • Every function in Haskell officially only takes one parameter • If we call a function with too few parameters, we get back a partially applied function (the return ->) multThree :: (Num a) => a -> a -> a -> a multThree x y z = x * y * z • If we do multThree 3 4 5, which is same as ((multThree 3) 4) 5, the 3 is applied to multThree and the function type is the same as multThree :: (Num a) => a -> (a -> (a -> a)) • and will return another function that has type as follow multThree :: (Num a) => a -> (a -> a) • applied 4 to this function and it is return a function with the following type multThree :: (Num a) => a -> a • and finally apply 5 to the last function and return a. By calling the function with too few parameter, we create new function on the fly. • The following two functions are the same because compare has type (Ord a) => a -> (a -> Ordering) and we can use that function for the value we need to compare with. compareWithHundred :: (Num a, Ord a) => a -> Ordering compareWithHundred x = compare 100 x compareWithHundred = compare 100 • Similarly, Infix function works the same way. The function will take one parameter and then applied to the missing operand. Thus, calling divideByTen 200 is equivalent to 200 / 10 or (/10) 200. divideByTen :: (Floating a) => a -> a divideByTen = (/10) ## Some higher-orderism is in order • Function can take a function as parameter applyTwice :: (a -> a) -> a -> a applyTwice f x = f (f x) • applyTwice take two parameters, a function (a->a) and a of the same type and return a. This function apply whatever the function is twice and then apply it to the value. • zipWith’ takes two lists and a function and apply the function to each corresponding element of the lists and produce a result list. zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c] zipWith' _ [] _ = [] zipWith' _ _ [] = [] zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys • We can use this function in many ways as long as the type is consistent with the declaration. The last one zipWith list of list. ghci> zipWith' (+) [4,2,5,6] [2,6,2,3] [6,8,7,9] ghci> zipWith' max [6,3,2,1] [7,3,1,5] [7,3,2,5] ghci> zipWith' (++) ["foo ", "bar ", "baz "] ["fighters", "hoppers", "aldrin"] ["foo fighters","bar hoppers","baz aldrin"] ghci> zipWith' (*) (replicate 5 2) [1..] [2,4,6,8,10] ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]] [[3,4,6],[9,20,30],[10,12,12]] ## Maps and filters • map take a function and a list and applies that function to every element in the list map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs ghci> map (+3) [1,2,3,4,5] [4,5,6,7,8] • You can do this with list comprehension [x + 3 | x <- [1,2,3,4,5]] • filter is a function that takes a predicate (which is a function that return true or false) and a list and returns the list of elements that satisfy the predicate. filter :: (a -> Bool) -> [a] -> [a] filter _ [] = [] filter p (x:xs) | p x = x : filter p xs | otherwise = filter p xs ghci > filter (>3) [1,2,3,4,5] [4,5] • Again, you can do this with list comprehension [ x | x <- [1,2,3,4,5], x > 3] • find the largest number under 100000 that’s divisible by 3829 largestDivisible :: (Integral a) => a largestDivisible = head (filter p [100000,99999..]) where p x = x mod 3829 == 0 • more general largestDivisible’ with the max limit and the divisor. largestDivisible' :: (Integral a) => a -> a -> a largestDivisible' x y = head (filter p [x,(x-1)..]) where p z = z mod y == 0 • takeWhile function takes a predicate and a list and then goes from the beginning of the list and returns its elements while the predicate holds true. • take the first word of the string “elephants know how to party”. Not equal is /=. ghci> takeWhile (/=' ') "elephants know how to party" "elephants" • find the sum of all odd squares that are smaller than 10000. We use both filter & map or list comprehension to achieve the same result. However, both needed takeWhile as a stopping condition. ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..]))) 166650 ghci> sum (takeWhile (<10000) [n^2 | n <- [1..], odd (n^2)]) 166650 • you can use pure list comprehension to do the same thing without takeWhile but must upper bound the list ghci> sum ([n^2 | n <- [1..10000], odd (n^2), (n^2) < 10000]) 166650 • the following create a list of function and use it by selecting an element from it. The first line create a list of [(0*), (1*), (2*)..] or (Num a) => [a -> a]. ghci> let listOfFunc = map (*) [0..] ghci> (listofFunc !! 4) 5 20 ## Lambdas • Lambdas are anonymous functions that are used because we need some functions only once. chain :: (Integral a) => a -> [a] chain 1 = [1] chain n | even n = n:chain (n div 2) | odd n = n:chain (n * 3 + 1) numLongChains :: Int numLongChains = length (filter isLong (map chain [1..100])) where isLong xs = length xs > 15 numLongChains :: Int numLongChains = length (filter (\xs -> length xs > 15) (map chain [1..100])) • Lambdas is an expression (e.g \xs -> length xs > 15) return a function. • Lambdas can take multiple parameters (e.g. \a b) • Lambdas can use pattern matching but can’t define multiple patterns for the same parameter. Any fall through will result in error. ## Only folds and horses • fold takes a binary function, a starting value and a list to fold up. The type signature foldl :: (a -> b -> a) -> a -> [b] -> a • foldl function (left fold) fold from the left side. The following are equivalent function to sum a list sum' :: (Num a) => [a] -> a sum' xs = foldl (\acc x -> acc + x) 0 xs sum' :: (Num a) => [a] -> a sum' = foldl (+) 0 • any function with signature foo a = bar b a can be rewritten to foo = bar b. elem' :: (Eq a) => a -> [a] -> Bool elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys • foldr function folds from the right side. use accumulator signature (\x acc -> …). • right fold works on infinite list and left don’t. • foldl1 and foldr1 is similar to foldl and foldr except they take the first or last (respectively) value as starting value. Therefore, the same sum function can implement as follow but will have runtime error on empty list sum' = foldl1 (+) • scanl and scanr are like foldl and foldr but create a list of all the intermediate accumulator states. scanl1 and scanr1 are scanl and scanr without using starting value. ## Function application with$

• function application ($) is right associative. Lowest precedence. Consider the following two lines are equivalent.$ replaced parentheses.
sum (map sqrt [1..130])
sum $map sqrt [1..130] • map function application over a list of functions. The following maps 3 to all the function in the list ghci> map ($ 3) [(4+), (10*), (^2), sqrt]
[7.0,30.0,9.0,1.7320508075688772]

## Function composition

• definition: $(f \circ g) (x) = f(g(x))$
• function composition is represented by the period “.” and is right associative. therefore, f(g(h x)) is equivalent to (f.g.h) x. Its implementation is as follow:
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
• For functions with multiple parameters, we must first partially apply them so that each function only take one parameter before being use in function composition.

## Other commands

• To change directory
• :cd
• To use shell commands
• :! (e.g. :!ls to list file)

# Learn You a Haskell for Great Good!

## Hello recursion!

• Do computation in Haskell by declaring what something is instead of declaring how you get it.

## Maximum awesome

• Here is an example of maximum function:
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs)
| x > maxTail = x
| otherwise = maxTail
where maxTail = maximum' xs

•  The function check base or edge condition of empty list and singleton. Then it check if the head is more than the maximum of the rest of the list and recursive through the tail.
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)
• A different representation use max function
$maximum'[2,5,1] = max ~2 \left( maximum'[5,1] = max ~3 \left( maximum[1] = ~1 \right) \right)$

## A few more recursive function

• The take function return the number of element from a list. Take 0 or less will return an empty list
take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
| n <= 0 = []
take' _[]    = []
take' n (x:xs) = x : take' (n-1) xs
• Num is not a subclass of Ord. When doing addition and subtraction and comparison, both are needed.

## Quick, sort!

• In quick sort, take a pivot, x, and put all element smaller than x before x and bigger than x after x.
quicksort' :: (Ord a) => [a] -> [a]
quicksort' [] = []
quicksort' (x:xs) =
let smallerSorted = quicksort [a | a <- xs, a <= x]
biggerSorted = quicksort [a | a <- xs, a > x]
in smallerSorted ++ [x] ++ biggerSorted

## Thinking recursively

• Start with an edge case where the recursion doesn’t make sense and then use function to make a smaller problem that can be solve by the function again.

# Learn You a Haskell for Great Good!

## Pattern matching

• When a function is call, if the function is overloaded with other arguments, it will check from top to bottom until a match is found and return the corresponding value. e.g.
lucky :: (Integral a) => a -> String
lucky 7 = "Lucky number 7!"
lucky x = "Sorry, out of luck."
• Be sure to have something at the end to catch all or it will failed.
• Pattern matching can be use with tuple and list
addVectors :: (Num a) => (a, a) -> (a, a) -> (a, a)
addVectors a b = (fst a + fst b, snd a + snd b)
• [1,2,3] is the same as 1:2:3:[]. Pattern x:xs will bind head of the list to x and rest to xs.
• Use error for exception handling with an message follow it
• Here is a recursive pattern that use for calculating the sum of a numeric list (this pattern is use for a lot of similar recursive function)
sum' :: (Num a) => [a] -> a
sum' [] = 0
sum' (x:xs) = x + sum' xs
• as pattern is a reference to a pattern. The name of the reference is follow by an @. See the example below uses all as pattern name for the whole string.
capital :: String -> String
capital "" = "empty"
capital all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x]

ghci> capital "Dracula"
"The first letter of Dracula is D"

## Guards, guards!

• Guards are indicated by the pipe | and is like a nested if-then-else statement
• Here is an example of compare implementation. Notice it can implement using more than one parameters, use of otherwise is similar to catch all and define the function using infix with backticks.
myCompare :: (Ord a) => a -> a -> Ordering
a myCompare b
| a > b     = GT
| a == b    = EQ
| otherwise = LT

## Where!?

• Where binding let you bind to a variables at the end of a function and the whole function can see them, including all the guards. In this case, bmi, skinny, normal and fat are all constant variables.
bmiTell :: (RealFloat a) => a -> a -> String
bmiTell weight height
| bmi <= skinny = "You're underweight."
...
where bmi = weight / height ^ 2
(skinny, normal, fat) = (18.5, 25.0, 30.0)
• here is a function defined to calculate a list of weight-height pairs and return a list of bmis.
calcBmis :: (RealFloat a) => [(a, a)] -> [a]
calcBmis xs = [bmi w h | (w, h) <- xs]
where bmi weight height = weight / height ^ 2

## Let it be

• Let binding let you bind to variables anywhere and are expressions themselves, but are very local, so they don’t span across guards. The form let <bindings> in <expression> uses the name defined in the “let” part to be use only in the “in” part.
• Use ; to bind several variable inline
ghci> (let a = 100; b = 200; c = 300 in a*b*c, let foo="Hey "; bar = "there!" in foo ++ bar)
(6000000, "Hey there!")
• The let binding inside a list comprehension are visible to the output function (the part before the | ), however, it can’t be used in the first predicate (w, h) <- xs because it defines prior to let. We also omit the “in” part when we use let binding inside list comprehension.
calcBmis :: (RealFloat a) => [(a, a)] -> [a]
calcBmis xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2]

## Case expressions

• case is like switch statement in other imperative languages but more powerful by using pattern matching. Pattern matching uses the fall through rules defined earlier, thus, a catch all case should be there to avoid error.
describeList :: [a] -> String
describeList xs = "The list is " ++ case xs of []  -> "empty."
[x] -> "a singleton list."
xs  -> "a longer list."
• Notice the last line is a catch all.

# Learn You a Haskell for Great Good!

## Believe the type

• Haskell has a static type system
• type of every expression is known at compile time, leads to safer code
• check type for both variable and functions
• :t
• x has type of t
• x :: t
• element in a list must have the same type
• e.g. “HELLO!” :: [Char]
• element in a tuple can have different type
• e.g. (True, ‘a’) :: (Bool, Char) or (‘a’, ‘b’, ‘c’) :: (Char, Char, Char)
• function declaration
• e.g. removeNonUppercase :: [Char] -> [Char]
• mapping string to string
• String is equivalent to [Char]
• function declaration with multiple parameters
• e.g. addThree :: Int -> Int -> Int -> Int
• mapping the first three Int as parameters and the last item as return type
• Some common types and all types start with a Capital letter
• Int stands for Integer but bounded with minimum and maximum values
• Integer stands for Integer also but without bound.
• Float is single precision real floating point number.
• Double is double precision real floating point number.
• Bool is a boolean type (True or False).
• Char is a character.

## Type variables

• type variable is use to represent any type and are usually given names like a, b, c, …
• this mean head operate on a list of type a and return an element of type a.
• e.g. :t fst will result fst :: (a, b) -> a
• this mean fst operate on a tuple pair of type a, b and return an element of type a (the first element of the tuple)

## Typeclasses 101

• typeclasses is a sort of interface that defines some behavior.
• e.g. :t (==) will gives (==) :: (Eq a) => a -> a -> Bool
• Note: == is a function and comprise of only special characters, so it is consider to be infix function by default, use parentheses to call it as a prefix function (e.g. infix a==b vs prefix (==) a b).
• equality function takes any two parameters that are of same type and return a Bool.
• class constraint, =>
• Some basic typeclasses
• Eq typeclass provides an interface for testing for equality
• e.g. == or /=
• Ord  takes two values of same type and returns an ordering.
• e.g. parameter >, <, >= and <=
• To be a member of Ord, a type must first have membership in Eq.
• Ordering is a type that can be GT, LT or EQ.
• Show can be presented as strings. All types covered so far except function are a part of Show. show function deals with the Show typeclass.
• e.g. show 3 gives “3”
• Read is sort of the opposite of typeclass of Show.
• e.g. read “6” – 1 gives 5
• However, read “6” alone will give an error because GHCi cannot infer what type it suppose to be.
• Using explicit type annotations to solve the issue
• e.g. read “6” :: Float gives 6.0
• Enum members are sequentially ordered types.
• e.g. [LT .. GT] gives [LT,EQ,GT]
• e.g. succ ‘B’ gives ‘C’
• Bounded members has upper and lower bound
• e.g. minBound :: Int gives the lower bound of integer (depend on architectural)
• e.g. maxBound :: Bool gives True
• All tuple are also part of Bounded if Bounded components are in it.
• Num is a numeric typeclass. It includes all numbers.
• e.g. :t 20 gives 20 :: (Num t) => t
• To join Num, a type must already be friends with Show and Eq
• Integral is also numeric typeclass that include only whole numbers
• Floating includes only floating point numbers.
• fromIntegral x
• signature of fromIntegral has multiple constraint (Num b, Integral a) => a -> bturn Integral type to more general number
• e.g. length function return Int type instead of Num type

# Learn You a Haskell for Great Good!

• use parentheses for negative number.
• 5 * (-3) instead of 5 * -3.
• binary operation on same type
• True == 5 is not allow because comparing bool with number
• 5 + “llama”is not allow because comparing number with string
• 5 + 4.0 is ok because the 5 adapted to become a floating-point number

## Baby’s first functions

• Infix examples are +, -, *, /, ==, …etc.
• prefix examples are succ, min, … etc.
• function application has highest precedence
• div 92 10 is equivalent to 92 ‘div’ 10
• to load a script (without .hs)
• :l [filename]
• function in Haskell don’t have to be in any particular order
• if then else statement must have an else statement
• ‘ is a valid character for function
• functions can’t begin with uppercase letters
• function without parameter is a definition

## An intro to lists

• homogenous (list of elements of the same type)
• let keyword define a name
• lists are denoted by square brackets []
• a string is just a list of characters (“string”, character – ‘c’)
• combine two lists
• list ++list
• the con operator put an element (not a list) at the beginning of the list
• element : list
• [] is an empty list
• get the x element out of the list where indices start at 0.
• list !! x
• list can also contain list
• return the first element of the list, (e.g. head [5,4,3,2,1] gives 5)
• return the same list but without the head, (e.g. tail [5,4,3,2,1] gives [4,3,2,1])
• tail list
• return the last element of the list, (e.g. last [5,4,3,2,1] gives 1)
• last list
• return the same list but without the tail (e.g. init [5,4,3,2,1] gives [5,4,3,2])
• init list
• return the length of the list
• length list
• check if the list is empty
• null list
• return the same list in reverse order
• reverse list
• return the same list using only x number of the elements from the beginning
• take x list
• return the same list without the x number of the elements from the beginning
• drop x list
• return the sum of a list of numbers
• sum list
• return the product of a list of numbers
• product list
• check whether a is in the list
• elem a  list

## Texas ranges

• to make a list from a to b
• [a .. b]
• to make a list from a to b with step s (e.g. [3,6..20] gives [3,6,9,12,15,18])
• [a,(a+s)..b]
• to make a infinite list with step s
• [a,(a+s)..]
• takes a list and cycles it into an infinite list
• cycle list
• takes an element and produce an infinite list of just that element
• repeat x
• give a list of x elements of a
• replicate x a

## I’m a list comprehension

• a list comprehension that constraint the variable from the criteria before calculating the function of the element into a list. (filtering)
• [function | predicate 1, predicate 2 ..]
• check whether x is odd
• odd x
• _ means we don’t care what we’ll draw from the list

## Tuples

• can contain a combination of several types
• use parentheses () to denoted a tuple
• list of tuple will force the list to use the same tuple type
• takes a pair and returns its first component
• fst tuple
• takes a pair and return its second component
• snd tuple
• combine corresponding elements of both list and put them in a tuple and return a list with the same length as the shorter list
• zip list1 list2
• Example: right triangle
• find the dimension of a right triangle with perimeter equal to 24.
• let rightTriangles = [ (a,b,c) | c <-[1..10], b <-[1..c], a <-[1..b], a^2+b^2==c^2, a+b+c==24]

## Other commands

• quit ghci
• :quit
• to set default text editor
• :set editor [editor]
• to edit a file
• :edit [filename.hs]

# Learn You a Haskell for Great Good!

• Purely functional programming language
• Think of program as a series of transformations on data. Execution of functions and calculations are only done when it is being force to show the result.
• Statically typed with type inference.