# Algebraic Data Types: Exponents

Episode #9 • Mar 26, 2018 • Subscriber-Only

We continue our explorations into algebra and the Swift type system. We show that exponents correspond to functions in Swift, and that by using the properties of exponents we can better understand what makes some functions more complex than others.

###### Previous episode
Algebraic Data Types: Exponents
Introduction
00:05
A correction
01:05
Exponents
04:50
Functions
05:30
Property #1
08:58
Property #2
12:32
Property #3
14:57
The algebra of in-out
22:41
The algebra of throws
24:28
What’s the point?
28:07

### Introduction

In the last episode on algebraic data types we started to get a glimpse of what it means to see algebraic structure in the Swift type system. We saw that forming structs corresponds to a kind of multiplication of the types inside the struct. Then we saw that forming enums corresponded to a kind of summation of all the types on the inside. And finally we used this intuition to figure how to properly model a datatype so that impossible states are not representable, and enforced by the compiler.

In this episode we are we are going to look at the next piece of algebra that is not captured by just plain sums and products: exponentiation. We will see that it helps build our intuition for how function arrows act with respect to other constructions, and even allow us to understand what makes a function more or less complicated.

This episode is for subscribers only.

### Subscribe to Point-Free

Access this episode, plus all past and future episodes when you become a subscriber.

See plans and pricing

### Exercises

1. Prove the equivalence of `1^a = 1` as types. This requires re-expressing this algebraic equation as types, and then defining functions between the types that are inverses of each other.

2. What is `0^a`? Prove an equivalence. You will need to consider `a = 0` and `a != 0` separately.

3. How do you think generics fit into algebraic data types? We’ve seen a bit of this with thinking of `Optional<A>` as `A + 1 = A + Void`.

4. Show that sets with values in `A` can be represented as `2^A`. Note that `A` does not require any `Hashable` constraints like the Swift standard library `Set<A>` requires.

5. Define `intersection` and `union` functions for the above definition of set.

6. How can dictionaries with keys in `K` and values in `V` be represented algebraically?

7. Implement the following equivalence:

``````func to<A, B, C>(_ f: @escaping (Either<B, C>) -> A) -> ((B) -> A, (C) -> A) {
fatalError()
}

func from<A, B, C>(_ f: ((B) -> A, (C) -> A)) -> (Either<B, C>) -> A {
fatalError()
}
``````
8. Implement the following equivalence:

``````func to<A, B, C>(_ f: @escaping (C) -> (A, B)) -> ((C) -> A, (C) -> B) {
fatalError()
}

func from<A, B, C>(_ f: ((C) -> A, (C) -> B)) -> (C) -> (A, B) {
fatalError()
}
``````
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://www.pointfree.co/episodes/ep9-algebraic-data-types-exponents", "fetch_time": 1685715988000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2023-23/segments/1685224648695.4/warc/CC-MAIN-20230602140602-20230602170602-00196.warc.gz", "warc_record_offset": 1028718051, "warc_record_length": 16569, "token_count": 750, "char_count": 2869, "score": 4.09375, "int_score": 4, "crawl": "CC-MAIN-2023-23", "snapshot_type": "latest", "language": "en", "language_score": 0.916519820690155, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00047-of-00064.parquet"}