— CPSC 312 – 2021 – Lazy Computation in Haskell
module Lazy where
— To run it, try:
— ghci
— :load Lazy
add1y x y = y+1
add1x x y = x+1
— foldr add1y 0 [7..9]
m x y = x*y
inf = 1+inf
inlst = 1:inlst
— try:
— take 20 inlst
sq x = x*x
sqr = \x -> x*x
lstto 0 = []
lstto n = n:lstto (n-1)
mysum [] = 0
mysum (h:t) = h+mysum t
— mysum (lstto 5)
myzip (h1:t1) (h2:t2) = (h1,h2) : myzip t1 t2
myzip _ _ = []
dotprod l1 l2 = sum [n1*n2 | (n1,n2) <- zip l1 l2]
-- dotprod [1000000,999999..] [1..1000000]
-- primes is the list of all primes
primes = sieve [2..]
where -- sieve is the list of all primes given previous primes have been removed
sieve (p:xs) =
p : sieve [x | x <- xs, x `mod` p /= 0]
-- take 20 primes
-- fib n = fib (n-1) + fib (n-2)
-- 1 1 2 3 5 8 13
-- pow x op n = x op x op x... op x (n times)
-- use x^n = (x^2)^(n/2) if n is even
pow x _ 1 = x
pow x op n
| even n = pow (sq2 op x) op (n `div` 2)
| otherwise = op x (pow x op (n-1))
-- sq2 squares its argument using op
sq2 :: (t -> t -> t) -> t -> t
sq2 op x = op x x
— An alternative pow, using x^n = (x^(n/2))^2 is n is even
— pow2 x op n = x op x op x… op x (n times)
pow2 x _ 1 = x
pow2 x op n
| 0 == n `mod` 2 = sq2 op (pow2 x op (n `div` 2))
| otherwise = op x (pow2 x op (n-1))
— powlin x op n = x op x op x… op x (n times) but using linear number of op’s
powlin x _ 1 = x
powlin x op n = op x (powlin x op (n-1))
— pow 1.000000000001 (*) 1000000000000
— pow 3 (+) 10
———————————–
— Fibonnacci
— A matrix a function from 2 indexes into a value
type Matrix t = Int -> Int -> t
— we will use a 2×2 matrix where the values are Integers
type Matrix22 = Matrix Integer
— m1110 is a particular 2×2 matrix
m1110 :: Matrix22
m1110 2 2 = 0
m1110 _ _ = 1
— mm is matrix multiplication for 2×2 matrices
mm:: Num t => Matrix t -> Matrix t -> Matrix t
mm m1 m2 i j = sum [(m1 i k)*(m2 k j) | k <- [1..size]]
size = 2
m2 = mm m1110 m1110
m4 = mm m2 m2
m8 = mm m4 m4
-- m8 1 1
-- find the nth Fibonnacci number
fib n = pow m1110 mm n 2 1
fib2 n = pow2 m1110 mm n 2 1
-- Try
-- fib 125
-- fib 1000
-- fib2 125
-- fib2 1000
-- Alternative defintion of the list of all Fibonnacci numbers
fibs = 0:1:(zipWith (+) fibs (tail fibs))
-- fibs !! 200000
-- show a matrix in a linear form (for playing)
prm mat = [mat 1 1, mat 1 2, mat 2 1, mat 2 2]
-- prm (pow m1110 mm 3)
sqm = sq2 mm
-- prm (sqm m1110)
-- prm (sqm (sqm ( sqm (m1110))))
-- prm ((sqm . sqm . sqm) m1110)
-- prm ((sqm . sqm . sqm . sqm) m1110)
-- prm (sqm . sqm . sqm . sqm $ m1110)
-- prm $ sqm . sqm . sqm . sqm $ m1110
--- niave reverse
nrev [] = []
nrev (h:t) = nrev t ++ [h]
-- try in ghci:
-- :set +s
-- length (nrev [1..10000])
-- length (nrev [1..20000])
-- elem 5 ([1..100000000000000]++[1..])
data APerson = Person String Int
showPerson (Person name age) = name ++ " " ++ show age
sam = Person "Sam" 27
-----
data FValue = BooleanF Bool
| NumberF Int
| StringF [Char]
| MissingF
data MyListInteger =
Empty
| ConsI Integer MyListInteger
deriving Show
-- append for MyListInteger
myApp :: MyListInteger -> MyListInteger -> MyListInteger
myApp Empty lst = lst
myApp (ConsI h t) lst = ConsI h (myApp t lst)
— myApp (ConsI 1 (ConsI 2 Empty)) (ConsI 4 (ConsI 5 Empty))