Collections Theory (Lists concat and reverse)
Rohit edited this page Dec 22, 2016
·
2 revisions
Q: How can we prove that the concatenation using ++ or the ::: operator is associative, and that it allows using Nil as an element either on the left or the right of it?
A: Done using Structural Induction: (prove that it holds for base case p(Nil), and for a lists xs and element x, if p(xs) holds, then for p(x :: xs) also holds.
This is analogus to Natural induction: (prove that it holds for p(base case) and if it holds for p(n) then it also holds for p(n+1).
Done using induction again.
This and the next lecture are mathematical proofs. Not required for programming in Scala, or for any assignments.
Week 1
Week 2
- Higher Order Functions
- Classes and Objects
- Substitution Model (CBV, CBN) with Classes
- Operators, Precedence and Types
Week 3
- Class Hierarchies and Dynamic Binding
- Organizing Classes and Scala Class Hierarchy
- Polymorphism (Subtyping and Generics)
Week 4
- Objects-Everywhere
- Subtyping and Generics (Bounds and Covariance)
- Decomposition
- Pattern Matching
- Collections (Lists)
Week 5
- Collections (List Methods)
- Pairs and Tuples
- Collections (Lists - Applying functions to elements)
- Collections (Lists Reduction)
- Collections Theory (Lists concat and reverse)
Week 6