Functional Electromagnetism

James Earl Douglas

June 07, 2019

D'origine Française

English via French

DSP via FP

Agenda

  1. Visualizing categories
  2. Composition
  3. Functors
  4. Natural transformations

Visualizing categories

What's in a category?

┌────────────┐
│ Category C │
├────────────┤
│ X          │ <── A collection of objects
│ Y          │
│ Z          │
│            │
│ X => Y     │ <── A collection of arrows
│ Y => Z     │
└────────────┘

The category of types

┌───────────────┐
│     Types     │
├───────────────┤
│ Int           │ <── Simple types are objects
│ String        │
│               │
│ Int => String │ <── Function types are arrows
│ String => Int │
└───────────────┘

Type constructors as categories

┌────────────────────────┐
│       Option[_]        │
├────────────────────────┤
│ Option[A]              │
│ Option[B]              │
│                        │
│ Option[A] => Option[B] │
└────────────────────────┘

Type constructors as categories

┌────────────────────────┐     ┌────────────────────┐
│       Option[_]        │     │      List[_]       │
├────────────────────────┤     ├────────────────────┤
│ Option[A]              │     │ List[A]            │
│ Option[B]              │     │ List[B]            │
│                        │     │                    │
│ Option[A] => Option[B] │     │ List[A] => List[B] │
└────────────────────────┘     └────────────────────┘

Exploring the radio

Transmitter hardware

HackRF One

HackRF One

Transmitter software

GNU Radio Companion

GNU Radio Companion

Receiver hardware

RTL-SDR

RTL-SDR

Receiver software

Gqrx SDR

Gqrx SDR

Receiver hardware

BF-F8HP

BF-F8HP

Flow graph as a radio

Flow graph as a category

┌──────────────────┐
│    Flow Graph    │
├──────────────────┤
│ Signal           │ <── Signals are objects
│                  │
│ Signal => Signal │ <── Blocks are arrows
└──────────────────┘

Takeaway

We can use categories to visualize anything we like as long as we can identify the objects and arrows.

Composition

The composition operator

┌────────┐
│   C    │
├────────┤
│ X      │
│ Y      │
│ Z      │
│        │
│ X => Y │
│ Y => Z │
│        │
│ _ ∘ _  │ <── A composition operator
└────────┘
(Y => Z) ∘ (X => Y) = (X => Z)

Composing functions

Composed blocks

Composing blocks

         ┌───┐   ┌───┐
────────>│ m ├──>│ n ├────────>
         └───┘   └───┘

     ┌───────────────────┐
     │ m and then n      │
     │                   │
     │                   │
────>│                   ├────>
     │                   │
     └───────────────────┘

Composing blocks

         ┌───┐   ┌───┐
────────>│ m ├──>│ n ├────────>
         └───┘   └───┘

     ┌───────────────────┐
     │ n ∘ m             │
     │                   │
     │   ┌───┐   ┌───┐   │
────>│-->│ m │-->│ n │-->├────>
     │   └───┘   └───┘   │
     └───────────────────┘

Takeaway

Composition hides complexity by abstracting two functions as one.

Functors

Mapping between categories

┌────────┐        ┌───────────────┐
│   C    │        │       D       │
├────────┤        ├───────────────┤
│ A      │        │               │
│ B      │        │               │
│        │        │               │
│ A => B │        │               │
└────────┘        └───────────────┘

┌────────────┐
│  Functors  │
├────────────┤
│ F: C => D  │
└────────────┘

Mapping objects between categories

┌────────┐         ┌───────────────┐
│   C    │         │       D       │
├────────┤         ├───────────────┤
│ A ─────── F.map ─> F[A]          │
│ B      │         │               │
│        │         │               │
│ A => B │         │               │
└────────┘         └───────────────┘

┌────────────┐
│  Functors  │
├────────────┤
│ F: C => D  │
└────────────┘

Mapping arrows between categories

┌────────┐         ┌───────────────┐
│   C    │         │       D       │
├────────┤         ├───────────────┤
│ A ─────── F.map ─> F[A]          │
│ B      │         │               │
│        │         │               │
│ A => B ── F.map ─> F[A] => F[B]  │
└────────┘         └───────────────┘

┌────────────┐
│  Functors  │
├────────────┤
│ F: C => D  │
└────────────┘

Mapping types

┌───────────────┐              ┌───────────────────────────────┐
│     Types     │              │           Option[_]           │
├───────────────┤              ├───────────────────────────────┤
│ Int           │              │                               │
│ String        │              │ Option[String]                │
│               │              │                               │
│ Int => String │              │                               │
└───────────────┘              └───────────────────────────────┘

Mapping simple types

