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))
--