Thursday, September 29, 2005

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

Tuesday, September 27, 2005

Haskell - lecture 3

-- Here's the filter again, this time with "guards".  Guards are like
-- case statements in other languages. The guards are
-- evaluated in order; "otherwise" must come last.
otherFilter :: (a -> Bool) -> [a] -> [a]
otherFilter functionName [] = []
otherFilter functionName (x:xs)
| functionName x = x : otherFilter functionName xs
| otherwise = otherFilter functionName xs

-- This function is intended for use as a filter. It takes one pair
-- as an argument, and returns true if y == 2*x.
-- example use: myFilter doubleSecond [(1,2),(3,4),(5,10)] -> [(1,2),(5,10)]
doubleSecond :: (Int, Int) -> Bool
doubleSecond (x,y)
= y==2 *x

-- Here's another kind of "filter" function: a mapper. It takes a
-- mapping function as an argument, along with a list. It passes
-- each element of the list to the supplied function, and puts the
-- return values in a new list. Example use:
-- myMap (^2) [1,2,3,4] -> [1,4,9,16]
myMap :: (a -> b) -> [a] -> [b]
myMap fn []
= []
myMap fn (x:xs)
= fn x : myMap fn xs

-- The inRange function determines whether a number is
-- in a certain range.
-- The type declaration introduces "Ord". "Ord a" means
-- "any type 'a' that is ordered", i.e. that supports magnitude
-- operators such as > and <. Also notice the new arrow, "=>".
-- It looks like the arrow separates the "interface constraint"
-- on the left with the normal data type declaration on the right.
inRange :: Ord a => a -> a -> a -> Bool
inRange beginning end element
= element >= beginning && element <= end

-- inRange can't be used as a filter directly because it takes 3
-- arguments instead of 1:
-- * myFilter inRange 2 4 [1,2,3,4,5,6] -- wrong
-- However, we can bind the first two arguments, to produce
-- a "new" function that takes only one argument:
-- myFilter (inRange 2 4) [1,2,3,4,5,6] -> [1,5,6]

-- BTW: "zip" takes two lists and makes a list of pairs:
-- zip [1,2,3] ['a','b','c'] -> [(1,'a'),(2,'b'),(3,'c')]
-- zip [1,2,3] "abc" -> [(1,'a'),(2,'b'),(3,'c')]
-- zip [1,2,3,4,5,6] (map (^3) (filter (inRange 2 4) [1,2,3,4,5,6]))
-- -> [(1,8),(2,27),(3,64)]

-- "List comprehensions": a way to generate a finite or infinite
-- list from 1 to 3 parameters. Best explained by example:
-- [1..4] -> [1,2,3,4]
-- [5,4..1] -> [5,4,3,2,1]

-- [5,3.. -5] -> [5,3,1,-1,-3,-5]
-- [2,3.5..7] -> [2.0,3.5,5.0,6.5]
-- [2,3.5..7.5] -> [2.0,3.5,5.0,6.5,8.0] -- strange, eh?
-- [0,10..29] -> [0,10,20]
-- [-2..] -> [-2,-1,0,1,2,...]
-- [2,4..] -> [2,4,6,8,10,12, ...]

-- Here's a list-generating loop construct in Haskell.
ex1 = [x *2 +4 | x <- [1,3..10]]
-- ex1 -> [6,10,14,18,22]
ex2 = [(x,y) | x <- [1..4], y <- [1..4]]
-- ex2 -> [(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)]
ex3 = [(x, x*2+y) | x <- [1,2,3], y <- [4,5,6]]
-- ex3 -> [(1,6),(1,7),(1,8),(2,8),(2,9),(2,10),(3,10),(3,11),(3,12)]
tri m = [(i,j) | i <- [0..m], j <- [0..i]]
-- tri 3 -> [(0,0),(1,0),(1,1),(2,0),(2,1),(2,2),(3,0),(3,1),(3,2),(3,3)]
-- :t tri
-- tri :: (Num a, Enum a) => a -> [(a,a)]

-- Tomorrow: computing prime numbers

Monday, September 26, 2005

ACLU's twisted ideas

Wow.
I am writing to let you know about a vitally important ACLU case that will begin in a few days.

Once again, the ACLU will be defending religious freedom against those who want to force creationism into our public schools. The underlying conflict has been going on at least since the Scopes trial, a famous ACLU case from an earlier era.