┌───────────────┐              ┌───────────────────────────────┐
│     Types     │              │           Option[_]           │
├───────────────┤              ├───────────────────────────────┤
│ Int ──────────── Option[_] ──> Option[Int]                   │
│ String        │              │ Option[String]                │
│               │              │                               │
│ Int => String │              │                               │
└───────────────┘              └───────────────────────────────┘

Mapping function types

┌───────────────┐              ┌───────────────────────────────┐
│     Types     │              │           Option[_]           │
├───────────────┤              ├───────────────────────────────┤
│ Int ──────────── Option[_] ──> Option[Int]                   │
│ String        │              │ Option[String]                │
│               │              │                               │
│ Int => String ── F.map ──────> Option[Int] => Option[String] │
└───────────────┘              └───────────────────────────────┘

┌───────────────────┐
│     Functors      │
├───────────────────┤
│ F: _ => Option[_] │
└───────────────────┘

Functor as a type class

trait Functor[F[_]] {
  def map[A,B](f: A => B)(fa: F[A]): F[B]
}

A functor for Option

trait Functor[F[_]] {
  def map[A,B](f: A => B)(fa: F[A]): F[B]
}
val optionFunctor: Functor[Option] =
  new Functor[Option] {
    def map[A,B](f: A => B)(fa: Option[A]): Option[B] =
      fa match {
        case None => None
        case Some(a) => Some(f(a))
      }
  }

Option as a functor

sealed trait Option[+A] {
  def map[B](f: A => B): Option[B] =
    this match {
      case None => None
      case Some(a) => Some(f(a))
    }
}

case object None extends Option[Nothing]
case class Some[A](value: A) extends Option[A]

Amplification with a functor

Time domain vs. undesignated domain

Time domain signal:

f(t): Time[Signal] = sin(t)

Amplify function:

f(x): Signal => Signal = 0.5 * x

Mapping between signal domains

                               f(t)
                                │
┌──────────────────┐         ┌──│───────────────────────────┐
│     Signals      │         │  │  Time domain signals      │
├──────────────────┤         ├──v───────────────────────────┤
│ Signal ──────────── F.map ─> Time[Signal]                 │
│ Signal => Signal ── F.map ─> Time[Signal] => Time[Signal] │
└──^───────────────┘         └──────────────────────────────┘
   │
  f(x)

┌───────────────────────────────────┐
│            Functors               │
├───────────────────────────────────┤
│ F: Signals -> Time domain signals │
└───────────────────────────────────┘

Takeaway

Functors allow the use objects and arrows from another category.

Natural transformations

Three categories

┌───────┐           ┌───────┐           ┌───────┐
│   D   │           │   C   │           │   E   │
├───────┤           ├───────┤           ├───────┤
│       │           │       │           │       │
│       │           │       │           │       │
│       │           │ X     │           │       │
│       │           │       │           │       │
│       │           │       │           │       │
└───────┘           └───────┘           └───────┘

And a functor

┌───────┐           ┌───────┐           ┌───────┐
│   D   │           │   C   │           │   E   │
├───────┤           ├───────┤           ├───────┤
│       │           │       │           │       │
│       │           │       │           │       │
│ F[X] <─── F.map ─── X     │           │       │
│       │           │       │           │       │
│       │           │       │           │       │
└───────┘           └───────┘           └───────┘

┌────────────┐
│  Functors  │
├────────────┤
│ F: C => D  │
│            │
└────────────┘

And another functor

┌───────┐           ┌───────┐           ┌───────┐
│   D   │           │   C   │           │   E   │
├───────┤           ├───────┤           ├───────┤
│       │           │       │           │       │
│       │           │       │           │       │
│ F[X] <─── F.map ─── X ─────── G.map ──> G[X]  │
│       │           │       │           │       │
│       │           │       │           │       │
└───────┘           └───────┘           └───────┘

┌────────────┐
│  Functors  │
├────────────┤
│ F: C => D  │
│ G: C => E  │
└────────────┘

An arrow between them

┌───────┐           ┌───────┐           ┌───────┐
│   D   │           │   C   │           │   E   │
├───────┤           ├───────┤           ├───────┤
│ ┌────────── p ──────────────────────────┐     │
│ │     │           │       │           │ v     │
│ F[X] <─── F.map ─── X ─────── G.map ──> G[X]  │
│       │           │       │           │       │
│       │           │       │           │       │
└───────┘           └───────┘           └───────┘

┌────────────┐     ┌─────────────────┐
│  Functors  │     │     Natural     │
├────────────┤     │ transformations │
│ F: C => D  │     ├─────────────────┤
│ G: C => E  │     │ p: F => G       │
└────────────┘     │                 │
                   └─────────────────┘

And another in the reverse

