Cows

....Because trying something new is fun!

What is Haskell?

  • Functional - Given the arguments, always returns the same output ie no global or local state.
  • Lazy
  • Statically typed

Learn you a Haskell

Learn You a Haskell for Great Good the goal of the reading group is to get through this book.

Week 1 is about

  • Getting Started
  • Lists (and list comprehension)

Getting started

REPL

Cows

Running from Powershell GIT in windows

string1 = "hello"
string2 = "world"
greeting = string1 ++ string2

doubleMe x = x + x

-- 6
b = doubleMe 3

-- 16.6  as + works on ints and floating-point numbers
c = doubleMe 8.3

-- * is an infix function which takes 2 numbers and multiplies (as opposed to a prefix)
a = 49 * 100

-- 10/3 gives 1 as a remainder
s = mod 10 3
-- backtick infix style gives 1 as a remainder
t = 10 `mod` 3

-- Cons operator
-- [3,5,7,11]
favNums = 3:5:7:11:[]

Cows

Loading hello.hs and calling functions

  • Ctrl D - exit from GHCI in Powershell
  • Ctrl L - cls

Euler 1

Project Euler is where I start when learning a new language to flex my new ‘toolbelt’..

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

-- 1.  Head of list
a = head [1,2,3]
-- 2,3.  Tail of the list
b = tail [1,2,3]
-- List comprehension (output function is before the pipe)
-- x 'such that', x goes to [1..999]
-- filtering (weeding out lists by predicates)
h = sum [x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]

Cows

running the function h to get the answer. Reloading changes :r in file euler.hs

Euler 2

-- Each new term in the Fibonacci sequence is generated by adding the previous two terms.
-- By starting with 1 and 2, the first 10 terms will be:
-- 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
-- By considering the terms in the Fibonacci sequence whose values do not exceed four million, 
-- find the sum of the even-valued terms.

-- [7,9,11,13,15]
sumOfLists = zipWith (+) [1,2,3,4,5] [6,7,8,9,10]

-- zipWith adds 2 lists together
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

-- [1,1,2,3,5,8,13,21,34,55,89,144,233,377]
q = takeWhile (< 4000000) fibs

--4613732
o = sum [ x | x <- takeWhile (< 4000000) fibs, even x]

Euler 3

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

-- Euler 3
-- The prime factors of 13195 are 5, 7, 13 and 29.
-- What is the largest prime factor of the number 600851475143 ?

-- number is prime if only divisible by 1 and itself
-- http://stackoverflow.com/a/5811176/26086
-- eg if checking isPrime 12
-- 3 * 4 are factors
-- 2 * 6 are factors..
-- one of the factors has to be less than the sqrt
-- and if there is a factor, then it isn't a prime
-- only need check up to the sqrt of number to see if it can be divided with remainder of 0

-- getting the square root as an int
-- x 35 = 5
-- x 144 = 12
x num = floor (sqrt (fromIntegral num))

-- If result set is empty isPrime = True
isPrime num = [x | x <- [2..floor (sqrt (fromIntegral num))], num `mod` x == 0] == []

-- The factors of a number 
facs num =  [x | x <- [3..num], num `mod` x  == 0]
-- [5,7,13,29,35,65,91,145,203,377,455,1015,1885,2639,13195]
q = facs 13195

-- Prime factors
facs' num =  [x | x <- [3..num], num `mod` x  == 0, isPrime x]
-- [5,7,13,29]
q' = facs' 13195

-- Problem is that it doesn't stop after giving the correct answer
-- as its checking all the way up to 600851475143 to see if its a factor
-- [71,839,1471,6857]
r = facs' 600851475143

-- only need to check up to sqrt of 600851475143 to see if it's a factor and a prime
facs'' num =  [x | x <- [3..floor(sqrt (fromIntegral num))], num `mod` x  == 0, isPrime x]
s = facs'' 600851475143

Euler 4

-- Euler 4
-- A palindromic number reads the same both ways. 
-- The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
-- Find the largest palindrome made from the product of two 3-digit numbers.

-- [4,3,2,1]
u = reverse [1,2,3,4]

-- int to string
v = show 345
-- string to int
w = read "345" :: Int

-- can reverse the string (as it is a list of chars really)
u' = reverse "1234"
z = reverse v

-- 9009
t = maximum [x*y | x <- [10..99], y <- [10..99], isPalindrome (x*y)]
-- int to string, reverse int to string ie compare 2 strings
isPalindrome num = show num == reverse (show num) 

-- 906609
t' = maximum [x*y | x <- [100..999], y <- [100..999], isPalindrome (x*y)]

_ and Tuples

-- implementing own version of length (of a list)
-- _ means we don't care what we draw from the list.
-- replace every element of a list with 1, then sum
length' xs = sum [1 | _ <- xs] 

-- 4
o = length' [1,2,3,4]

-- Tuple can contain several types
-- returns first component of the Tuple
-- 8
p = fst (8,11) 
-- "Wow"
q = fst ("Wow", False)

-- Which right triangle that has integers for all sides and all sides equal to or 
-- smaller than 10 has a perimeter of 24?
-- a^2 + b^2 = c^2
-- eg 3,4,5 triangle.. perimeter = 12
-- 9 + 16 = 25

