-
Notifications
You must be signed in to change notification settings - Fork 8
/
arrow-talk.html
301 lines (209 loc) · 7.1 KB
/
arrow-talk.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
<!DOCTYPE html>
<html>
<head>
<title>Arrows</title>
<meta charset="utf-8">
<style>
@import url(https://fonts.googleapis.com/css?family=Yanone+Kaffeesatz);
@import url(https://fonts.googleapis.com/css?family=Droid+Serif:400,700,400italic);
@import url(https://fonts.googleapis.com/css?family=Ubuntu+Mono:400,700,400italic);
body { font-family: 'Droid Serif'; }
h1, h2, h3 {
font-family: 'Yanone Kaffeesatz';
font-weight: normal;
}
h1 {
color: #5f00aa;
}
h2, h3, h4 {
color: SlateBlue;
}
.remark-code, .remark-inline-code { font-family: 'Ubuntu Mono'; }
img {
display: block;
margin-left: auto;
margin-right: auto;
}
</style>
</head>
<body>
<textarea id="source">
class: middle, right
# Categories and Arrows:<br/>What Do They Do? Do They Do Things??<br/>Let's Find Out!
.footnote[A massively informal introduction to what makes arrows arrows]
---
# What is an Arrow?
In category therory, an arrow, is... well... an arrow in a diagram. Mostly.
Official definition: _stuff that maps other stuff to moar stuff_ (ie. a morphism).
...yeah, ask Arnaud or Krzysztof about that really...
---
# What is an Arrow _in Haskell_?
As is usual in Haskell, an ungodly mess of typeclasses, I'm afraid.
#### In a nutshell:
```haskell
data A x y -- `Type -> Type -> Type` kind
```
An arrow is a computation from `x` to `y` with... some effects. And you can
compose them to build a pipeline of computations.
#### The Arrow typeclass stack:
```haskell
-- From most OK to least OK:
class Category -- We're cool
class Arrow -- Oh wowie! Parallel composition, still cool
class ArrowZero -- Mostly chill
class ArrowPlus -- Hmmm, okaaayyy...
class ArrowLoop -- Oh, some Tardis-trickery, I can deal with it I guess...
class ArrowChoice -- Wait, we're /branching/ now? But I thought
-- we were making a static pipeline of...
class ArrowApply -- PINEAPPLE! PINEAPPLE!
```
---
# Preliminary Warning
Rather: use monads directly. They're cool.
---
# A general form for Arrows
#### Not the _MOST_ general form, but still a general and useful one:
```haskell
newtype ArrowFromEffects f w m a b =
ArrowFromEffects (f (w a -> m b))
```
- `f`: Applicative
- `w`: Comonad
- `m`: Monad
- `w` and `m`: Distributive (ie. `w (m a) -> m (w a)`)
- Then: `ArrowFromEffects f w m` is `Arrow`, yay
And if `f`, `w` and `m` are just `Identity`, then we just have... a pure function.
#### Decomposing that gives:
```haskell
newtype Kleisli m a b = Kleisli (a -> m b) -- from base
newtype Cokleisli w a b = Cokleisli (w a -> b) -- from comonad
newtype Tannen f arr a b = Tannen (f (arr a b)) -- from bifunctors
```
Each implements all the classes up to `ArrowChoice`
---
# Composing Arrows
#### Product
```haskell
type Product arr arr' a b = (arr a b, arr' a b)
```
`arr` and `arr'` fully parallel. Cannot communicate. Implements whatever classes
`arr` and `arr'` both implement.
#### Alternation
```haskell
data Altern arr arr' a b where
AlternId :: Altern arr arr' a a
Altern :: arr a x -> arr' x y -> Altern arr arr' y b -> Altern arr arr' a b
```
Can communicate. Implements at least Category and Arrow (didn't try the rest
yet. Also didn't check if it satisfies Arrow laws yet (Booooo me, yes I know))
---
# Free Arrows
Create an arrow out of a `eff :: Type -> Type -> Type` datatype which doesn't
have to implement anything:
#### Initial encoding
```haskell
data FreeArrow eff a b where
Id :: FreeArrow eff a a
Arr :: (a -> b) -> FreeArrow eff a b
Eff :: eff a b -> FreeArrow eff a b
Comp :: FreeArrow eff a b -> FreeArrow eff b c -> FreeArrow eff a c
First :: FreeArrow eff a b -> FreeArrow (a,c) (b,c)
```
#### Final ~~countdown~~ encoding
```haskell
type FreeArrow eff a b =
forall ar. (Arrow ar) => (forall x y. eff x y -> ar x y) -> ar a b
```
---
# Summary
- Kleisli (used in `funflow`)
- Cokleisli
- Tannen (used in `porcupine`)
- Product (to be used in `porcupine`)
- Alternation
- Free arrows (used in `funflow`)
### Do these cover all the ways to define an arrow?
Let's say that's left as an exercise to the reader :) (Pheeewww...)
### What about that "profunctor" cr*p I hear about?
`Arrow` = `Category` ∩ `Profunctor` ∩ `Strong` ∩ `arr` method
but these aren't all in `base` for now.
---
# What was the point?
```haskell
newtype ArrowFromEffects f w m a b =
ArrowFromEffects (f (w a -> m b))
```
An arrow is the combination of monadic, comonadic and applicative
effects, or some parallel/sequential combination of that, itself possibly
wrapped in an applicative. Pretty general a framework.
_**Arrow = computation with ahead-of-time effects (applicative) and just-in-time
effects (monadic)**_
Defining applicative and monadic effects easy: lots of them around, lots of libraries.
Decomposing applicative effects as separate types (to `Compose` them) clean and
easy.
Use of comonadic effects? ...Could come handy. Dunno, still processing, some
papers to read and all.
### IMHO: Very relevant for code decomposition and reusability
---
# Comparison with Applicative
_In case of no monadic effects_, one could argue that:
```haskell
type Arr a b = f (a -> b)
```
Same power? Do we _really_ need arrows? (= Couldn't we have an equivalent for
every class this way?)
### Let's try to implement the Arrow stack with that type:
```haskell
class Category -- Yup
class Arrow -- Yup
class ArrowZero -- Alternative is there, so yup
class ArrowPlus -- Yup, for same reasons
class ArrowLoop -- Oh, oh, wait, wait, is it... and yes that's a yup
class ArrowChoice -- Yes... Aaaand dammit, no, it doesn't have the right semantics
class ArrowApply -- Lol
```
`ArrowChoice` doesn't have the right semantics (though it satisfies Arrow
laws!): you can't shortcut effects.
---
# Comparison with Applicative (2)
### Wait! Now we have `Selective`!!
...Yeah. Still no ArrowChoice, sorry...
```haskell
branch :: (Selective f)
=> f (a -> c) -> f (b -> d) -> f (Etiher a b) -> f (Either c d)
(|||) :: (ArrowChoice arr)
=> arr a c -> arr b d -> arr (Either a b) (Either c d)
```
If `arr` is `f (a -> b)` that gives:
```haskell
branch :: f (a -> c) -> f (b -> d) -> f (Etiher a b) -> f (Either c d)
(|||) :: f (a -> c) -> f (b -> d) -> f (Either a b -> Either c d)
```
`(|||)` with `(<*>)` gives you `branch`, but no way back possible.
#### Every `ArrowChoice` can give you a `Selective`, but not the reverse :/
---
# Case of `funflow`
One of most important functions:
```haskell
step' :: Properties a b -> (a -> b) -> Flow a b
```
Generalization of `arr` function
Could have been:
```haskell
step' :: Properties a b -> (a -> b) -> AppFlow (a -> b)
```
(thus generalizing `pure`)
But what about:
```haskell
stepIO' :: Properties a b -> (a -> IO b) -> Flow a b
```
No way to return a `f (a -> b)` from a `(a -> m b)`!!
</textarea>
<script src="https://remarkjs.com/downloads/remark-latest.min.js">
</script>
<script>
var slideshow = remark.create();
</script>
</body>
</html>