┌───────┐           ┌───────┐           ┌───────┐
│   D   │           │   C   │           │   E   │
├───────┤           ├───────┤           ├───────┤
│ ┌────────── p ──────────────────────────┐     │
│ │     │           │       │           │ v     │
│ F[X] <─── F.map ─── X ─────── G.map ──> G[X]  │
│ ^     │           │       │           │ │     │
│ └────────── q ──────────────────────────┘     │
└───────┘           └───────┘           └───────┘

┌────────────┐     ┌─────────────────┐
│  Functors  │     │     Natural     │
├────────────┤     │ transformations │
│ F: C => D  │     ├─────────────────┤
│ G: C => E  │     │ p: F => G       │
└────────────┘     │ q: G => F       │
                   └─────────────────┘

Natural transformation as a trait

trait ~>[F[_], G[_]] {
  def apply[A](f: F[A]): G[A]
}

Option to List

┌───────────┐                               ┌─────────┐
│ Option[_] │                               │ List[_] │
├───────────┤                               ├─────────┤
│ Option[A] │                               │ List[A] │
└─│─────────┘                               └─^───────┘
  └─────────────────── optionToList ──────────┘
val optionToList: Option ~> List =
  new (Option ~> List) {
    def apply[A](o: Option[A]): List[A] =
      o match {
        case None => Nil
        case Some(x) => List(x)
      }
  }

An implied category

┌───────────┐           ┌───────┐           ┌─────────┐
│ Option[_] │           │ Types │           │ List[_] │
├───────────┤           ├───────┤           ├─────────┤
│ Option[A] │           │ A     │           │ List[A] │
└─│─────────┘           └───────┘           └─^───────┘
  └─────────────────── optionToList ──────────┘

And an implied functor

┌───────────┐           ┌───────┐           ┌─────────┐
│ Option[_] │           │ Types │           │ List[_] │
├───────────┤           ├───────┤           ├─────────┤
│ Option[A] <── O.map ─── A     │           │ List[A] │
└─│─────────┘           └───────┘           └─^───────┘
  └─────────────────── optionToList ──────────┘

┌────────────────────┐
│      Functors      │
├────────────────────┤
│ O: _ => Option[_]  │
│                    │
└────────────────────┘

And another implied functor

┌───────────┐           ┌───────┐           ┌─────────┐
│ Option[_] │           │ Types │           │ List[_] │
├───────────┤           ├───────┤           ├─────────┤
│ Option[A] <── O.map ─── A ─────── L.map ──> List[A] │
└─│─────────┘           └───────┘           └─^───────┘
  └─────────────────── optionToList ──────────┘

┌────────────────────┐
│      Functors      │
├────────────────────┤
│ O: _ => Option[_]  │
│ L: _ => List[_]    │
└────────────────────┘

A natural transformation from O to L

┌───────────┐           ┌───────┐           ┌─────────┐
│ Option[_] │           │ Types │           │ List[_] │
├───────────┤           ├───────┤           ├─────────┤
│ Option[A] <── O.map ─── A ─────── L.map ──> List[A] │
└─│─────────┘           └───────┘           └─^───────┘
  └─────────────────── optionToList ──────────┘

┌────────────────────┐     ┌──────────────────────┐
│      Functors      │     │       Natural        │
├────────────────────┤     │   transformations    │
│ O: _ => Option[_]  │     ├──────────────────────┤
│ L: _ => List[_]    │     │ optionToList: O => L │
└────────────────────┘     └──────────────────────┘

The frequency domain

A digital filter

Time to frequency and back

Time and frequency domains as categories

┌──────────────┐              ┌──────────────┐
│     Time     │              │   Frequency  │
├──────────────┤              ├──────────────┤
│              │              │              │
│              │              │              │
│ Time[Signal] │              │ Freq[Signal] │
│              │              │              │
│              │              │              │
└──────────────┘              └──────────────┘

Converting between signal domains

┌──────────────┐              ┌──────────────┐
│     Time     │              │   Frequency  │
├──────────────┤              ├──────────────┤
│ ┌────────────── timeToFreq ───┐            │
│ │            │              │ v            │
│ Time[Signal] │              │ Freq[Signal] │
│              │              │              │
│              │              │              │
└──────────────┘              └──────────────┘

Converting between signal domains

┌──────────────┐              ┌──────────────┐
│     Time     │              │   Frequency  │
├──────────────┤              ├──────────────┤
│ ┌────────────── timeToFreq ───┐            │
│ │            │              │ v            │
│ Time[Signal] │              │ Freq[Signal] │
│ ^            │              │ │            │
│ └────────────── freqToTime ───┘            │
└──────────────┘              └──────────────┘

Takeaway

Natural transformations convert values between "constructed" types.

Conclusion

Recognizing functional patterns in unfamiliar systems can help us understand them.

References

Questions