https://gist.github.com/sgoyal1012/98ac2d289ddef3c1b3e4c4bb9a6093c6#file-best-links-md
Scala, SBT setup
Create scala worksheet .sc - useful feature
Practice assignment
=== instead of == in tests.SBT Tutorial
https://www.coursera.org/learn/progfun1/supplement/uV974/sbt-tutorial-and-submission-of-assignments-please-read
Can run in two ways, either via main or extends App
REPL
Pure LISP) vs wider (focus on functions, eg. Scala)REPLC++
:=>
- https://alvinalexander.com/source-code/scala/simple-scala-call-name-exampleBy-name parameters are only evaluated when used. They are in contrast to by-value parameters. To make a parameter called by-name, simply prepend => to its type.
sqrt@tailrec(x:Int) => x*x*x
sum(cube)(1,10) applies sum to cube; and then this applied function is applied to (1,10)
Function application associates to the left.f(x) = x -- is the fixed point of a functionSQRT is a special case of fixed point.Average DampingtoString needs an override method!gcd in the constructor itself, and use to reduce the rational. -- Data Abstractionthis in the max/less functions.require!
assertrequire is to enforce a precondition on the caller, assert on code's behavior.new Class(x1, x2) is already a value.this for the class value (self-reference)r.add(s) <--> r add sunary_ prefix : https://stackoverflow.com/questions/16644988/why-is-the-unary-prefix-needed-in-scalaRepresent sets as functions.
/**
* Returns the set of the one given element.
*/
def singletonSet(elem: Int): Set = {
x: Int => x.equals(elem)
}
Method XXX is not defined HDP!Organized in packages. -- package clause at top of the file.
Int etc are automatically imported)Traits
Scala.Any
Any, AnyRef, AnyvalNothing at the bottom
null --> Null
Int CANNOT be null! (null is only for AnyVal)[T]val defines it as an accessible member.Very nice assignment on TweetSets
conditional operator~ https://alvinalexander.com/scala/scala-ternary-operator-syntaxtrue and false becomes Constant objects!Int can become a class!Function types are are.. IN FACT objects in scala
type A => B is just an abbreviation for class trait Function1[A, B]
Anon functions lead to AnonFun
Calling a function is f.apply() -- Functions are objects!
Eg.
class AddOne extends Function1[Int, Int] {
| def apply(m: Int): Int = m + 1
| }
def is NOT an object!, When for example def f() is used as f -- converts it into function value -- ETA expansion.Useful -- https://twitter.github.io/scala_school/basics2.html#apply
Base Type
assertAllPos exampleS <: T --> S is a subtype of T
--> S > :T --> S is a supertype of TS <: T, given covariance for some types, therefore List[S] <: List[T], becuase LIsts are covariant.
Covariance -- https://docs.scala-lang.org/tour/variances.htmlIn Java, arrays are covariant, but they do type checking for every array to prevent issues.
Barbara Liskov Substition Principle
If A<:B, then everything you can do with B, you should be able to do with A.
In scala, Arrays are NOT Covariant (for why, see more below)
C[+A], contravariant C[-A], or nonvariant C[A]For a function, if A2 <: A1 and B1 <: B2, then A1 => B1 <: A2 => B2.
Functions must be contravariant in their argument types and covariant in their result types
Example -->
trait Function1[-T, +U] {
def apply(x: T): U
} // Variance check is OK because T is contravariant and U is covariant
class Array[+T] {
def update(x: T)
} // variance checks fails
MIND BLOWN! --> Function trait (checked in Scala code) becomes
trait Function1[-T, +U] {
def apply(x: T) : U
}
i.e. return type is covariant, argument type is contravariant.
+ and - whenever the hell you want?! NOOO -- otherwise we could make array covariant. Scala compiler checks that are no problematic rules of variance.. Roughly, what it will do is, it will let covariant type parameters only appear in method results. Contravariant type parameters can only appear in method parameters, and nonvariant, or invariant, that they are used as aliases, type parameters can actually appear anywhere.
Example from Piyush 007 -- https://gitlab.criteois.com/p.narang/scala-class/blob/master/src/main/scala/com/criteo/scalaclass/generics/Generics.scala
Takes example of Nil from the Cons Lists example.Nothing is a subtype of everything.
Making a class covariant can be a lot of work! -- The prepend example
Assume the similar Cat, Dog, Animal inheritance tree used earlier, plus the following:
abstract class SmallAnimal extends Animal
case class Mouse(name: String) extends SmallAnimal
Suppose we’re working with functions that accept types of animals, and return the types of food they eat. If we would like a Cat => SmallAnimal (because cats eat small animals), but are given a Animal => Mouse instead, our program will still work. Intuitively an Animal => Mouse will still accept a Cat as an argument, because a Cat is an Animal, and it returns a Mouse, which is also a SmallAnimal. Since we can safely and invisibly substitute the former by the latter, we can say Animal => Mouse is a subtype of Cat => SmallAnimal.
Expr, Number and Sum example; trait exprType Casts? Nooo that sucks! Scala does not recommend it.eval in every class -- but that way need to touch all classes if you add a method to the base trait.Case Classes
-- Automatically adds companion objects.
-- A generalization of the switch statement.
-- Can match on multiple expressions
-- Matches in the order they are written (Can match constructors too Sum(x1, x2)
-- You can have methods in the class/object itself this.match for example.Expression ProblemCons lists implemented before.::, called Cons eg. fruit = "apples" :: "(banana")
List(x) == x :: NilA::B::C is interpreted as A::(B::C)def makeOrderedLeafList(freqs: List[(Char, Int)]): List[Leaf] = {
freqs.sortBy(_._2).map {
case (c: Char, count: Int) => Leaf(c, count)
}
}
trait TestTrees {
val t1 = Fork(Leaf('a',2), Leaf('b',3), List('a','b'), 5)
val t2 = Fork(Fork(Leaf('a',2), Leaf('b',3), List('a','b'), 5), Leaf('d',4), List('a','b','d'), 9)
}
drop, tail.. xs(n)xs ++ ys. xs updated (n,x)xs indexOf x, xs contains xlast, init, reverse and concat in a recursive manner.RemoveAt in terms of take and dropMerge function (Compare head elements with each other)splitAt function returns a pair, eg. ("answer", 42) is a pair._1 and _2 can be used to access the fieldscase (Nil, ys) => ys
case (xs, Nil) => xs
[T]..but then not every type defines a comparator <, so compiler cannot be sure.lt -- put function value last in your parameters..gives compiler an idea of the types of parameters.Ordering[T] as a parameter -- leave out the ord in the call after you mark as implicit..the compiler figures out the correct orderingmap method to transform every element of a list.filter method to filter out elements based on a condition.filterNot, partition, takeWhile, dropWhile, span -- Nice functions!reduceLeft for sum and product.foldLeft takes in an accumulatorfoldLeft and reduceLeftfoldRight and reduceRight --> parenthesis go to the right.P(xs) for all lists xs, show base case, and then prove for x::xsreverse -- proving by induction does not workxs.reverse by ys; and prove that.Vector -- Upto 32*32 is an array, after 32 .. every element becomes a pointer to an array of 32 elements.
log32(n)-- much faster!!head and list, Vector is mucho mejor~
::, but has +: and :+Seq is the base class --> the common base class for List and Vector
IterableArray and StringRange function --> 6 to 1 by -2 -- >Lower Bound to Upper Bound by Typeexists and forallzip and unzipflatmapsum, max etc for numeric listsHandling nested sequences
IndexedSequence ---> is implemented using Vector.foldRight or flatten.
xs flatmap f = (xs map f).flattenProgram can be difficult to understand! due to abstraction.
Introduces the for expression. --> for (s) yield e; s contains a generator and a filter.
isPrime problem in nested for.Sets
Sets are unorderedcontains method.N Queens problem -- VERY NICE PROBLEM!
zip is very useful!!!Maps
NoSuchElementException -- the get method returns None if key not found.Option type. --> Some and None --> pattern matchingSorted and GroupBy
sorted is natural ordering, sortWith is according to a rule.The polynomial example
++ superimposes instead of adding.adjust!withDefaultValue!! -- simplifies it.Repeated parameters --> bindings: (Int, Double)*foldLeft -- is more efficientforencode function.identity function -- JHAKAAS!s flatmap wordOccurencesRecap on case classes
toString method.JBinding, String example. Goes over trait Function1Seq[Elem] extends (Int => Elem)MatchErrorPartial Function -- mind blown!
isDefinedAt to checkisDefinedAt only applies to the outerblock of matching, does not guarantee in Nested.Recap on collections
map, flatMap, filter, foldLeft, foldRightmap, flatMap and filter on Liststail-recursiveFor expressions --> simplify combinations of core methods map, flatMap and filter -- the Prime example is much simpler!How for translates to map, flatMap
flatMap --> for recursivelywithFilter on the pattern.for can be considered as querying a database.yielding results to find authors who have writen at least two books.distinctmap, flatmap and filter can all be expressed in for.for in terms of map
withFilterflatMapisPrime example.map, flatMap and filter, can use any datatype for forfor expressions are NOT TIED to collections, all you need is map, flatMap and filter.for for it, but need a map and flatmap definition.self example (because there are two generate fns)List generators; trees example.Has two functions flatMap and unit
List is a monadandThen for function compositionMonad Laws
Option class -- flatMap proof is a bit involved.Significance of laws
The Try type
Success and FailureforBulletproof example - an expression composed of Try, map and flatMap will never throw a non fatal exception.Trees
IntSet --> contains and incl(s incl x) contains y = s contains yIntSetEmpty, induction step is NonEmptyfor code.
tail only IF needed.Stream:: produces a list; #:: produces a stream (identical to Stream.cons)Stream objecttail params is call by name (remember the :=> to make a var call by name!StreamRange example questiontail everytime, can store the result and re-use it --> lazy evaluation vs call by name evaluation
lazy val vs def --> is the same the first time..but after the first time, lazy val is not recomputed --> very good exampleStream's tail becomes a lazy val
isPrime exampletake upto the where you need them.Explains the problem, and the methods/classes to represent.
Capacity, trait Move with moves Empty, Fill and Pourdef change in the trait to be defined by every case class above.foldRightNOT VERY EFFICIENT
TIP -- Name everything you can!, do not put all operators in one line and keep scope for future changes!
https://alvinalexander.com/scala/how-to-control-visibility-constructor-fields-scala-val-var-private
var is a mutable definition (can be reassigned)BankAccount example and definition.Cons Stream's example -- assuming operations on Stream are purely functional, unless you have side effects.Referential TransparencyOperational Equivalent -- two definitions x and y are operationally equivalent if any tests cannot be distringuished.
BankAccount example.REPEATfor loops cannot be represented by just higher order functions.
for expressions.. but uses foreachAND, OR and NOT (with a delay)Wires and gatesHalfAdder to define a FullAdderAction --> a function that has side effect (return type Unit)time is simulated, not actual time.Wire class -> getSignal, addSignal, actions to be done when signal changes.Agenda is a list of Events to be performed at a time; they perform actionsAction goes into the Agenda.Probe is also defined to get the values of the wire during the simulationOrGateAlt -- an implementation in terms of AND and NOTObserver Pattern -- Remember MVC from Objective C days!! (Publisher-Subscriber)
Publisher traitBankAccount in this pattern.subscriber Consolidator that subscribes to all the bank accounts.
_ Nice example!!Goes over the good and the bad (Bad is return type is Unit (forces imperative style) -- CONCURRENCY!!
We will study how to go from Imperative Functional Programming to Functional Reactive Programming
Signals that changed with time.
Mouse moved example -- Signal[Position]frp.Signal <--> Scala.React
Var ---> for signals that can be updated/changed (The Update method -- which is also defined for Arrays.Important -- Defining a signal in terms of other Signal A = f(Signal B) for example -- the relation is maintained going forward. (forever in the future!)
Goes over the BankAccount example.
Balance becomes a Signal[Int]balance() = balance() * amount IS WRONGG!!
balance in a val and then do itIMPORTANT!
b = b + 1 and b() = b() + 1 -- the latter DONT MAKE SENSE!, as the first one updated value, and the second defines a relation in eternity.Stackable variablesSignal[_] it means can take signals of all types.
NoSignal -- a sentinel signal.caller to the signal
computeValue() does the propagationNoSignal's computeValue does nothing.thread local -- Dynamic VariableFuture (Computations can take time!!!)
Callback -- mind blown!!*A Monad -- Future
onComplete --> think of it as an envelope given to the calculator and asking him to find the result, fill the envelope and return it back to us.implicit execution context for now.Success or Failure
onComplete that takes two callbacks (one for success/failure)readFromMemory returns Future[Array[Byte]]Future's apply returns a future that computes asynchronously (Future just expects a Body)flatMap etc, along with recoverWithflatMap cleans up the code and makes it nicer -- Very nice examples!
zips two futures (Does not work as zip fails when one of the lists being zipped fails)recover and recoverWithfallBackTo --> expressed in terms of recoverWithAwaitable trait, but IS NOT RECOMMENDED!!
for comprehensions (remember brightroll?!!)retry
fallBackTo recursionflatMap in terms of CallBackfoldLeft and foldRightretry in terms of foldLeft and foldRightSignal's -- FRPAmdahl!!program counter and a program stackmain thread -- in a sequential program, only the main thread is used.Thread subclasssynchronized construct! -- at most one thread
can hold a monitornested! -- Gives the example of a bank transfer -- locks on both source and transfer account
a1 to a2, and another from a2 to a1 --> DEADLOCK!pNorm exampletask instead of parallel.
Task interface that takes in a computation as an argumenttasksparallel construct in terms of tasksWork (all sequential) and Depth (Infinite parallel)
Depth (as that is the case when parallelism is infinite)Amdahl's law returns!! -- the law of parallelismScalaMeterwithWarmer -- awesome!! -- Nice intro to ScalaMeter; can also measure Memory footprint`merge and the copy functionsparMergeSort vs quickSort -- Uses ScalaMeterfold, scan, map etc.)List is NOT good (as cannot find the middle easily) --> use Array and Treefirst element cons rest of list is still n!!Array
parallel implementation -- (1) Writes need to be disjoint (2) Threshold for sequential needs to be large enough to have efficiency!Tree
leaf stores the num of elements, and nodes contain the elementsTrees --> in trees less worry about disjointnessfoldLeft, foldRight, reduceLeft, reduceRightTree, can use listreduce and reduceSeg function. (reduce is done in a sequential fashion)less checker)A Closure B)scan is like a combo of map and foldupsweep and downsweep functions to the rescueCount change problem -- how to divide stuff if we do not know the workload?!!
Counting change is a canonical example of a task-parallel problem in which the partitioning the workload across processors is solution-driven -- to know how to optimally partition the work, we would first need to solve the problem itself.
the synchronization costs of doing this are way too high. Instead, we need to agglomerate parts of the computation. We do this by calling the sequential countChange
ScalaMeter -- letting it warmup and GC firstNice line of sight problem
for loop --> MUST BE CAREFUL of adding .par to the loopimage array in parallel.filter can be done in par.foldLeft CANNOT be done --> great lego example!! -- foldLeft depends on the previous part --> so MUST be sequentialfold can be done--> it is like a reduction treemax using Int.MinValue as the neutral elementRock, paper and scissors example!
Play is NOT associative --> it is commutativefold to work --> the two following conditions must hold to make the operator f a MONOID
f(a, f(b,c)) == f(f(a,b),c) -- ASSOCIATIVEf(z,a) == f(a,z) == a -- Like an identity on the neutral element zfold -- the type of the neutral element must be the same !!!aggregate --> a combination of fold and foldLeftz A z A z A z A
\ / \ /seqop\ / \ /
B B B B
\ / combop \ /
B _ _ B
\ combop /
B
https://stackoverflow.com/questions/6928374/example-of-the-scala-aggregate-function
Scala collections hierarchy
Traversable[T] -- Must implement foreachIterable[T] -- Must have iteratorSeq[T] -- Orderd
...Parallel collection hierarchy
ParIterable[T] etcGenSeq, GenIterable etc -- can or cannot be run in parallel
Compares toPar on List vs Vector -- List is way slower
All collections have a parallel counterpart (mutable Par, immutable par etc)
Example of calling a function with arguments GenSet that accepts both sequential and parallel implementations.
ConcurrentSkipListSetTrieMap is an exception -- has a snapshot() method.
Iterator - must always call hasNext
foldLeft on iteratorSplitter extends Iterator
split --> O(n)fold on a splitter --> similar to reduction trees --> parallely keep splitting and then sequential if below a thresholdBuilder
newBuilder methodCombiner -- is a parallel version of the Builder -->
newCombiner -->combinersO(logn)Good notes!
K-means is an example of a bulk synchronous parallel algorithm (BSP). BSP algorithms are composed
from a sequence of supersteps, each of which contains:
parallel computation, in which processes independently perform
local computations and produce some values;
communication, in which processes exchange data;
barrier synchronisation, during which processes wait until every process finishes
https://en.wikipedia.org/wiki/Bulk_synchronous_parallel
Remember Tail Recursion! -- https://gist.github.com/sgoyal1012/98ac2d289ddef3c1b3e4c4bb9a6093c6#17-tail-recursion
Transformer methods --> like filter, map etc (create new collection)Builder for sequential transformer operationsCombiner (a Builder with a combine) (combine this with that)
Combine is different for different collections (for Set and Map it is a union)O(log n + log m) timeCombiner --> O(n)combine method, an efficient += method and can convert into the resulting data structure in O(n/P) timenested array buffer -- and then just copies the reference!result method to copy back into the array in a parallel fashionCons List
Conc trees! Contains level and size info at each node<> to Concat trees -- Concat making sure that the tree balance structure is maintained+= method should be O(1)
Append node type
log N Append nodesConc buffers -- introduces the Chunk node and the expand methodIn previous node, we did data-parallel (jellybeans in a jar!)
My dear RDD
RDDs seem like a immutable collection, have higher order functions like map, filter etc
How to create a RDD?
SparkSession, SparkContextTransformers create a new collections (not single values!) -- Accessors return single values as resultsTransformations and Actions
Transformations return RDDActions return NOT a RDD.. write to HDFSTransformations are lazy and Actions are eager
map -- add an action to get a result!!collect, count, take, reduce etc. etc.Stage
x.filter.take(10) can stop when you have 10! -- MIND BLOWNunion, cartesian etc)Why is spark good?
Gives an example of logistic regression
persist -- after an RDD is evaluated, can reuse -- MUY IMPORTANTEtake followed by countPersistence comes in various flavors
cache vs persist -- cache is memory only and persist can take multiple arguments (eg. MEMORY_ONLY, MEMORY_ONLY_SER)Different than collections!
Laziness is a good thing!!
map and filter are two passes, but it just does it once!! (MIND BLOWN!)master-worker topology
master is the driver program (The commander, we talk to this)executors are workers (they do the work)Cluster manager is YARN or MESOSDriver is the brain
main, transformations etcforeach is an action -- so nothing happens on the driver! (ONLY Transformations happen on it)take gives it back to the driver program (sent back to the driver)actions`reduction operations` distributed?
fold, aggregate etc walk through a collection and combine to get a resultfoldLeft is NOT parallelizable
fold returns the same typeaggregate combines the twofoldLeft and foldRight does NOT even exits -- as it is not parallelizable! -- Thy must use aggregate!!aggregate is desirable as you go from a higher data structure (Case class) to a simpler one (like Int)Key-value pairs are preferred in the map-reduce world!
PairRDDs have special operations -- special methods -- groupByKey, reduceByKey, join etc.Actions and Transformations on PairRDD
groupBy examplegroupByKey groups the functions according to the keys they already have (no function required)reduceByKey reduces the values for the same keys.
reduceByKey is a transformation, unlike the action reduce in scala collectionsmapValues only applies functions to the valuescountByKey just counts the number of elements by keykeysis NOT an actionInner Join vs Outer Join
Inner join only takes the keys that intersect
transformations~~Outer join --> takes the union
Option type (can be None or Some)left vs right depends on whose keys are more important to usgroupBy and grooupByKey --> shuffle data as data MUST move around to combine data for the same keygroupBy returns a ShuffledRDDSHUFFLE is expensive!! -- Remember the humanized latencyreduceByKey is much more efficient! USE THIS!
reduces on the mappers firstreduceByKey gives almost 3x speed!
partition?
p using the hashvalue -- tries to spread around based on the value
partitionBypersist()!! -- otherwise it is repatition everytimemap does not make sense AS the KEYS MAY CHANGE!!!
mapValues WHEREVR possible!reduceByKey, 9x speedup over grouoByKey!join always shuffling dataRDDs are depicted as partitions (atomic pieces of dataset), and the dependenciesNarrow dependency -- Each partition of parent is used by at most one partitionWide dependencies -- Eacg partition of parent may be used by more partitions in child RDDgroupByKey has wide dependenciesjoin can cause shuffle (depending on whether you were smart to partition or not)dependencies method!! and toDebug Stringdeep dependencies.. need to recompute all partitions above! -- MIND BLOWN!RDDs
cartesianfilter before join is much faster than join then filter.JSON, XML etc.Database tablesSQL is the lingua francaSQL lingoRDD[Row]createOrReplaceTemplate -- then just SQL away!!, gives the people exampleRows! Scala compiler does not type checkMap, Struct etc)
StructgroupBy, select etc$"age">10GroupBy returns the RelationalGroupedDataset datatypeNan and null) (drop, fill, replace)join MUST specify the columns to join onRow is not convenient, need to cast them back using asInstanceOf
printSchema to get the schemaDataframe = Dataset[Row] --> Dataframe is a type of a DatasetRDD and Dataframe
RDD and DFF to DatasetTypedColumn and not just Column (as datasets are typed!)
map on Dataframe -- gives a dataset; but need to typecast manually!groupByKey returns the maldito KeyValuedGroupedDataset
TypedColumn!KeyValuedGroupedDataset --> mapGroups and flatMapGroups
reduceByKey! (Datasets do NOT have it!)mapGroups requires a full shuffle!! (Do NOT use'em!)Aggregator.
[-IN, BUF, OUT]zero, reduce, merge and finishEncoders.STRING