Programming Paradigms - Informationsteknik

�vningar

Tentasvar

ProgrammingParadigmsDecemberNollSju

ProgrammingParadigmsMarsNoll�tta

ProgrammingParadigmsAugustiNoll�tta

Links

Haskell + ghc tutorial

http://book.realworldhaskell.org/read/types-and-functions.html

1. lambda-calculus

1.1 Some easy Haskell functions

L = lambda
inc (Lx. x + 1)
twice (Lf. Lx. f x)
-- arg1: an integer
inc = \ x -> x + 1

-- arg1: a function
-- arg2: an integer
twice = \ f -> \ x -> f (f x)

1c)

(Lx. x)(Lx. x) = > (Lx. (Lx. x)) = > (Lx. x) => x

2a)

(Lf. Lx. x)

2b)

(Lf. Lx. f x)

2c)

type Church a = (a -> a) -> a -> a
church :: Integer -> Church a
church 0 = \ f -> \ x -> x
church n = \ f -> \ x -> f ( church(n - 1) f x)

unchurch :: Church Integer -> Integer
unchurch n = n (\ x -> x + 1) 0

2. Lecture 2008-10-31: His crazy live example (not tested)

head [1,2,3] -- Takes first part of list
tail [1,2,3]


--cons
a: [2,3] -- Gives [1,2,3]

[1,2] ++ [3,4] -- [1,2,3,4]

-- Range
[1..10] -- List 1 to 10
[1..] -- Infinite


take 10 [1..] -- Take first 10 elements in infinite litst

-- Strings
"Hello" -- List of chars
head "hello" -- Gives 'h'

"hello " ++ "world" -- Appents two lists of chars

[ i*i | i <- [1..10] ] -- Iterate over list, take element i, square it

-- Define function

----------------------------------------
module Lecture where

-- read | as where
squares n = [i*i | i <- [1..n]]
         -- {i*i | i <- {1..n}}   (Math representation)

-- :l Lecture
-- squares 4

----------------------------------------

-- (i,j) is pair/tuple
[(i,j) | i <- [1..10], j <- [1..i]] -- Loop j is nested in loop with i

[i | i <- [1..24], 24  `rem` i == 0] -- �rem� call rem function with args 24 and i
-- List of divisors to 24

----------------------------------------
factors n = [i | i <- [1..n-1], n `rem` i == 0]
prime n = factors n == [1]

[p \ p <- [1..100], prime p]


--- QuickSort
qsort (x:xs) = 
  qsort [y | <-  xs, y < x] ++ [x] ++
  qsort [y | <- xs, y >= x]

qsort [] = []
----------------------------------------

qsort [10, 9..1]
qsort "hello world"
qsort (words "I need a sentance, what shal i use")



-- Add numbers 1 to 10
foldl (+) 0 [1..10]
foldl (*) 1 [1..10]

foldl (&&) True [True, False, True]
foldl (++) [] (words "hello clounds hello sky")

----------------------------------------
plus x y =  "(" ++x++"+"++y++")"
----------------------------------------

plus "12" "13"

"12" `plus` "13"
"12" `plus` "13" `plus` "14"

-- We can see what foldl does...
foldl plus "z" ["a", "b", "c", "d"]


-- Does stuff the other way...
foldr plus "z" ["a", "b", "c", "d"]


-- Multiply by 10, add digit, repeat
foldl (\ x y ->10*x+y) 0 [1, 3, 4, 2]

----------------------------------------
import Char
digitVal d = ord d - ord '0'

-- Convert from char to int
numVal s = foldl (\ x y -> 10*x+y) 0 [digitVal c | c <- s ]
----------------------------------------
numVal "132" -- Gives 132


----------------------------------------
-- :l Calc
calc "123"
calc "1+2"
calc "1+(2*3)"

----------------------------------------
-- Input : String, Result: digit
-- Extracts digit from string
digit (x:xs) = 
  if isDigit x
  then [x]
  else []

----------------------------------------
digit "123"
-- "1"

digit "abc"
-- ""

----------------------------------------
-- Same as first def
digit (x:xs) = [x | isDigit x]
letter (x:xs) = [x | isAlpha x]
----------------------------------------

letter "123"
-- ""

----------------------------------------
digitOrLetter s = digit s  ++ letter s
----------------------------------------

digitOrLetter "asd"
-- "a"
digitOrLetter "123"
-- "1"


----------------------------------------
-- Defines new operator '|||', looks for stuff in p and q
p ||| q = \s -> p s ++ q s

