### Haskell - lecture 4

--

-- What's this?

interleave x [] = [[x]]

interleave x (y:ys)

= [x:y:ys] ++ map (y:)(interleave x ys)

perms [] = [[]]

perms (x:xs)

= [ zs | ys <- perms xs, zs <- interleave x ys ]

-- Back to prime calculation. Note: /= means "not equal to"

crossOut :: Int -> [Int] -> [Int]

crossOut m ns = [ n | n <- ns, (n `mod` m) /= 0] -- Could also use "mod n m"

-- Excludes non-prime numbers from a list. Must be [2..] or a list of the form [2..n]

seive :: [Int] -> [Int]

seive [] = []

seive (x:xs)

= x : seive (crossOut x xs)

-- output of seive [2..50]

-- -> [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

-- Finds a bunch of integers satisfying a^2 + b^2 == c^2

-- What's interesting about this example is that it is slow: n^3

-- 50x50x50 = 125,000 iterations; takes about 20 seconds @ 1.6GHz

-- Other languages would do it faster.

triads = [(a,b,c) | a <- [1..50], b <- [1..50], c <- [1..50], a^2 + b^2 == c^2]

-- type: [(Integer,Integer,Integer)]

-- output: [(3,4,5),(4,3,5),(5,12,13),(6,8,10),(7,24,25),(8,6,10),(8,15,17),(9,12,15),(9,40,41),(10,24,26),(12,5,13),(12,9,15),(12,16,20),(12,35,37),(14,48,50),(15,8,17),(15,20,25),(15,36,39),(16,12,20),(16,30,34),(18,24,30),(20,15,25),(20,21,29),(21,20,29),(21,28,35),(24,7,25),(24,10,26),(24,18,30),(24,32,40),(27,36,45),(28,21,35),(30,16,34),(30,40,50),(32,24,40),(35,12,37),(36,15,39),(36,27,45),(40,9,41),(40,30,50),(48,14,50)]

-- The quicksort (using first-element pivot)

-- Here are two implementations.

quicksort :: Ord a => [a] -> [a]

quicksort [] = []

quicksort (x:xs)

= quicksort [y | y <- xs, y <>= x]

-- = quicksort (filter (=x) xs)

-- You can sort numbers but also pairs:

-- quicksort [(1,3),(6,3),(2,4),(2,0),(6,1)] -> [(1,3),(2,0),(2,4),(6,1),(6,3)]

-- All operators can be expressed in prefix form.

-- (+) 1 2: 3

-- :t (+): (+) :: Num a => a -> a -> a

-- :t (^): (^) :: (Num a, Integral b) => a -> b -> a

-- This is interesting:

-- :t (^2): flip (^) 2 :: (Integral a, Num b) => b -> b

-- ((flip (^)) 2) 3: 9

-- This function performs an operation on a collection of elements like so:

-- myfoldr (+) 1 [2,3,4] == 1 + (2 + (3 + 4))

-- Note the right-first evaluation.

myfoldr :: (a -> b -> b) -> b -> [a] -> b

myfoldr fn b []

= b

myfoldr fn b (x:xs)

= fn x (myfoldr fn b xs)

myfoldr1 :: (a -> a -> a) -> [a] -> a

-- myfoldr1 is meaningless on an empty list: show error message

myfoldr1 fn [] = error "applied to empty list"

myfoldr1 fn [x] = x

myfoldr1 fn (x:y:xs) -- x:y:xs guarantees it matches only lists with at least 2 items

= fn x (myfoldr1 fn (y:xs))

--