D'origine Française

English via French

Alexandre Dumas

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

Transmitter software

GNU Radio Companion

Receiver hardware

RTL-SDR

Receiver software

Gqrx SDR

Receiver hardware

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

• n . m
• m.andThen(n)
• n.compose(m)
• { x => n(m(x)) }

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

• M. Sheeran, Categories for the Working Hardware Designer
• B. Pierce, Basic Category Theory for Computer Scientists
• M. Owen, Practical Signal Processing

Questions