Haskell Lecture 6

types, definitions of functions, pattern matching, lists, basic built-in functions and operators: :load, :type (:t), head, tail, length, map, zipWith

-- 3 equivalent definitions of factorial function:
 
-- fact :: Integer -> Integer
fact n | (n==0) = 1
       | otherwise = n * (fact (n-1)) 
 
 
fact' 0 = 1
fact' n = n * (fact' (n-1)) 
 
 
fact'' n = if n==0 then 1 else n * (fact'' (n-1)) 
data Colours = Blue | Green | Red
 
-- Instead of the following construction for a list of Colours: 
data ListColours = Cons Colours ListColours | Empty
-- is better to use the following parametric type:
data List a = Cons a (List a) | Empty
 
-- built-in list: data [a] = a : [a] | []
 
-- example of a binary tree type with values in leafs and nodes
data BinTree a = BinNode a (BinTree a) (BinTree a) | BinLeaf a
 
-- example of an n-ary tree type
data NTree a = NNode a [NTree a] | NLeaf a
-- definition of a built-in function length:
length' [] = 0
length' (_:xs) = 1 + (length' xs)
 
-- some analogy of the built-in length to our type List a:
lenghtList Empty = 0
lenghtList (Cons _ xs) = 1 + (lenghtList xs)
 
head' (x:_) = x -- built-in function (similar to car in Scheme)
tail' (_:xs) = xs -- built-in function (similar to cdr in Scheme)
 
-- definition of a built-in function take:
take' 0 _ = []
take' n (x:xs) = x : (take' (n-1) xs)
 
-- definition of Fibonacci number:
fib' 0 = 1
fib' 1 = 1
fib' n = (fib' (n-1)) + (fib' (n-2))
 
-- definition of sequence of all Fibonacci's numbers:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs) -- here we are using "lazy" evaluation
 
-- definition of a built-in function zipWith:
zipWith' _ [] [] = []
zipWith' f (x:xs) (y:ys) = (f x y) : (zipWith' f xs ys)
 
-- definition of a built-in function map:
map' _ [] = []
map' f (x:xs) = (f x) : (map' f xs)
 
-- definition of a built-in function zip:
zip' [] [] = []
zip' (a:as) (b:bs) = (a,b) : (zip' as bs)
 
-- the following nth function works same as infix built-in (!!)
-- Here we are using the infix notation for binary functions with: `
(x:xs) `nth` 0 = x 
(x:xs) `nth` n = xs `nth` (n-1)
 
[1..100]     -- list of numbers from 1 to 100 with step 1.
[1,3..100]   -- list of odd numbers from  1 to 100 (with step 2)
[2,4..100]   -- list of even numbers from  2 to 100 (with step 2)
[1..]        -- list of all numbers from 1 with step 1
[1,3..]      -- list of all odd numbers from 1 (with step 2)
 
-- non-recursive definition of zip function (using Set construction):
zip'' xs ys = [(xs !! i,ys !! i)|i<-[0..(length xs) - 1]]
 
-- QuickSort in Haskell:
quicksort [] = []
quicksort (x:xs) = (quicksort [e|e<-xs,e<x]) ++ [x] ++ (quicksort [e|e<-xs,e>=x])

Haskell Lecture 7

lambda terms, curryfication, graphical syntax, @, let, where, type classes (class, instance, deriving), basic built-in type classes (Eq, Ord, Num, Show), :info (:i)

-- Example of lambda term
Main> map (\ x -> -x) [1..10]
[-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]
 
-- Example of curryfication of -
Main> map ((-) 0) [1..10]
[-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]
 
-- Example of curryfication of infix -
Main> map (0-) [1..10]
[-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]
 
-- Example of let 
Main> let minus = (0-) in map minus [1..10]
[-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]
 
-- Example of let
Main> let {minus = (0-); ls = [1..10]} in map minus ls
[-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]
 
-- Example of where
Main> map minus ls where {minus = (0-); ls = [1..10]}
[-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]
msort [] = []
msort [x] = [x]
msort ls = merge sas sbs where
        (xs,ys) = split ls where
        	split [] = ([],[])
        	split [x] = ([x],[])
        	split (x:y:ls) = ((x:xs),(y:ys)) where
        		(xs,ys) = split ls
	sas = msort xs
	sbs = msort ys
	merge [] ls = ls
	merge ls [] = ls
	merge ws@(x:xs) zs@(y:ys) | (x<=y) = (x : merge xs zs)
	                          | otherwise = merge zs ws 
 
-- Example:
Main> :t msort
msort :: Ord a => [a] -> [a]
 
Main> msort [6,4,1,3]
[1,3,4,6]
-- automated instantiation of Eq, Ord, and Show class for NTree type using: deriving
data NTree a = NNode a [NTree a] | NLeaf a deriving (Eq,Ord,Show)
 
 
-- Example:
Main> :t NNode 1 [NLeaf 2]
NNode 1 [NLeaf 2] :: Num a => NTree a
 
Main> NNode 2 [NLeaf 2] == NNode 1 [NLeaf 2]
False
 
Main> NNode 2 [NNode 2] <= NNode 1 [NLeaf 2]
False
 
Main> NNode 1 [NLeaf 2]
NNode 1 [NLeaf 2]
data NTree a = NNode a [NTree a] | NLeaf a
 
numberLeafs (NLeaf _) = 1
numberLeafs (NNode _ ls) = sum [numberLeafs x| x <- ls]
 
-- custom instantiation of Eq, Ord, and Show class for NTree type using: instance
instance (Eq a) => Eq (NTree a) where
	x == y = numberLeafs x == numberLeafs y
 
instance (Ord a) => Ord (NTree a) where
	x <= y = numberLeafs x <= numberLeafs y
 
instance (Show a) => Show (NTree a) where
	show (NLeaf x) = "{" ++ (show x) ++ "}"
	show (NNode x ls) = "(" ++ (show x) ++ "@" ++ (show ls) ++ ")"
 
 
-- Example:
Main> :t NNode 1 [NLeaf 2]
NNode 1 [NLeaf 2] :: Num a => NTree a
 
Main> NNode 2 [NLeaf 2] == NNode 1 [NLeaf 2]
True
 
Main> NNode 2 [NNode 2] <= NNode 1 [NLeaf 2]]
True
 
Main> NNode 1 [NLeaf 2]
(1@[{2}])
-- custom definition of some class W with one function w
class W a where
	w :: a -> Bool
 
-- instantiation of class W for type NTree a
instance W (NTree a) where
	w (NLeaf _) = True 
	w _ = False

Haskell Tutorial 7

-- matrix transposition
transp ([]:_) = []
transp m = first_row : transp rest where
	first_row = [(head x)|x<-m]
	rest = [(tail x)|x<-m]
data Natural = Nat Integer deriving (Eq, Show) 
 
instance Num Natural where
  fromInteger i = if i <= 0 then error "Negative natural number!" else Nat i
  (+) (Nat x) (Nat y) = Nat (x + y)
 
misc/projects/oppa_oi_english/courses/ae4b33flp/haskell.txt · Last modified: 2013/10/04 13:02 (external edit)