-- generate numbers for all sides returning a Tuple
-- [(6,8,10),(8,6,10)]
r = [(a,b,c) | a <- [1..10], b <- [1..10], c <- [1..10], a^2 + b^2 == c^2, a+b+c==24]

Summary of Book so far

Have been able to solve most of the first 9 Euler problems with just list comprehensions.

-- List comprehension (output function is before the pipe)
-- filtering (weeding out lists by predicates)
a = [x*2 | x <- [1..10], odd x, x > 3]

There are a ton of interesting functions in the language!

BrightonFunctionalReadingGroup

Meetup

Highlights from this meeting were

  • no let needed in REPL now
  • brackets around (+) mean passing + as an argument (actually an infix function to add 2 numbers)
-- zipWith f [a,b,c] [x,y,z]
-- [7,9,11,13,15]
sumOfLists = zipWith (+) [1,2,3,4,5] [6,7,8,9,10]
  • ’ is for single characters, “ is for strings (list of chars!)
aa = 'x'
ab = "this is a string"
ac = length ab
  • such that, is drawn from
-- x such that, x is drawn from 1 to 10
-- filter by odd x's and x>3 
a = [x | x <- [1..10], odd x, x > 3]

Noel Markham’s exercises link

-- Question 1
-- last element in a list
-- 4
ad = last [1,2,3,4]
-- returns everything except the last element
-- [1,2,3]
ae = init [1,2,3,4]

-- Find the penultimate element in list l
penultimate l = last (init l)


-- Question 2
-- determine if list l is a palindrome
-- palindrome is the same forward as reversed

-- l is a list of characters (a string)
isPalindrome l = l == reverse l
-- True
w = isPalindrome "abba"


-- Question 3
--  Duplicate the elements in list xs, for example "duplicate [1,2,3]" 
--  would give the list [1,1,2,2,3,3]
--  Hint: The "concat [l]" function flattens a list of lists into a single list. 
--  (You can see the function definition by typing ":t concat" into the interpreter. 
--  Perhaps try this with other variables and functions)
--  For example: concat [[1,2,3],[3,4,5]] returns [1,2,3,3,4,5]

-- concat the list of lists into a single list
-- [1,1,2,2,3,3]
ag = concat [[1,1],[2,2],[3,3]]

-- returns a list of lists
-- [[1,1],[2,2],[3,3]]
ai = [[x,x] | x <- [1..3]]

duplicate xs = concat [[x,x] | x <- xs]

--[1,1,2,2,3,3]
ah = duplicate [1,2,3]


-- Question 4
-- Imitate the functionality of zip
-- The function "min x y" returns the lower of values x and y
-- For example "ziplike [1,2,3] ['a', 'b', 'c', 'd']" returns [(1,'a'), (2, 'b'), (3, 'c')]
-- ziplike xs ys = undefined

-- use min to get the number of elements
--ab = min ((length [1,2,3]) length(['a', 'b', 'c', 'd']))

-- returns a list of Tuples with the last 'd' missed off as nothing to match
-- [(1,'a'),(2,'b'),(3,'c')]
aj = zip [1,2,3] ['a', 'b', 'c', 'd']

-- find min length of both lists
xs = [1,2,3]
ys = ['a', 'b', 'c', 'd']
-- 2 (3-1)
ak = min (length xs) (length ys)-1

-- x's at element i, y's at element i, such that i is drawn from 0 to the min length of both lists 
ziplike xs ys = [(xs!!i, ys!!i) | i <- [0..(min (length xs) (length ys)-1)]]



-- DG 1 - Factorials
-- the product of an integer and all the integers below it; e.g. factorial four ( 4! ) is equal to 24.

-- 4*3*2*1 = 24

-- recursion
fac n =
    if n < 2
        -- base case of the recursion.. stop at 1
        then 1
        else n * fac (n-1) 
an = fac 4

-- simplicity
fac' n = product [1..n]

ao = fac' 4

-- works
ap = product [1..4]
aq = product [4,3..1]

-- pattern match?
-- same logic as recursion
fact 1 = 1
fact n = n * fact (n-1)
ar = fact 4

-- fold right (higher order fn.. coming to that in the book, so leave for now)
fact2 n = foldr (*) 1 [1..n]
as = fact2 4


-- DG 2 - Fibonacci
-- Each new term in the Fibonacci sequence is generated by adding the previous two terms. 
-- By starting with 1 and 2, the first 10 terms will be:
-- 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

-- write a function to get first 10 fibs

--[1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
--at = fibs 10

-- keep generating fibs.  No base case for recursion
fibs a b =
    --if a > 89
        -- base case of the recursion.. stop at max (eg 89)..return empty list
        --  then [] 
        -- cons operator add a to start of list
        --else a : fibs b (a+b) 
        a : fibs b (a+b)

-- finding the 10,000th fib
at = last (take 10000 (fibs 1 2))
au = (fibs 1 2)!!10000
fibs' n = (fibs 1 2)!!n

-- nice way to test fibs', by throwing a range at it
av = [fibs' x | x <- [1..30]]

-- lazy
fibs'' = 1 : 1 : [x + y | (x,y) <- zip fibs'' (tail fibs'')]

-- zipWith adds 2 lists together
fibs3 = 1 : 1 : zipWith (+) fibs3 (tail fibs3)

Evolution of a Haskell coder