-- Refactor code above:
digitOrLetter s = (digit ||| letter) s -- constructs function in place..

-- Simplify: 
digitOrLetter = digit ||| letter

-- Simplify old stuff:
satisfy p (x:xs) = [x | p x]

--Refactor:
digit = satisfy isDigit
letter = satisfy isAlpha
----------------------------------------

-- Constructs functions in intepreter
(satisfy isDigit | satisfy isAlpha) "123"

(satisfy isDigit | satisfy isAlphaNum) "123"
-- "11"

digit ""
-- Program error...

----------------------------------------
satisfy p (x:xs) = [x | p x]
satisfy p []     = []
----------------------------------------

-- Satisfy function that checks args == plus
satisfy (=='+') "+123"
-- "+"

----------------------------------------
exactly c = satisfy (==c)

satisfy p (x:xs) = [(x,xs) | p x]
satisfy p []     = []

-- s' is variable name, prime ok.
digitThenPlus s = 
  [((d, '+'), s'') | (d,s') <- digit s, 
                     ('+', s'') <- exactly '+' s']
----------------------------------------

digitThenPlus "1+2"
-- [(('1', '+'), "2")]

digitThenPlus "a+2"
'' []



----------------------------------------
p ... q = \s -> 
  [((x, y), s'') | (x,s') <- p s, (y,s'') <- q s']

digitThenPlus = digit ... exactly '+'
----------------------------------------


----------------------------------------
-- Wtf....
p @@ q = \s -> 
  [(x y,s'') | (x,s') <- p s, (y,s'') <- q s']

value x s = [(x,s)]
----------------------------------------

(value digitVal @@ digit) "132"
-- [(1,"32")]

----------------------------------------
digits = value (:) @@ digit @@ digits
     ||| value []
----------------------------------------

digits "123x"
-- "It works..."


----------------------------------------
-- "Hey that sounds useful, lets refactor my code"
many p = some p ||| value []
some p = value (:) @@ p @@ many p

digits = some digit
number = value numVal @@ some digit
----------------------------------------

number "123x"

----------------------------------------
numPlusNum = 
  value addition @@ number @@ exactly '+'  @@ number

addition x '+' y = x+y
----------------------------------------

numPlusNum "1+2"


----------------------------------------
infixl 6 @@, ##
infixl 5 |||

numPlusNum = 
  value (+) @@ number ## exactly '+' @@ number

p ## q = value (\x y->x) @@ p @@ q
----------------------------------------

numPlusNum "1+2"

----------------------------------------
expr = value (+) @@ term ## exactly '+' @@ term
  ||| term

term = value (+) @@ factor ## exactly '+' @@ factor
  ||| factor

factor = 
 ||| value id ## exactly '(' @@ expr ## exactly ')'

parse p s = 
  [x | (x, "") <- p s]
----------------------------------------

expr "1+2*3"
parse expr "1+2*3"

3. Lecture 2008-11-06: More haskell

-- haskell requires the elements of a list to have the same type
[1, 2.0]
-- [1.0, 2.0]

-- information about (+)
:i +

-- a as input has to be a Numeric type
-- a can be any type, Integer, Float etc.

-- information about Num
:i Num

-- Num is a class
-- Num depends on two other classes
-- any type in class Num has to provide support for all the operators listed here
-- instances of Num: Int, Integer, Float, Double etc.

-- test the sort function
:l List
sort [1,4,3,2,5]
-- [1,2,3,4,5]

-- so, we can sit here and test functions manually,
 but what we would like to is to automate this.

	module Lecture where
	import List
	
	-- function to test wheter or not a list is ordered
	ordered (x:y:xs) = x <= y && ordered (y:xs)
	ordered _ = True -- true if 0 or 1 element
	
ordered (sort [1,4,2,3])
-- True

	prop_sort xs = ordered (sort xs)

prop_sort [1,3,5,4]
-- True

	import Test.QuickCheck
	
	prop_sort (xs::[Integer]) = ordered (sort xs)
	-- the reason of putting [Integer] here is to tell quickCheck
what type of elements to test
	
quickCheck prop_sort
-- OK, passed 100 tests.
-- what happened was that quickCheck created 100 randomly generated test cases,
and they all passed
-- a random test case technique has become very popular,
it's quick to create them (it creates them itself)
	
	prop_insert (x::Integer) xs = ordered (insert x xs)
	
quickCheck prop_insert
-- Falsifiable, after 5 tests:
-- -1
-- [0, -1]
-- hmm, why this?! let's try it manually:

insert (-1) [0, -1]
-- [-1, 0, -1]
-- ok, well our definition of prop_insert is wrong

	prop_insert (x::Integer) xs = ordered xs ==> ordered (insert x xs)
	-- ==> means what?
	-- it's a conditional property to in this case check if the list is ordered

-- now, quickCheck will pass 100 tests.
-- quickCheck can also collect stats from testing

	prop_insert (x::Integer) xs =
		collect (length xs) $
		ordered xs ==> ordered (insert x xs)	
	
quickCheck prop_insert
-- 49% 0. (empty lists)
-- 32% 1. (one element)
-- 9% 2.
-- 8% 3.
-- 2% 4.
-- this feels like wrong balance
-- why did we test empty lists and 1-element lists so much?
because they always pass the precondition
-- the chance for longer lists to already be ordered is pretty low,
that's why we threw away so many of them

	orderedList :: (Ord a, Arbitrary a) => Gen [a]
	orderedList =
		do xs <- arbitrary
			return (sort xs)
			
	prop_insert2 x =
		forAll orderedList
			(\xs -> prop_insert x xs)
			
quickCheck prop_insert2
-- now we get a much more variety in the length of the test lists
-- why?
-- but ok, why do we actually use the sort function within prop_insert?
-- let's write another version that doesn't use sort()

	orderedNumList :: (Num a, Ord a, Arbitrary a) => Gen [a]
	orderedNumList =
		do x <- arbitrary
			listFrom x
	
	listFrom x =
		frequency [(1, return []),
				(5, do diff <- arbitrary
					xs <- listFrom (x+abs diff)
					return (x:xs))]

	prop_insert3 x =
		forAll orderedNumList $ \xs ->
			prop_insert x xs
			
quickCheck prop_insert3


-- now we're gonna do something called PROPERTY DRIVEN TESTING (using quickCheck)
-- we're gonna implement functionality for a queue

	instance QueueCLass Queue where
		empty = []
		add x xs = xs ++ [x]
		del (x:xs) = xs
		front (x:xs) = Just x
		front [] = Nothing 

-- he's not gonna test it because he's not satisfied
-- ++ is a damn slow operation, and he wants something better
-- any ideas why keeping the slow code? it's testable, we use it to test the real code
-- we can split the queue into two parts, ehrm...
-- he's gonna do it like a zig-zag airport queue

	data Queue a = Q [a] [a]
		deriving (Eq, Show)
		
	instance QueueClass [] where
		empty = Q [] []
		add x (Q front back) = Q front (x:back)
		-- he's storing the back in reverse order, so when we add we can put it
at the front of the list, which is gonna be fast
		-- when we delete, we take it from the front, an
		del (Q (x:front) back) = flipQ (Q front back)
		front (Q (x:front) back) = Just x
		front (Q [] back) = Nothing
	
	flipQ (Q [] back) = Q (reverse back) []
	flipQ (Q front back) = Q front back
	
-- but now we have the same name of the functions and haskell won't let me have that,
let's introduce a class and add "instance" to the above blocks

	class QueueClass q where
		empty :: q a
		add :: a -> q a -> q a
		del :: q a -> q a
		front :: q a -> Maybe a
		
	model (Q front back) = front ++ reverse back
	
-- now we want to test this code
	
	prop_empty = model empty == empty &&
		invariant (empty)
	
	-- these two empty's mean two different things because we used the model
function to convert between the first type of queue and the more efficient one

quickCheck prop_empty
-- OK, passed 100 tests.

	prop_add x (q::Queue Integer) =
		model (add x q) == add x (model q)

quickCheck prop_add
-- error, let's have a break
-- ok, we needed this:

	instance Arbitrary a => Arbitrary (Queue a) where
		arbitrary =
			do front <- arbitrary
			   back <- arbitrary
			   	return (Q front back)
			   	
-- now prop_add works!

	prop_front (q:: Queue Integer) =
		front q == front (model q)

-- testing of prop_front fails
-- because there was an invariant in our implementation
(add invariant-stuff to all the prop_x's?)

	invariant (Q frot back) =
		not (null front) || null back
		
	prop_add x (q::Queue Integer) =
		invariant q ==>
			model (add x q) == add x (model q) &&
				invariant (add x q)

-- yes, now the front is working 

	prop_del x (q::Queue Integer) =
		invariant q && q\=empty ==>
			model (del q) == del (model q) &&
				invariant (add x q)