At the core, the conflict is between those who believe science should be taught in science classes and those who want to use our public schools to promote one set of religious beliefs over another.

But, this time, the creationists have a new ploy. It's called "intelligent design" -- an "alternative" to the scientific theory of evolution that religious extremists have cooked up as a way to sneak religious proselytizing into our public schools.

...
It is all too clear that powerful political forces are not just tinkering around the edges of our religious freedom -- they have set their sights on transforming our country from a constitutional democracy to a thinly veiled theocracy. They want to turn America into a country governed by their interpretation of the Bible, serviced by faith-based, taxpayer-funded institutions and guided by religious doctrine against which neither citizens nor judges should dare to speak up.

- Anthony D. Romero
Executive Director, ACLU
hmm.
"The consent judgment is repeatedly violated by these individuals because they do not believe anything will happen to them," the ACLU said in its Wednesday court filing. "Their refusal to comply with the consent decree should and must result in their removal from society." (emphasis added)

Thursday, September 22, 2005

CPSC 349: Haskell: 2nd lecture

-- To use Haskell on Windows, download WinHugs from here:
-- http://cvs.haskell.org/Hugs/pages/downloading-Nov2003.htm
-- Commands in the Haskell environment start with a colon:
-- If this code is in test.hs, use command ":l test.hs" to load
-- :t gives the type of something
-- :? gives a list of commands

-- Computes a factorial
fact :: Integer -> Integer
-- Int is 32 bits; Integer is unlimited.
fact 0 = 1
fact (n+1) = (n+1) * fact n

-- Gets the sum of the diagonal of a 3x3 list
-- e.g. diagonal [[1,2,3],[4,5,6],[7,8,9]] = 1+5+9 = 15
diagonal :: [[Int]] -> Int
diagonal [a,b,c] -- type decl. implies a, b, and c are lists of Int
= head a + head (tail b) + head (reverse c)

-- Tuples: complex ordered data type with unnamed elements
-- e.g. (1, 1.0, "1.0", '1', [1])
-- e.g. ("my age in years", 25)

-- 'points' compute the coordinates of a series of integer points
-- along a line, where each point is 1 unit apart horizontally
-- points 8 0 2 4
-- -> [(0,4),(1,6),(2,8),(3,10),(4,12),(5,14),(6,16),(7,18)]
points :: Int -> Int -> Int -> Int -> [(Int, Int)]
points 1 x slope intercept
= (x, x * slope + intercept) : []
points (n+1) x slope intercept
= (x, x * slope + intercept) : points n (x+1) slope intercept

-- "++": Concatenation operator: [1,2] ++ [3,4] -> [1,2,3,4]
-- ":": I don't know what it's called: [1,2] : [3,4] -> [[1,2],[3,4]]

-- You can produce functions from the built-in operators.
-- Examples:
-- (2/) is a function that divides 2 by something, so (2/) 4 -> 0.5
-- (/2) is a function that divides something by 2, so (/2) 4 -> 2.0
-- (/) is the division function: (/) 21 3 -> 7.0
-- Another example: ([1,2]++) [3,4] -> [1,2,3,4]

-- This function uses the output of another function as a "filter".
-- The filter determines whether to keep an element of the list.
myFilter :: (a -> Bool) -> [a] -> [a]
myFilter functionName [] = []
myFilter functionName (x:xs) =
if functionName x then
x : myFilter functionName xs -- Keep 'x' in the output list
else myFilter functionName xs -- Discard 'x'
-- Example:
-- myFilter (>4) [1,8,2,7,3,6,4,5] -> [8,7,6,5]
-- myFilter

Tuesday, September 20, 2005

Haskell sample

About haskell haskell.org
-----------------
len :: [a] -> Int
len []
= 0
len (a : rest)
= 1 + len rest
-----------------
everyThird :: [Char] -> Int
everyThird [] = []
everyThird (x:y:z:xs) = x : everyThird xs
everyThird (x:y:xs) = []
everyThird (x:xs) = []
-- Um, whouldn't these be ambiguous? [1,2,3] ought to match x:xs and x:y:xs and x:y:z:xs, cxu ne?
-- Result of everyThird "classroom" : "arm"
-----------------
To load a file: :l filename.hs
To get the type of something: :t 123
output: 123.0 :: Int