Relationship:

|Functors |
|__________________ |
|Applicatives | |
|_______________ | |
|Monnads | | |
|| | |
|| |
|________________|

Functors:

• Definition:

  A class instance with fmap implemented.
  It should satisify the law:
  fmap id = id : there exits an identity function s.t. the function does not change anyhting about the container.
  The law make sure that fmap does not change the structure of the container and it implies fmap (g . h) = (fmap g) . (fmap h) (distrubitivity?)

  • Intuition:

    Container(type function) of (not concrete, i.e. the type should be a type function that accepts another type as parameter)types where fmap can be used (a function that a takes in a function f :: (a -> b) where a and b are non concrete types and output a function f' :: (functorInstance a -> functorInstance b). i.e. apply the function f to every element in the coontainer).

  • Syntax:

    1 2 3

    instance Functor $TYPE_FUNCTION where fmap :: (a->b) -> $TYPE_FUNCTION a ->$TYPE_FUNCTAION b $FMAP_DEFINITION_HERE

    • Usage:

      Error checking, e.g. a function that applies to Either e could take a possible failure and pass some useful information about the failure.

    • Notable Examples:

      • Tree
      • Map
      • Sequence
      • []
      • Maybe
      • Either

Key ideas:

• Curl is infinetestimal circulation just as divergence is infetestimal flux.

Fundamentals / building blocks:

• Parametrize curves:

  • Parametrization:
    a map $\gamma $ so that curve $C$ is image of $\gamma$ on $[a,b]$ and $\gamma$ is continuous on $[a,b]$.
  • regular parametrization:
    same but $\gamma$ must be $C^1$ and $\gamma^\prime(t)\neq 0$ in the open interval $(a,b)$.
  • simple regular:
    add to regular the constraint that $\gamma$ is injective except when $\gamma(a)=\gamma(b)$¹.
  If $\gamma(a)=\gamma(b)$ then we say $\gamma$ is closed.²

• Line integrals

• Vector fields:

Circulation

Flux

Green’s theorem

I keep forgetting how BFS checks if the node is unexplored.
Like sometimes I just forget about it and turn it into a DFS and when I rememmber I want to check if the node is in the queue.
Just remember you only go down a row when you are down with the current row
Seriously why can’t I remember this.

Basically some gists from http://www.cs.toronto.edu/~krueger/csc263h/lectures/BFS.pdf.

1
2
3

graph TD;
  S-->U;
  U-->V;

$d$: depth from root
$\delta$: shortest path from root

Prove by contradiction:
$v$: closest node ( to $s$) where $d[v]\neq \delta(s,v)$.
$u$: the “predecessor” of $d$ on one of the shortest paths from $s$ to $v$.
Statement to contradict with :

• since predecessor, $\delta(s,u)+1=\delta(s,v)$.
• since $v$ closest and $u$ closer, $d[v]=\delta(s,u)$.
• from definition $d[v]\neq \delta(s,v)$.
• therefore $d[v]\neq \delta(s,v)=\delta(s,u)+1$
• since $d[v]$ is some kind of a path, and $\delta(s,v)$ is the shortest path by definition, $d[v]\geq \delta(s,v)$.
• Combine last 2 step and $d[v]>d[u]+1$.

Remark: basically deduce that between reaching the predecessor on shortest path and the vertex, the BFS visits at least 2 other nodes.

Three cases:

• $v$ not discovered:
  then $d[v]=d[u]+1$ since we will go to $v$ when exploring $u$’s neibours.

• $v$ is discovered and explored:
  Then it is enqued before $u$ thus $d[v]\leq d[u]$¹

• $v$ discovered but not fully explored
  Take the node that discovered $v$, this node is explored before $u$
  so by it is enqueued before $u$¹ $d[w]\leq d[u]$. Since $v$ discovered by $w$, $d[v]=d[w]+1\leq d[u]+1$

  ---

  Remark: the depth difference between $u$ and $v$ can’t be greater than 1 because we would explore all neighbours thus depth difference bettween neightbours cant be greater than $1$; and we know $u$ and $v$ have to be neighbours. Anyway the contradiction proof in other 2 cases uses property¹ but it is pretty intuitive that the depth difference can only be smaller.