1JC3 Lecture Notes.pdf

Video Lecture Notes: Week 1: Computational Thinking is thinking inspired, supported, or enabled by computing (whatever thinking that a computer scientist does). Computing is the development and use of computer hardware and software to ○ Man...

Video Lecture Notes: Week 1: Computational Thinking is thinking inspired, supported, or enabled by computing (whatever thinking that a computer scientist does). Computing is the development and use of computer hardware and software to ○ Manage problems and information, create smart products, connect to others, explore the world. Computing is a mix of math, science, engineering, technology, and design. Fields of computing are CS, Comp Eng, Soft Eng, Info Systems, Info Tech, etc. (heavy overlap within these). Many kinds of thinking: ○ Historical, political, business, math, engineering, scientific, artistic. 1. Mathematical Thinking: Maths is a process for understanding the mathematical aspects of the world (time, space, measure, pattern, logical consequence). This process is based on math models that consist of objects, concepts, and facts. ○ Model is created to describe a math phenomenon. ○ Model is explored in various ways to discover new objects, concepts, and facts related to the model. ○ The resulting model gives a deeper existence of the understanding of the math phenomenon. Mathematical thinking is the thinking in the mathematics process. 2. Scientific Thinking: Science is the systematic study of the world through observation and experiment. Centered on: ○ The scientific method as a process of hypothesis formation and experimentation. ○ Formation of knowledge on the basis of evidence and thinking. 3. Engineering Thinking: Engineering is the application of knowledge (science and math) to solve problems and create things. Concerned with: ○ Developing and using best practice. ○ Understanding problems and products in terms of systems. ○ Using requirements to drive development. ○ Public safety and security. 4. Artistic Thinking: Art is the production of artifacts that express beauty or aspects of the world/human existence. It includes: ○ Finding inspiration in nature, ideas, past events, imagination, other art. ○ Looking for new ideas/experiences. ○ Imposing restrictions to focus creativity. 5. Computational Thinking:  Starts with understanding computing (Haskell programming language) A mix of the previous 4 types of thinking The fundamental question of comp thinking is: What can and cannot be done with computing? ○ Forms two questions: What are the theoretical, and the practical limits of computing. Question: Are there any theoretical limits on what can be computed? ○ Answer: Yes, not every problem can be solved computationally, regardless of computational power. ○ There are also practical limits to computing, as some problems might need unbearably high storage, memory, or GPU capacity. (limits to computational power) Gottfried Leibniz (1646-1716): German polymath (excels in more than one thing) Developed calculus (1684) independently of Newton. Great CS and engineer who anticipated the ideas of modern computing. ○ Developed binary number system ○ Created the Staffelwalze (Stepped Reckoner), a machine that can add, subtract, multiply, divide, and do square roots. Motto was Calculemus! (Latin for “Let us calculate!”) He postulated the characteristica universalis, a universal language where all scientific ideas could be expressed. Also postulated the calculus ratiocinator, a computing device that gives true or false to any statement expressed in the language from his previous postulation. ○ This device is not theoretically possible. ○ Alonzo Church and Alan Turning proved that there are undecidable decision problems Their work was influenced by Kurt Godel’s proofs of his famous first and second incompleteness theorems. Week 2: Haskell B. Curry (1900 - 1981): American mathematician, logician, and CStist. Known for developing combinatory logic (This was first presented by Moses Schonfinkel in a 1924 paper) ○ It is a system for defining and using functions without variables f(x) = x^2 is an example of doing the above with variables (not combinatory logic) Known for the Curry Paradox, Curry-Howard correspondence, and the method of currying a function 1. If this sentence is true, then something absurd is also true (ex. If the sentence is true, then COVID is fake)  2. Merging programming and logic together (Proofs and programs are equivalent) 3. Will be mentioned later Liar Paradox is that, if you have a false statement saying that it is false, then it is technically true, and if you have a false statement saying it is true, then it is technically false ○ A = “A is false” The Haskell programming language is named after him. Computers store and manipulate information. The behavior of a computer is determined by a sequence of statements called a program. Computers are useful as: ○ Hardware allows massive amounts of data to be stored and manipulated with great speed and accuracy. ○ Software allows you to control the hardware with great power and flexibility. A programming language is a language to write programs in. An imperative statement expresses an action to be performed (Start your engine), while a declarative statement expresses a property. Imperative program is a sequence of imperative statements that express how the program works. Declarative program is a sequence of declarative statements that expresses what the program will do. A programming paradigm is a well-developed style of programming. (Each language supports one or more paradigms) ○ Procedural: Imperative program, collection of procedures possibly having side effects (ex. C) ○ Object-Oriented: Imperative, behaves as a collection of interacting objects (objects hold data and operations) (ex. C++, Java, Python) ○ Functional: Declarative, collection of side-effect free function definitions (Doesn’t ever change the functions) (ex. Elm, Haskell) ○ Logical: Declarative, collection of logical statements (ex. Prolog) Modes of Program Execution: 1. Programs are interpreted line by line: ○ Advantage: Supports interactive development and debugging. ○ Disadvantage: Is slower than executing compiled code. 2. Program can be compiled into native machine code ○ Advantage: Machine code is optimized to run fast ○ Disadvantage: Code development is more difficult. 3. Programs can be compiled into byte code for a virtual machine that then does either of the two above. ○ Advantage: Programs are more portable ○ Disadvantage: Byte code is slower than native code  Haskell can use both of the first two modes Values are info/data stored and manipulated by computer programs. ○ Booleans for true and false. ○ Machine integers for small integers ○ Floating point numbers for rational numbers in scientific notation ○ Strings for sequences of characters ○ Tuples for sequences of values of different kinds ○ Lists for a sequence of values of the same kind ○ Functions for mathematical functions Different languages may have more ways to represent data. Expressions are syntactic entries that denotes a value. (Haskell examples below) ○ (x * 2) + 7 ○ “Abc” ○ True && y An atomic expression is an identifier (x or rotateHorse) or a literal (2.3, “cat”, or True) A compound expression is formed by applying a function or operator to other expressions (abs 10, 1 + 2) The value of an expression is obtained by evaluating the expression. Data type is a syntactic entity that denotes a collection of values in a similar form. ○ Bool for True and False, Int for machine(small) integers, Float for decimals, Integer for all Integers, Integer -> Integer for a set of functions from Integer to Integer ○ Integer x Integer and Int x Int are both data types ○ Boolean (Bool) doesn’t count as a valid data type?in Type error occurs when one type is used when another is expected. Haskell type checks before evaluation to find any type errors. The following evaluates to the type of expression e: ○ :type e Integers and Integer -> Integer can contain/represent an infinite amount of numbers. Unary Functions: Unary functions only take in one input A function is a rule f: I -> O (f is function, I is input, O is output) ○ Every input has at most one output (might not) (example is the reciprocal function x -> 1/x, as 1/0 doesn’t gives no output) OR, a function is a value(set), where in (x, y) and (x, y prime), since the input is same, the output must also be the same (y = y prime) Domains are the inputs, and ranges are the outputs Important properties of functions: ○ Total: Domain is all sets of inputs (infinite, function is defined at any input)  ○ Surjective: Range is all sets of outputs (infinite, can get any output from a limited set of input) ○ Injective: If f(x) = f(y), then x must equal y (Injective means that two different values in the domain are mapped to two different values in the range) ○ Bijective: All three of the above n-Ary Functions: n-Ary take any number of inputs For n >= 0, an n-ary function is the same as the second point for unary functions, but it also gives an output when no input is given (constant value) For n >= 0, an n-ary function is the same as the third point for unary functions (cartesian product, which is a set of tuples) Can represent n-ary functions as a unary function: ○ As a function on tuples: make f prime take only one input, which is a tuple (full set). In the end f = f prime ○ As a curried function: have f double prime, when fed an input, it gives another function that takes another input, and so on until the final output. In the end, f = f double prime. For a function f: N -> R ○ N means any positive number starting from 1, and R means any real number (Negative, positive, and zero) In Haskell, a function definition has the following form: f :: t1 -> … -> tn -> to F p1…pn = e ○ This is the curryed form ○ First line declares the type of the function f, second line defines f ○ t1, …, tn are all types of the inputs to f, to is the type of the output from f ○ p1, …m pn are the formal parameters of the definition that represent the inputs to f ○ Expression e is the result ○ Example below: (function takes one argument, then another, then the output) minus :: Integer -> Integer -> Integer minus m n = m + (-n) Function application has the form below, where each a1 is an expression of type t1: f a1, …, an a1,.., an are actual parameters of the application It is evaluated by subbing a1, …, an for p1, …, pn in e, and then simplifying the result expression (“Plug and chug”) Example below, which is evaluated by plugging in 4 and 9 into m and n from the previous example, and then chugging to get -5:  minus 4 9 While functions are usually defined in curryed form, they can also be defined on tuples. Example: The function f(x, y) = x^2 + y^2 can be represented in the following ways (Curryed and tuple, p is a tuple where fst is the 1st part of the ordered pair, and snd is the second part): ○ f1 :: Integer -> Integer -> Integer f1 x y = x^2 = y^2 ○ f2 :: (Integer, Integer) -> Integer f2 p = (fst p)^2 + (snd p)^2 f2 can also be defined using pattern matching as: ○ f2 (x,y) = x^2 + y^2 Trick to find if a function is injective: ○ If it fails the horizontal line test, it is not injective (Integer, Integer), which is a tuple, is the same as Integer x Integer, and it is called the collection of all Integer pairs. (Tuple is not a type) For a function, f :: Integer -> Integer -> Integer, the input is Integer, and the output is Integer -> Integer The function below is injective, as the input is just m, and n is ignored as it isn’t first. It is also not surjective, as it cannot achieve every possible output since it is cubed. (n^2 - 1, n^2 + 1, n^2 - 8, n^2 + 8, etc) F :: integer -> integer -> integer fmn Functional Programming: Programs are declarative. A program is a sequence of side-effect free function definitions. Results are made by evaluating expressions. Functions are defined as first-class values and used as rules. Recursion plays a big role. State change and data mutation are avoided as much as possible. Advantages over procedural programming include: ○ The meaning of the code is simpler ○ Testing and reasoning is more simple ○ Expressions can be safely moved around ○ Code is more compact ○ Evaluation can be performed in parallel Leading functional programming languages include: ○ Lisp family (Scheme, Clojure) ○ ML family (Standard ML, F#)  ○ OO + FP languages (Python, ruby) ○ Pure FP (Elm, Haskell) Haskell is simpler than procedural languages cause: ○ No imperative statements, no loops Focus is on what instead of how (implementation does the how) It encourages good programming practice. Testing and reasoning is much simpler. Haskell is well-established, highly accessible and easy to use, purely functional, supports recursion but not iteration, sophisticated static type system, has an interpreter (GHCi) Cardinality: Since there are N number of programs, while there are 2^N number of decision problems, almost all decision problems will be uncomputable. ○ Example: Exact gps is impossible, but we approximate to make it possible. Week 3: Ariane 5: Was a rocket that cost 10 billion that exploded in 1996, 500 million dollars lost. This was due to a software error:  ○ A 64-bit floating point number was converted to a 16-bit machine integer (Module was originally created for Ariane 4, but was reused without re-testing) ○ Shows that SWE must have a good understanding of how numbers are represented. Number systems: N = {0, 1, 2, …}, natural numbers, for counting and ordering. Z = {..., -2, -1, 0, 1, 2, …}, integers, for counting forward and backward. Q, rational numbers, for measuring. (½, ⅓, ¼, …) R, real numbers, for solving geometric problems. C, complex numbers, for solving algebraic problems. Zn, modular integers, for integer arithmetic modulo n, where n >= 1 (clock arithmetic). All of these systems are closely related to each other. Numeral Systems: A writing system for expressing numbers, especially integers and rational numbers. Roman numerals: ○ I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000 Hindu-Arabic numeral system: ○ Uses positional notation based on the number 10. ○ What we use now. ○ Introduced to Europe by Fibonacci through his book Liber Abaci (1202). Mohammad Al-Khwarizmi is called Algorimi, one of the founders of algebra, who helped spread the use of the Hindu-Arabic numeral system to Europe and the Middle East. Spent most of his life in the House of Wisdom, a major library in Baghdad. The method was called algorithm, from where the word algorithm comes from. He wrote a book on algebra: ○ Provided an exhaustive account on how to solve linear and quadratic equations. ○ Proved his results with geometry. ○ “Algebra” comes from the name of his book “al-jabr”. Decimal vs. Binary: Base 10: 0-9 Base 2: 0, 1 The position of place value specifies magnitude. Common bases in history: 10, 12, 20, 60 Common bases in computing: 2, 10, 16 (Base 16 uses 0-9 and A-F) The most important computer application is the processing of number-based computations. Problem: How can an infinite number system be represented on a computer? ○ Solution 1: Represent each member of the system using a fixed number of bits.  Advantage: Efficiency in use of space and time Disadvantage: Only finitely many numbers can be represented. ○ Solution 2: Represent each member of the system using an unbound # of bits. Advantage: All #s can be represented. Disadvantage: Inefficient in use of space and time. Machine Integers: Integers are represented with a fixed # of bits. Signed magnitude approach: ○ First bit from the left is 0 for positive, 1 for negative ○ The rest of the bits give the numerical value (ex. First bit gives + or -, and the rest gives numbers like 27, 573, etc.) ○ 00110 means +6 and 10110 means -6 ○ Has the problem of 2 zeros. (+0 and -0) ○ Another problem is that it isn't great for computation. If you do binary addition for 5 and -5, you will get the binary for 2, even though the answer is 0. ○ Most computers use 2’s complement. Two's complement using 2^n bits: ○ Has one 0; 2^(n-1) - 1 positives, 2^(n-1) negatives ○ Positives look as expected; negative #s have 1 as the most significant bit ○ Negate a number by inverting its bits and adding 1 ○ x + (-x) = 0 ○ Addition and multiplication are done using modular arithmetic. Arithmetic operations like + and * on machine integers can cause overflow. Example convert 127 to -127: ○ 127 is 01111111 -> -127 is the inverse 10000000 plus 1 -> 10000001 (-128 would be 10000000) (-1 is 11111111) (It is clock arithmetic once the 8 bits are full, if goes down, signifying -1 to -128) Question: What are the smallest and largest integers in a type of 2^n-bit (n >= 2) machine integers? ○ Answer: -2^(n-1) and 2^(n-1) - 1 Floating Point Numbers: A way of representing rational numbers in base-2 scientific notation with a fixed # of bits: ○ +-1.m*2^e 1.m is called the mantissa, 2 is the base (binary) and e is the exponent (not euler’s number). Single-precision floating # use 32 bits with 1 bit for the sign, 23 bits for the (unsigned) mantissa, and 8 bits for the (signed) exponent. For ease, floating point # can be expressed in Haskell in base-10: ○ 23.678, -0.04, 59.78e20, etc. Since the (0.1) base-10 = (0.00011001100…) base-2, 0.1 cannot be exactly represented as a floating point #. If you want to represent 0.625 in floating point binary notation: ○ 0.101, or 1.01 x 2^-1 Imagine in binary it is usually, 1111. If you make that decimal, you get 1111.1111. The positions for after the decimal is 2^-1, 2^-2, 2^-3, 2^-4, etc. 2^-1 = 0.5, and 2^-3 = 0.125. Therefore 0000.1010 is the representation for 0.625. Arithmetic operations on floating point #s return the float that is the closest to the true value: ○ -0.0 or 0.0 is returned if the result is close to zero (underflow) ○ Infinity is returned is # is too large (positive overflow) ○ -Infinity is returned is # is too small (negative overflow) ○ NaN (not a number) is returned if # is not defined (ex. sqrt(-1)) Floating point arithmetic can produce inaccurate or even bogus results. ○ + and * are not associative. ○ Floats must be used with care. Patriot Missile Disaster: Patriot missile missed an incoming Scud (enemy) missile: ○ Due to an inaccurate time calibration. 0.1 seconds was chopped at 24 bits After 100 hours, the error was 0.34 seconds, and the enemy missile can travel more than half a km in this time. Shows that computer professionals must know how numbers are represented on a computer. Avoid equality and inequality tests with floats: Tests for x == y or x /= y should be avoided when using floating point numbers. Only a small # of real numbers are properly represented as floats. Consider a problem of finding the roots of a function: ○ Testing for f x == 0.0 will often be False, even when x is close to the root. ○ f x may be small, but never 0.  ○ If f x evaluates to less than 1e-15, is this small enough? ○ You should use this: abs (f x) < epsilon, for suitably some small epsilon. ○ The value of epsilon can change depending on the context. (different tolerances) Numeric Types in Haskell: It is a type of value that represents a number system. Haskell has the following: ○ Int (32-bit and 64-bit machine integers) ○ Integer (all integers) ○ Float (32-bit floating point numbers) ○ Double (64-bit floating point numbers) ○ Rational (all rational numbers) These types have separate arithmetic operators with overloaded names: ○ +: addition ○ -: subtraction ○ *: multiplication ○ /: division ○ ^ and **: exponentiation Week 4: Computation thinking is using the right computational tools in the right way for the problem at hand, and it is understanding the limits and pitfalls of computational tools. Floating point numbers have 5 special values: ○ 0(underflow), -0(underflow), Infinity, -Infinity, NaN For floating point numbers, imagine a number line starting from 0: ○ 1 is really just 1.000…(23 zeroes) * 2^0. 2 is 1.00 * 2^1. 4 is 1.00 * 2^2. 8 is 1.00 * 2^3 ○ In the gap between 1 and 2, there are 2^23 different numbers that can be represented. Gap between 2 and 4 is 2^23. Gap between 4 and 8, 8 and 16, 16 and 32, and so on are also 2^23. ○ This means that as the numbers get higher/further away from 0, there are less floating point numbers available for use. ○ 0.5 is 1.00 * 2^-1, 0.25 is 1.00 * 2^-2, and so on. ○ The gap between 0.5 and 1 is 2^23 numbers, and the gap between 0.25 and 0.50 is 2^23 numbers. Infinity and -Infinity cannot be represented using floating point numbers as there is only a defined number of bits. 0.011 in binary would be 0.375 in decimal, as 0.1 means 0.5, 0.01 means 0.25, and 0.001 means 0.125. The base-2 scientific representation of 42 is: ○ Convert 42 to binary, which is 101010 ○ Convert that to scientific notation: 1.01010 x 2^5  ○ Note: 21, which is 42 divided by 2, is represented by 1.0101 x 2^4, which is the representation of 42 divided by 2. ○ 10.5 would be 1.0101 x 2^3 ○ This means that if you need to get the representation of something like 12.5, and it is too much work to do, you can get the representation for 25, and then divide that by 2. ○ Ex. 2.625 would be 1.0101 x 2^1, which was found by doing 10.5 / 2, and then that was divided by 2 again. ○ 1.3125 is 1.0101 x 2^0 ○ 0.65625 is 1.0101 x 2^-1 ○ This might be in the exam. ○ -0.65625 would be -1.0101 x 2^-1 Logic is: ○ The study of the principles surrounding sound reasoning. ○ The branch of mathematics behind mathematical reasoning. ○ The branch of mathematics underlying computing. A logic is a reasoning system that has: ○ A language with a formal syntax and proper semantics. ○ Concepts of truth and logical consequence. ○ A proof system for establishing that the statements in the language are true. ○ Examples include propositional logic, first-order logic, higher-order logic. The theoretical uses of logic are to study: ○ Computation, programming languages, and software design. The practical uses of logic are: ○ To write precise documentation about software artifacts that can be stored and manipulated by computers. ○ To reason about software artifacts, possibly with the help of math software systems like proof assistants. ○ To implement electronic circuits. ○ To provide reasoning facilities in programming languages. Software artifacts are by-products of the software development process that include requirements, design documents programs, and testing plans. A form of quantifier-free first-order logic is embedded into Haskell. ○ Bool, a type of truth values ○ Boolean functions ○ Predicates ○ Conditional expressions ○ Guarded function definitions ○ Case expressions A boolean is a truth value, either true or false. ○ In haskell, the type Bool has True and False. ○ A boolean expression is an expression of type Bool. True, False  True && False 1 == 2 (False) ○ Boolean expressions are used to make decisions. A boolean function is in the following form: ○ Bool -> Bool -> … -> Bool Haskell has 3 boolean functions: ○ Negation: NOT (not) ○ Conjunction: AND (&&) ○ Disjunction: OR (||) Think of the truth tables for NOT, AND, and OR All boolean functions can be made using just: ○ NOT and AND ○ NOT and OR ○ NAND (Sheffer Stroke) ○ NOR (Peirce arrow) IMPLIES (implies) is another function: ○ B1 implies b2 If the first input is F, then the second doesn't matter, and the output will be true. If the first input is T, and second is F, then output is F. If the first input is T, and second is T, then output is T. (not b1) or b2 would be an equivalent expression to b1 implies b2. ○ not (b1 and (not b2)) is also equivalent ○ (not b2) implies (not b1) is also equivalent There are 16 binary boolean functions in Bool -> Bool. (2 possible answers for each of the 4 lines in a truth table. 2^4 = 16) ○ 1 boolean function has 2 outputs (Bool) ○ 2 boolean functions has 4 outputs (Bool -> Bool) ○ 3 boolean functions has 16 as well (When you get 4 outputs as the final output from the Bool -> Bool, those 4 values just get inputted again into the new function, so it's just 4X4 again.) (Bool -> Bool -> Bool) ○ 4 boolean functions would have 256 outputs. (Bool -> Bool -> Bool -> Bool) ○ The formula to calculate this is 2^2^(n-1). A predicate is a function of a type with the following form: ○ t1 -> … -> tn -> Bool An example is a boolean function Haskell has the following predefined binary predicates: ○ ==, /=, = A (full) application of a predicate is a boolean expression. ○ Example: 1 == 2 A conditional expression is an expression whose value depends on the value of a boolean expression. In Haskell, it has the form: if c then e1 else e2  ○ The condition c is a boolean expression. Conditional expressions also allow for parts of the code to be skipped during evaluation. Example: ○ absInteger n = if n >= 0 then n else -n A guarded function definition is an alternative to conditionals. ○ f x1 … xm | g1 = e1 … | gn = en The guards g1, …, gn are boolean expressions. Example: ○ absInteger n | n < 0 - -n | n >= 0 = n A case expression, which allows a value to be chosen from a set of options, is a generalization of a conditional expression. ○ case e of p1 -> e1 … pn -> en The value of the expression e is matched against the patterns p1, …, pn Example: ○ boolToInt b = case b of False -> 0 True -> 1 Alonzo Church (1903-1995) was an American mathematician, logician, and CSist. He developed a model of computation called the lambda calculus based on function application and abstraction. Using the lambda calculus, he showed in 1936, for the first time, there is an undecidable decision problem. ○ He used this to show that first-order logic is undecidable (often called Church’s theorem) He is also known for the Church-Turing thesis, the Church-Rosser theorem, and his many exceptional phD students. (Alan Turing is his student, as is Dana Scott and Stephen Kleene. Ken Kunen is Dana Scott’s student, and Bill Farmer, the creator of 1JC3, is the student of Ken Kunen.) Lambda notation is a precise and convenient way to specify anonymous functions. If B is an expression of type Beta, ○ Lambda x: Alpha. B ○ Denotes a function f: Alpha -> Beta such that f(a) = B[x->a] Example: Let f = lambda x: R. x*x ○ f(2) = (lambda x: R. x*x)(2) = 2*2 ○ f denotes the squaring function.  In Haskell, an anonymous n-ary function can be expressed with lambda notation as: (\ means lambda) ○ \x1 … xn -> e Example: ○ The squaring function can be written as \x -> x * x Question: With the following Haskell function: ○ f x y = sqrt (x - y), what is the value of f 7? ○ Answers: ○ \y -> sqrt (7 - y) (Curried function, x is already filled in) ○ (\ x y -> sqrt (x - y)) 7 (the first bracket is just everything from f) (Both are right) Week 5: Recursion is a method of defining something (usually a function) in terms of itself. ○ An alternative to loops (iteration) ○ Can make many programs easier to write, understand, and prove correct. Almost all languages allow functions to be defined by recursion, but not all of them implement recursive functions efficiently. Use of recursion requires care and understanding. ○ Recursive definitions can be nonsensical (Example: non terminating) ○ Sloppy use of recursion can lead to confusion ○ Correctness is proved by mathematical induction. Learning how to use recursion is one of the best ways to develop computational thinking. A problem is solved by recursion as follows: ○ The simplest instances of the problem are solved directly. ○ Each other instance is solved by reducing the instance to simpler instances of the problem. ○ As a result of the last two points, each instance can be solved by reducing the instance to simpler instances and then reducing these instances to simpler instances and so on until a simplest instance is reached, which has already been solved. Notice that recursion uses a divide and conquer strategy. A function is defined by recursion as follows: ○ Has the form: f(x) = E(f(a1(x)),...f(an(x))) ○ Each element is assigned a natural number n(i). ○ For all i (special e) I and m (special e) N with 1 x) is a function that just returns the same x value. ○ (\x -> x^2) is a function that returns the value of x squared. ○ factorial is a function that returns the factorial of the x value entered. Question: What should A and B be for the function bigProd: (Answer is 1 and *) Applications of bigProd function: Linear Search function example:  Maximum value in a list example: A student of Church at Princeton, Stephen Kleene (1909–1994) was an American mathematician, logician, and computer scientist. He is one of the founders of the subfield of logic known as computability theory or recursion theory. He is the inventor of regular expressions. ○ The Kleene star operator and Kleene algebra are named after him. He made significant contributions to constructive logic. (To prove that something exists, you have to show an example) He wrote Introduction to Metamathematics, a highly influential textbook published in 1952. Kleene is a phD student of Alonzo Church To use induction to prove a recursive function, where n >= 1, we need to prove that: ○ f(n) = (n(n+1)(2n+1))/6 ○ For example, the function is f n = n**2 + f (n-1) This would return the value 14 if n = 3  When you plug 3 as n into the f(n) formula, you will also get 14. ○ The induction proof has two steps: Base step: Prove it for n = 1 Inductive step: Assume that f(k) = (k(k+1)(2k+1))/6 inductive hypothesis. Then show that f(k+1) = ((k + 1)(k+2)(2k+3))/6 (Just subbed in k+1 for n) Use the inductive hypothesis and prove it For bigSum 1 n (\x -> x), the formula would be (n(n+1))/2 ○ 1 + 2 + 3 + 4 + … + (n-1) + n ○ Pair the first and last to get (n + 1) ○ Pair second and second last to get (2 + n - 1) = (n + 1). All pairs would be (n + 1) ○ Do (n+1) times n, and then divide all that by 2. For bigSum 1 n (\x -> x**2), the formula would be (n(n+1)(2n+1))/6 Week 6: Linear Search question: (Answer is B, z is used to see if x matches to y) ○ Example: Solving a problem with recursion: ○ Problem: Define a function f :: Integer -> [Integer] -> Bool in Haskell such that f x L is True if x occurs in L and is False if x does not occur in L whenever the members of L are in ascending order. ○ Solution: Define the function using recursion: What are the simplest cases? How is a non-simplest case reduced to simpler cases? What assignment of natural numbers to the (x,L) input pairs shows that the definition is well-defined? ○ Two solutions are possible: Inefficient linear search (goes through each element of a list to try and find the value you are searching for) (Does not need to be ordered) Efficient binary search (goes to the middle, if it is that number, then great, otherwise the number will be either greater than or less than that middle value, so go to the middle of whatever side has the value, and keep doing this till you find the value) (Needs to be ordered) Creating types in Haskell: A very important part of programming is choosing or creating the right types for the task at hand. There are two main ways of creating types in Haskell:  ○ Give a new name to an old type ○ Create a new type of values Synonym Types: ○ A new name for an old type ○ It is defined by a type declaration of the form: type new-name = old-type ○ The type new-name can be used any place where the type old-name can be used. ○ Example: ○ type Vector = (Double,Double,Double) A synonym type with parameters is a new name for an old type with parameters. ○ In Haskell, a synonym type with parameters is defined by a type declaration of the form: type new-name p1 · · · pn = old-type ○ The parameters p1 · · · pn are type variables. A type with parameters is called a polymorphic type and represents a family of types. ○ Example: type Vector a = (a,a,a) An algebraic data type (algebraic type for short) is a new type of new values formed as a “sum” of “products”. ○ In Haskell, an algebraic type is defined by a data declaration of the form: ○ Each member of the type t is constructed from the constructors in exactly one way. ○ That is, there is “no junk and no confusion”. A function can be defined on t by using pattern matching with respect to the value constructors. ○ At least one pattern is needed for each constructor of A. Algebraic types are also called inductive types. The definition of the algebraic type t induces an induction principle that can be used to prove that a property holds for all members of t. ○ Proof by induction is the most useful proof technique employed in computing. A sum type is an algebraic type that has more than one constructor. Example: ○ data Bool = False | True  A product type is an algebraic type that has one constructor and has the same structure as a tuple type. ((Int,Int,Int) is the same as Int x Int x Int). Example: ○ data Point = MakePoint Float Float ○ , which has the same structure as the tuple type below: ○ type Point = (Float,Float) An enumeration type is an algebraic type that enumerates a finite set of new values. (No arguments like Integer in them) The definition of an enumeration type has the form: ○ data t = C1 | C2 | … | Cn C1, …, Cn are the new values of type t. Example: ○ data Bool = False | True Examples: ○ ○ Question: What kind of algebraic type is the following:  ○ A recursive type is an algebraic type whose defined type is included in the constructor’s types. Examples: ○ data Nat = Zero | Suc Nat ○ data ListInteger = Nil | Cons Integer ListInteger ○ data BinTreeFloat = Leaf Float | Branch BinTreeFloat Float BinTreeFloat Question: The set of values in a recursive type is: (C and D are correct) ○ Example using Nat:  ○ Question about using fibonacci numbers: (Answer is 3 as three cases are needed) ○ ○ The structural induction property for Nat is below, and it holds for every property P of Nat: ○ This principle is called mathematical induction or weak induction. ○ Example proof for the natPlus function from before is below:  ○ An algebraic type can define a type constructor that has types as parameters. Examples: ○ data List a = Nil | Cons a (List a) ○ data BinTree a = Leaf a | Branch (BinTree a) a (BinTree a) ○ data Maybe a = Just a | Nothing Example to define List and Maybe:  ○ Examples for BinTree: ○ Question: BinTree height: (Just a node could be either 0 or 1, but since B have to be 1, A must be 0. C is max) ○  An algebraic type A defines a new language L of expressions. ○ L is infinite when A is recursive. The expressions of L are in a one-to-one correspondence with the values of A. ○ The expressions of L serve as literals for the values of A. (Like the Suc numbers) Functions on A can be defined using pattern matching on the different forms of expressions of L. In Haskell, a newtype declaration of the form below defines a new type (possibly with parameters) by putting a “wrapper” around an existing type. ○ newtype new-type = constructor old-type new-type is semantically equivalent to a type defined by a data declaration with a single one-argument constructor. new-type is treated as a type distinct from old-type during compile time but as old-type during run time. Examples: ○ newtype Natural = Natural Integer ○ newtype Vector3 a = MakeVector3 (a,a,a) ○ newtype Function a b = Function a -> b Week 7: Week 8: Week 9: Week 10: Week 11: Week 12:  Video Tutorial Notes: Week 1: The interlude functions include drop, take, reverse, head, tail, length, div, last, init, and index (!!) ○ Week 2: Syntax rules for Haskell: ○ Functions and arguments must have the first letter be lowercase. Example: myFun, fun1, bigFunctionName ○ Lists should also have an additional letter ‘s’ at the end of them.\ Example: xs, ns ○ In a sequence of definitions, each definition must begin in the exact same column. a=… b=… c=… ○ Use local variables and let expressions to make code more readable and allow for reuse Instead of using: poly x = (x+1) * (x+1) Use this instead: poly x = let y=x+1 in y * y ○ Can also use where expressions: function = func(func2(funct3 xs)) where func xs = … func2 xs = … func3 xs = … In Haskell, functions run based on order of operations, not based on which line is first. Every expression, e, has its type, t. ○ e :: t A list is a sequence of values that are of the same type and is defined as below: ○ [1, 4, 5, 8] :: Integer A tuple is a sequence of values that can be from different types, and is defined as below: ○ (8, ‘a’, “String”, [‘f’, ‘g’]) :: (Integer, Char, String, [Char]) While you don't need to specify the type in a list for every entry, you need to do that, and have the exact location for tuples.  A string is really just type [Char], but type String also works in code When writing code, we need to always add in the type signature. Week 3: Conditional expressions allow you to define control structures over Bool values: ○ if Bool then val1 else val2 Conditionals can be nested. Signum takes an integer n and returns -1 if n is negative, 0 if n = 0, and 1 if n is positive. ○ signum :: Int -> Int signum n = if n < 0 then -1 else If n == 0 then 0 else 1 Can also do: signum n = if n < 0 then -1 else if n == 0 then 0 else -1 For expressions: ○ Every expression has a type ○ Every if has an else ○ The then and else cases must return the same type undefined is a very special value that can be used to cover a case that should never be reached. ○ The program will end if it reaches undefined. ○ Error function is the same, except it outputs an error message. (better to use) error “message” Guarded equations are an alternative to if expressions. ○ dbzDialogue powerLevel | powerLevel > 9000 = “ITS OVER 9000!!!” | otherwise = “Lame…” Functions can also use pattern matching: ○ not :: Bool -> Bool not False = True not True = False Can be defined in many ways using pattern matching: ○ (&&) :: Bool -> Bool -> Bool True && True = True True && False = False False && True = False False && False = False ○ Or you can do True && b = b _ && _ = False Haskell functions use curryed functions ○ Using tuples will allow you to make uncurryed functions. A function is polymorphic if its type contains one or more types of variables (a is not a type, it can be any type inputted)  ○ length :: [a] -> Int Reverse function takes a list of any type and returns a list of that same type ○ reverse :: [a] -> [a] Head function takes a list of any type and returns a value of the same type ○ head :: [a] ->\ Map function takes a function of any type to any other type, a list of the input type of the function, and returns a list of the output type of the function ○ map :: (a -> b) -> [a] -> [b] If a function g has the output of the same type as the input of a function f, you can compose them into a function z: ○ z=f.g You can use the $ to skip a bracket if the bracket ends at the end of the line of code. ○ Function = reverse (+) (map (2) (reverse (init (x:xs)))) would become: ○ Function = reverse (+) $ map (2) $ reverse $ init $ x:xs)) Type classes allow you to define functions that have different implementations depending on the type of their input (methods) ○ class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool ○ To use a function from a type class, you must make an instance for that class. instance Eq Bool where x == y = if x then … x /= y = not (x==y) Some basic classes include: ○ Eq, Show, Read, Eq => Ord, Eq,Show => Num, Num => Integral, Num => Fractional A polymorphic function is called overloaded if its type contains one or more class constraints. Instead of doing the first which only works for ints, do the second: ○ add :: Int -> Int -> Int add x y = x + y ○ add :: Num a => a -> a -> a [1, 2, 3, 4] == 1:(2:(3:(4:[])))) Functions can be defined using (x:xs) patterns: ○ head :: [a] -> a head (x:xs) = xs Using x:xs patterns doesnt work on empty lists ○ head [] would give an error Functions can be made without a name by using lambda expressions: ○ \x -> x + x Lambda expressions are useful when defining functions that return a function as a result. ○ add x y = x+y ○ add = \x -> (\y -> x + y)  Map function takes a function and a list and applies that function to each element in the list. ○ add1 x = x+1 sum1 xs = map add1 xs Use map and lambda together: ○ sum1 xs = map (\x -> x + 1) xs Recursion is the defining of a function using the definition of that function, or simply, using that function in its own definition. ○ map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : (map f xs) An example using the above function is below: ○ map (+1) [1, 2, 3] => map (+1) (1:2:3:[]) => (1+1) : (map (+1) (2:3:[])) => (1+1) : (1+2) : (map (+1) (3:[])) => (1+1) : (1+2) : (1+3) : (map (+1) []) => (1+1) : (1+2) : (1+3) : [] => [2, 3, 4] Week 4: Functions can be naturally defined in terms of other functions. Example: ○ factorial n = product [1..n] ○ Doing factorial 4 would do: product [1..4] = product [1,2,3,4] = 1*2*3*4 = 24 Functions that are defined in terms of themselves are called recursive. Example: ○ factorial 0 = 1 factorial n = n * factorial (n-1) Doing factorial 3 would do: ○ 3 * factorial 2 = 3 * (2 * factorial 1) = 3 * (2 * 1 * factorial 0) = 3 * (2 * (1 * 1)) = 6 A function to do powers would be: ○ pow m 0 = 1 pow m n = m * pow m (n-1) We can use recursion to define types with an infinite amount of values (Succ Nat means successor of a natural number) ○ data Nat = Zero | Succ Nat Nat is a new type, with constructors ○ Zero :: Nat – and Succ :: Nat -> Nat Nat contains the following infinite sequence of values: ○ Zero is 0 ○ Succ Zero is 1 ○ Succ (Succ Zero) is 2  ○ Succ (Succ (Succ Zero)) is 3, and so on Example: (deriving show is needed for ghci to print values of type Nat, as Nat needs to become a string to be printed in the console, and deriving means create an instance where you use type Show in a generic way) ○ data Nat = Zero | Succ Nat deriving Show 0 = Zero 1 = Succ Zero 2 = Succ (one) 3 = Succ (Succ (Succ Zero)) ○ Function to convert from Nat to Int: nat2int :: Nat -> Int nat2int Zero = 0 nat2int (Succ n) = 1 + (nat2int n) ○ Function to convert from Int to Nat: int2nat :: Int -> Nat int2nat 0 = Zero int2nat x = Succ (int2nat (x-1)) ○ Function to add two Nat numbers: (2 ways, 1st is very inefficient) add :: Nat -> Nat -> Nat add m n = int2nat (nat2int m + nat2int n) add :: Nat -> Nat -> Nat add Zero n = n add (Succ m) n = Succ (add m n) The second way does the following: ○ (Succ (Succ Zero)) `add` (Succ Zero) (Succ Zero) `add` (Succ (Succ Zero)) Zero `add` (Succ (Succ (Succ Zero))) (Succ (Succ (Succ Zero))) Arithmetic expressions are a simple form of expressions built up from integers using addition and multiplication. Example: 1 + 2 * 3 ○ Using recursion, you can declare a new type to represent such expressions: ○ data Expr = Val Int | Add Expr Expr | Mult Expr Expr For example, 1 + 2 * 3 would be represented as: ○ Add (Val 1) (Mult (Val 2) (Val 3))  For example, 2 * 5 + 6: ○ data Expr = Val Int | Add Expr Expr | Mult Expr Expr ○ expr = Add (Mult (Val 2) (Val 5)) (Val 6) ○ eval :: Expr -> Int eval (Val n) = n eval (Add x y) = eval x + eval y eval (Mult x y) eval x * eval y In computing, it is often useful to store data in a two-way branching structure or binary tree. Nodes are the circles, and each node has two branches (arrows). The nodes without branches are called leaves (at the bottom). For example: ○ data Tree = Leaf Int | Node Int Tree Tree ○ tree :: Tree Tree = Node 5 (Leaf 4) (Node 3 (Leaf 2) (Leaf 1)) ○ Function to see if the integer exists in the tree: (|| is a binary operator that means OR) (If one of the three options is true, then returns true, else returns false) occurs :: Int -> Tree -> Bool occurs m (Leaf n) = m == n occurs m (Node n t1 t2) = m == n || occurs m t1 || occurs m t2 ○ Running (occurs 1 tree) in ghci would return True, and running (occurs 7 tree) in ghci would return False.  ○ Function to squeeze down the above tree into a “sandwich”. Returns a list [4,5,2,3,1] flatten :: Tree -> [Int] flatten (Leaf n) = [n] flatten (Node n t1 t2) = flatten t1 ++ [n] ++ flatten t2 Below is an example of an ordered tree (Also called search trees): (If you used the flatten function from before, you will get [1,2,3,4,5]) Can create a new occurs function when dealing with ordered (sorted) trees (Is more efficient): ○ occurs :: Int -> Tree -> Bool occurs m (Leaf n) = m == n occurs m (Node n t1 t2) | m == n =True | m < n = occurs m t1 | m > n = occurs m t2 ○ If you run (occurs 2 tree), it looks at 4, recognizes that 2 < 4, goes to occurs 2 t1, which is the left side of the node. At this step, it sees that 2 == 2, and returns the value True. Lists allow the grouping of values together. Example: [1,5,3,2] Set comprehension is a notation used in math that can be used to construct new sets from old sets. Example: {x^2|x(Special e){1..5}} generates the set {1,4,9,16,25} In Haskell, comprehension notation can be used to create new lists from old lists. Example: ○ [x^2 | x