COMP1100
Assessment
Weekly lab submissions 5%
Assignment 1 20% assignment 2 20%
Mid-term exam 15%; final exam 40%
Tips of requirement
Advanced hurdle – 60% in midterm exam
Discrete mathematical models
Skills: assignments; exercises on textbook; past exam questions on the website
*Consultation: piazza.com/anu.edu.au/fall2020/comp1100comp1130
Hanna Neumann Lab1.23 4-5pm workdays
Miscellaneous resources -,,,
Week1 lecture programming as problem solving
– define the problem 1. what is input and output?
• what constraints must be satisfied?
• What information is essential?
– develop a solution 1. construct an algorithm – read in amount in US dollars; calculate the AU dollars amount; display the result
Function name: usd2aud :: Double -> Double
Usd2aud x = rateUS2Au * x where rateUS2Au = 1.4
Main :: IO( )
Main = do
IO -> CPU – > memory
2. implement a program
– complie test and debug the program
– document and maintain the program
Conversions
• divide number by base to which you are converting
• Prepend remainder to the result string
• Replace number by quotient
• Repeat until quotient is zero
Finite precision 有限的精准度
Computers store numbers using bits
Bits organized into bytes
Bytes organized into words, typically 4bytes (32 bits ) or 8 bytes (64bits)
Week1 lecture1intro sets and function [textbook] 13/3 22:40
*Preview:
范畴论? reading
Expression + declaration
Expression has value e.g.
(1)3 :: Float – ::表示3的类型,浮点数是3
(2)Sort 「3,8,1,4」排序函数
(3)lexical 词法
*If … then…else
*Case …of…, e.g. case Foo of True -> 1
False -> 2 表达式的值在Foo是True的时候为1, False则为2.
*let…in… 可以把复杂的表达式重组,还可以把重复计算的部分提取出来 e.g. ,,,(有点像where)
Declaration
addOne :: Int -> Int —- x的区域叫作x的作用域scope
addOne x = x + 1
welcomeMsg :: String – welcome message是类型是string
welcomeMsg = “hello world” – binding在左侧的名称上
* Haskell不存在变量只存在绑定 任何时刻一个名称对应的表达式都是唯一确定的
E.g. addOne 3 —- 3+1 = 4
程序的入口
module main where
Ismport Data.List
main :: I0()
main = print ( nub [1,2,3,2,3] )
Lecture 1
Set and function
A set (a collection of things) of elements; no order; unique element (appears only once)
A singleton {}
Booleans {False, True} — two elements
Use indicator range {1,2,…,100}
Infinite sets:
Natural numbers N {0,1,2,…}
Integer Z {…, -2, -1, 0 , 1, 2}
Real number R ???
String: list of characters of any finite length
Combing set : product
Every possible pairs can be constructed
Combining set : sum
Two sets A and B, form a new set A + B by combining
Week 1 Haskell
CS, fundamentals of algorithms and programming as means of problem solving
2/27
Sets and functions
– a collection of things, called its elements, have finitely many elements. so can be listed
Natural numbers, integers, real numbers, the strings: lists of characters of many finite length
– combining sets: product,,,
– combining sets: sum A+B disjoint union
Functions
– set A called domain (inputs)
– set B called codomain (possible outputs)
f :: A -> B ,,,f (a) = b
Polymorphic functions – a function that can be defined simultaneously for many different sets is called polymorphic
Identity id :: A -> A defined as id (a) = a,
constantzero :: B -> Z defined as constanzero (b) = 0
Week 1 – 1130
What is a computer? ,,,human interaction
ANUC 1100
What is haskell? A pure functional programming language (pure- no side effect)
Imperative vs. declarative
Imperative: tell the program how to do sth (program is a sequence of instruction)
Decarative: tell the program what you like to happen (not how to do it)
Import Data.Char
textToUpper :: [Char] -> [Char]
textToUpper txt = case txt of
[] -> []
c: cs -> toUpper c : textToUpper cs
Fibonacci Sequence 斐波纳契数列
Rich picture – human activity systems
A purposeful system of activities,,,
Interpreter vs. Compiler
Control flow: imperative / declarative 命令型/陈述型
How to programming?
Declarative – functional/ logic/ finite state machines
Allocations and bindings – static and dynamic
Time: event-driven/ discrete/ synchronous/ continuous
Focus: control flow / data flow
Concurrency: sequential/ concurrent/ parallel/ distributed 串行/ 并发/ 并行/ 分布式
Structure: modular/ generics/ templates/ objects/ aspects/ agents
Determinism: deterministic/ non-deterministic
Haskell is functional – function are first-calss, that is functions are values which can be used in exactly the same way as any other sort of value. Haskell program is centered around evaluating expressions rather than executing instructions.
Haskell is pure – referentially transparent, expressions are side-effect free, programs are deterministic – calling the same function with the same arguments results in the same output; no mutation, everything is immutable,,,
Haskell is lazy – expressions are not evaluated until their results are needed
It is possible to define and work with infinite data structures
Basic types: booleans, characters, strings,,,
&& // not(negation)
??? – boolean function definition “exclusive or”
exOr :: Bool -> Bool -> Bool
exOr x y = (x // y) && not (x && y)
Char: character
Integer – operation : + / */ – ; ^ ; div ; mod ; abs ; negate
Double – type double can be used to represent number with fractional parts (double-precision floating-point numbers) there is a fixed amount of space
Data singleton = LonelyElement
lonelyToZero :: Singleton -> Int
lonelyToZero LonelyElement = 0
allToLonely :: Int -> Singleton
allTolonely _ = lonelyElement
data Bool = True | False
Data Color = Red | Green | Blue | Indigo | Violet
deriving(Show, Eq)
Data Move = Rock | Paper | Scissors
whoWins :: Move -> Move -> Bool
whoWins a b = a
data IntPlusBool = Left Int | Right Bool
Data IntPlusIntPlusBool =
First Int | Second Int | Third Int
Maybe
data Maybe a = Just a | Nothing deriving (Eq, Ord)
Maybe Int = Just Int | Nothing
myNot :: Bool -> Bool
myNot b =
case b of
True -> False
False -> True
myAbs :: Int -> Int
myAbs x =
case x>=0 of
True -> x
False -> -x
myAbs x
| x >= 0 = x
| otherwise = -x
&&
Data Bool =True | False
myAnd :: Bool-> Bool -> Bool
myAnd b c =
case (b, c) of
(True, True) -> True
#(True,False) -> False
#(False, True) -> False
#(False, False) -> False
_ -> False
Data Animal = Cat | Dog | Cow
says :: Animal -> String
Says x =
case x of
Cat -> “meeow”
Dog -> “woof”
Cow -> “moo”
Parrot name -> “pretty”++name
myNotG :: Bool -> Bool
myNotG bg
|bg==True = False
|bg==False = True
myAbsG :: Int -> Int
myAbsG n
|n>=o = n
|n<0 = (-n)
myAndG :: Bool -> Bool -> Bool
myAndG a b
|a==True && b==True = True
(|a==True && b==False = False
|a==False && b==False = False
|a==False && b==False =False)
|otherwise = False
myAndP :: Bool -> Bool -> Bool
myAndP True True = True
myAndP _ _ = False
Introduction to List
Recursive Type
A recursive type is one whose definition makes mention of the type itself
This sounds circular but also very useful 递归的
myHead :: [Int] -> Maybe Int
Myhead l =
case l of
[] -> nothing
x:xs -> Just x
myTake :: Int -> [Double] -> [Double]
myTake n ls = case ls of
[ ] -> [ ]
m:ms -> m : (myTake (n-1) ms)
myTake :: Int -> [Double] -> [Double]
myTake n xs = case n of
0 -> []
m -> head xs : takeDoubles (m-1) (tail xs)
1: ( take 2 [2, 3] ) = 1: 2: (take 1 [3] )
[1, 2, 3]
Recursion –
addmultiply :: Int -> Int -> Int
addmultiply n x = case n of
1 -> x
n -> x + addmultiply (abs(n)-1) x
Mutual recursion
is Even :: Integer -> Bool
is Even n
| n == 0 = True
| otherwise = isOdd (n-1)
isOdd :: Integer -> Bool
isOdd n
| n == 0 = False
| otherwise = isEven (n – 1)
myLength :: [Int] -> Int
myLength xs = case xs of
[ ] -> 0
m -> 1 + myLength (tail m)
addZero :: [Int] -> [Int]
addZero xs = 0:xs
startWithZero :: [Int] -> Bool
startWithZero xs = case xs of
[ ] -> False
m:ms -> m==0
isEmpty :: [Int] -> Bool
isEmpty xs = case xs of
[ ] -> True
_ -> False
or: isEmpty xs = xs == [ ]
myLength :: [int] -> Int
myLength xs = case xs of
[ ] -> 0
ms -> 1 + myLength (tail ms)
squareAll :: [Int] -> [Int]
squareAll xs = case xs of
[ ] -> [ ]
ms -> (head ms)^2:sqaureAll (tail ms)
minimum :: [Int] -> Int
Minimum xs = case xs of
[ ] -> error”empty list”
[x] -> x
x:y:ys -> myMinimum ((min x y):ys)
least :: [Double] -> Double
least xs = case xs of
[ ] -> error”empty list”
[x] -> x
y:ys
|y < least ys -> y
|otherwise -> least ys
myProductRight :: [Double] -> Double
myProductRight l = case l of
[ ] -> 1.0
x:xs -> x* myProductRight xs
Zip
zip :: [Int] -> [Char] -> [(Int, Char)]
Lecture3 Part B
Recursion properties
In the direction,,, maybe the same maybe change (each instance size)
Desirable properties from a programming point of view
The definition of iteration is asking function call to do the same thing for several times
While recursion is fundamental in functional programming (no iteration)
How to solve problem with recursion
Base case – problem solving into very small pieces of data-write code without using recursion
Step case – at certain scale – solve bigger versions of the problem, with recursion call
*must have base case – defining the value for which the function is evaluated without recursively call itself — then each step case should lead base cases
How write a good technical reporting?
Documentation
– what do your functions do (conceptually) ?
– how do they work together ? overall structure ?
– what design choices have you made ?
– what assumptions did you make ? how did they change your design ?
Reflection
– Why did you solve problems the way you did ?
– What factors influenced your design decisions ?
– how did different tradeoffs or assumptions affect your program ?
– Where there any conceptual or technical problems ?
– if you solved them, how?
– if you didn’t, what do you think the problem was? How could you solve it ? What did you try?
Introduction
The program is totally design to draw of shapes into picture by using code world function. In controller, the program shows different events of key press and key release which are used to starting drawing. Then there are nextColor and nextTool functions as tools to change shape color and drawing tool.
In addition, in view there are function being used to label the tools and also there are several steps being used to convert shape to pictures.
Content
The way I structure the program is interacting shape program by writing helper function, rendering shapes, and handling events respectively.
The first task is to using helper function such as label tools and changing next tools.
In addition, the second task is to convert types from model to picture in a way of modeling colorShapesToPicture. To explain, there is a list of colorshapesToPicture which contains different shapes. So the first function is used to convert ColorShape into pictures therefore program can further convert the list into pictures. Secondly, in codeworld the data of color names should be converted to color types. Thirdly, there also should be a conversion between shapes and pictures. In this function, the mathematics calculation should be adapted respectively depends on different shapes.
Additionally, the third task is to handle events by constructing different modeling tools of shapes.
Testing
To module testing, for example, calculate height of the circle then vertically stretch the circle when draw of Ellipse by adapting scaled function by factors in x and y direction.
Inspiration/ external content
Codeworld is used to be referred.
Reflection
There are some discussions reasoning decisions I made and they reflect the developed process in the program:
Firstly, there is a conceptual problem in rendering shapes part. It is confused to choose guard and cases. However, case is more efficient to adapt when writing function because case can write more various situation compared to guard. For example, in the function of shapeToPicture, it contains several shapes of drawing picture with calculation. Especially in drawing of sector, it then can use guards to show its four situation considered. If I do next time I will still use case instead of guards because case can contain more situations.
***self-marking examination
Code quality – testing and style
Correct; fast; readable
– ensuring correctness: reading/ test code/ mathematical proof about code