# vim:tw=80:ft=pnlc:

.\p .p \x \f .f x \def

# this file is organized into a few sections separated by form feeds. sum

# types and product types are Scott encoded. type classes are product types and

# instances thereof inhabit those types. we keep their names short, at most four

# characters, because resolution is done manually; when you see a colon in an

# identifier, think type class instance. when defining binary operators, we

# order the parameters so as to be maximally lazy in the second argument;

# when an operator is strict in both arguments or can be made lazy in either

# argument, we order the parameters so as to make partial application useful

..def \x x \id

..def \x \y x \kestrel

..def \x \y y \kite

..def \x \f .f x \thrush

..def \x \y \f ..f x y \vireo

..def \x \y \z \f ...f x y z \veery # made this one up

..def \x \y \f ..f y x \finch

..def \x \f \y ..f y x \robin

..def \f .f f \mockingbird

..def \f \x ..f x x \warbler

..def \f \x \y ..f y x \cardinal

..def \g \f \x .f .g x \queerbird

..def \f \x \g .f .g x \quixoticbird

..def \x \f \g .f .g x \quizzicalbird

..def \g \x \f .f .g x \quirkybird

..def \x \g \f .f .g x \quackybird

..def \f \g \x .f .g x \bluebird

..def \f \g \x \y .f ..g x y \blackbird

..def \f \g \x \y \z .f ...g x y z \bunting

..def \f \g \h \x .f .g .h x \becard

..def \f \x \g \y ..f x .g y \dove

..def \f \x \y \g \z ...f x y .g z \dickcissel

..def \f \g \x \h \y ..f .g x .h y \dovekies

..def \f \x \g \y \z ..f x ..g y z \eagle

..def \f \g \w \x \h \y \z ..f ..g w x ..h y z \baldeagle

..def \f \g \x ..f x .g x \starling

..def \f \g \x ..f .g x x \violet # -backed starling

..def \f \g \x \y ..f y .g x \goldfinch

..def \f \g \h \x ..f .g x .h x \phi

..def \f \g \x \y ..f .g x .g y \psi

..def \f .\x .f .x x \x .f .x x \fix

 # constructors and eliminators

..def $err \void

..def \x x \unit

..def \true \false true \true

..def \true \false false \false

..def \true \false \bool ..bool true false \bool

..def .kestrel true \mrk # mark

..def .kestrel false \clr # clear

..def ..bool true false \buf # buffer

..def ..bool false true \not # invert

# when updating diadic gates update the Monoid instances too

..def ..bool buf clr \and # minimum

..def ..bool mrk buf \or # maximum

..def ..bool not clr \bgt # without

..def ..bool buf not \bet # xnor

..def ..bool clr buf \blt # -less

..def ..bool buf mrk \ble # implies

..def ..bool not buf \bne # xor

..def ..bool mrk not \bge # when

..def \gt \et \lt gt \gt

..def \gt \et \lt et \et

..def \gt \et \lt lt \lt

..def \gt \et \lt \cmp ...cmp gt et lt \cmp

..def ...cmp true false false \isgt

..def ...cmp false true false \iset

..def ...cmp false false true \islt

..def ...cmp false true true \isle

..def ...cmp true false true \isne

..def ...cmp true true false \isge

..def ..bool gt et \wolt # without lesser-than

..def ..bool gt lt \woet # without equal-to

..def ..bool et lt \wogt # without greater-than

..def ..bool et gt \woge # with only greater and equal

..def ..bool lt gt \wone # with only not equal

..def ..bool lt et \wole # with only lesser and equal

..def .kestrel gt \tmrk # mark

..def .kestrel et \trdc # redact

..def .kestrel lt \tclr # clear

..def ...cmp gt et lt \tbuf # buffer

..def ...cmp gt gt lt \tptb # positive-threshold buffer

..def ...cmp gt lt lt \tntb # negative-threshold buffer

..def ...cmp lt et gt \tnot # invert

..def ...cmp lt gt gt \tpti # positive-threshold inverter

..def ...cmp lt lt gt \tnti # negative-threshold inverter

..def ...cmp gt et gt \tabs # absolute value

..def ...cmp lt et lt \tnbs # negative absolute value

..def ...cmp lt gt lt \tisz # is zero

..def ...cmp gt lt gt \tisn # is nonzero

..def ...cmp gt et et \tclu # clamp up

..def ...cmp et et lt \tcld # clamp down

..def ...cmp lt et et \tuci # up-clamped inverter

..def ...cmp et et gt \tdci # down-clamped inverter

..def ...cmp gt lt et \tppi # positive-pivot inverter

..def ...cmp et gt lt \tnpi # negative-pivot inverter

..def ...cmp lt gt et \tinc # increment

..def ...cmp et lt gt \tdec # decrement

..def ...cmp gt gt et \tins # increment and saturate

..def ...cmp et lt lt \tdes # decrement and saturate

..def ...cmp et gt et \tinr # increment and redact

..def ...cmp et lt et \tder # decrement and redact

..def ...cmp lt lt et \tnss # negative spaceship

..def ...cmp et gt gt \tpss # positive spaceship

# when updating diadic gates update the Monoid instances too

..def ...cmp tbuf tcld tclr \tand # minimum

..def ...cmp tmrk tclu tbuf \tor # maximum

..def ...cmp tnbs tinr tnbs \tmean # mean

..def ...cmp tbuf tppi tpti \txmax # exclusive maximum

..def ...cmp tclu trdc tcld \tcons # consensus

..def ...cmp tins tbuf tdes \tgull # gullible

..def ...cmp tdes tbuf tins \tcord # converse order

..def ...cmp tpss tnot tnss \tord # order

..def ...cmp tntb tisz tnti \teq # equality

..def ...cmp tnot trdc tbuf \txor # exclusive or

..def ...cmp tbuf trdc tnot \tmul # multiplication

..def ...cmp tinc tbuf tdec \tsum # addition

..def ...cmp tmrk tbuf tclr \telse # else, priority left

..def ...cmp tptb tbuf tntb \tnles # unless, priority right

..def \val \some \none .some val \some

..def \some \none none \none

..def \some \none \opt ..opt some none \opt

..def ..opt \val true false \issome

..def ..opt \val false true \isnone

..def \fst \snd \pair ..pair fst snd \pair

..def \unpair \pair .pair unpair \unpair

..def .unpair \fst \snd fst \fst

..def .unpair \fst \snd snd \snd

..def \okval \ok \err .ok okval \ok

..def \errval \ok \err .err errval \err

..def \ok \err \res ..res ok err \res

..def ..res \okval true \errval false \isok

..def ..res \okval false \errval true \iserr

..def ..res some \errval none \okval

..def ..res \okval none some \errval

..def \head \tail \cons \nil ..cons head tail \cons

..def \cons \nil nil \nil

..def \cons \nil \list ..list cons nil \list

..def ..list \head \tail true false \iscons

..def ..list \head \tail false true \isnil

..def ..list \head \tail .some head none \head

..def ..list \head \tail .some tail none \tail

# the free monad

# data Free f a = Roll (f (Free f a)) | Return a

..def \term \roll \return .roll term \roll

..def \var \roll \return .return var \return

..def \roll \return \free ..free roll return \free

..def ..free \term true \var false \isroll

..def ..free \term false \var true \isreturn

..def ..free some \var none \term

..def ..free \term none some \var

# the cofree comonad

# data Cofree f a = Cofree (f (Cofree f a)) a

..def \trace \ann \cofree ..cofree trace ann \cofree

..def \uncofree \cofree .cofree uncofree \uncofree

..def .uncofree \trace \ann trace \trace

..def .uncofree \trace \ann ann \ann

# data Oct a = Oct a a a a a a a a

..def \0 \1 \2 \3 \4 \5 \6 \7 \oct ........oct 0 1 2 3 4 5 6 7 \oct

..def \unoct \oct .oct unoct \unoct

..def .unoct \0 \1 \2 \3 \4 \5 \6 \7 0 \oct.0

..def .unoct \0 \1 \2 \3 \4 \5 \6 \7 1 \oct.1

..def .unoct \0 \1 \2 \3 \4 \5 \6 \7 2 \oct.2

..def .unoct \0 \1 \2 \3 \4 \5 \6 \7 3 \oct.3

..def .unoct \0 \1 \2 \3 \4 \5 \6 \7 4 \oct.4

..def .unoct \0 \1 \2 \3 \4 \5 \6 \7 5 \oct.5

..def .unoct \0 \1 \2 \3 \4 \5 \6 \7 6 \oct.6

..def .unoct \0 \1 \2 \3 \4 \5 \6 \7 7 \oct.7

# def:u8

# type U8 = Oct Bool

..def ........oct false false false false false false false false \$00

..def ........oct true false false false false false false false \$01

..def ........oct false true false false false false false false \$02

..def ........oct true true false false false false false false \$03

..def ........oct false false true false false false false false \$04

..def ........oct true false true false false false false false \$05

..def ........oct false true true false false false false false \$06

..def ........oct true true true false false false false false \$07

..def ........oct false false false true false false false false \$08

..def ........oct true false false true false false false false \$09

..def ........oct false true false true false false false false \$0a

..def ........oct true true false true false false false false \$0b

..def ........oct false false true true false false false false \$0c

..def ........oct true false true true false false false false \$0d

..def ........oct false true true true false false false false \$0e

..def ........oct true true true true false false false false \$0f

..def ........oct false false false false true false false false \$10

..def ........oct true false false false true false false false \$11

..def ........oct false true false false true false false false \$12

..def ........oct true true false false true false false false \$13

..def ........oct false false true false true false false false \$14

..def ........oct true false true false true false false false \$15

..def ........oct false true true false true false false false \$16

..def ........oct true true true false true false false false \$17

..def ........oct false false false true true false false false \$18

..def ........oct true false false true true false false false \$19

..def ........oct false true false true true false false false \$1a

..def ........oct true true false true true false false false \$1b

..def ........oct false false true true true false false false \$1c

..def ........oct true false true true true false false false \$1d

..def ........oct false true true true true false false false \$1e

..def ........oct true true true true true false false false \$1f

..def ........oct false false false false false true false false \$20

..def ........oct true false false false false true false false \$21

..def ........oct false true false false false true false false \$22

..def ........oct true true false false false true false false \$23

..def ........oct false false true false false true false false \$24

..def ........oct true false true false false true false false \$25

..def ........oct false true true false false true false false \$26

..def ........oct true true true false false true false false \$27

..def ........oct false false false true false true false false \$28

..def ........oct true false false true false true false false \$29

..def ........oct false true false true false true false false \$2a

..def ........oct true true false true false true false false \$2b

..def ........oct false false true true false true false false \$2c

..def ........oct true false true true false true false false \$2d

..def ........oct false true true true false true false false \$2e

..def ........oct true true true true false true false false \$2f

..def ........oct false false false false true true false false \$30

..def ........oct true false false false true true false false \$31

..def ........oct false true false false true true false false \$32

..def ........oct true true false false true true false false \$33

..def ........oct false false true false true true false false \$34

..def ........oct true false true false true true false false \$35

..def ........oct false true true false true true false false \$36

..def ........oct true true true false true true false false \$37

..def ........oct false false false true true true false false \$38

..def ........oct true false false true true true false false \$39

..def ........oct false true false true true true false false \$3a

..def ........oct true true false true true true false false \$3b

..def ........oct false false true true true true false false \$3c

..def ........oct true false true true true true false false \$3d

..def ........oct false true true true true true false false \$3e

..def ........oct true true true true true true false false \$3f

..def ........oct false false false false false false true false \$40

..def ........oct true false false false false false true false \$41

..def ........oct false true false false false false true false \$42

..def ........oct true true false false false false true false \$43

..def ........oct false false true false false false true false \$44

..def ........oct true false true false false false true false \$45

..def ........oct false true true false false false true false \$46

..def ........oct true true true false false false true false \$47

..def ........oct false false false true false false true false \$48

..def ........oct true false false true false false true false \$49

..def ........oct false true false true false false true false \$4a

..def ........oct true true false true false false true false \$4b

..def ........oct false false true true false false true false \$4c

..def ........oct true false true true false false true false \$4d

..def ........oct false true true true false false true false \$4e

..def ........oct true true true true false false true false \$4f

..def ........oct false false false false true false true false \$50

..def ........oct true false false false true false true false \$51

..def ........oct false true false false true false true false \$52

..def ........oct true true false false true false true false \$53

..def ........oct false false true false true false true false \$54

..def ........oct true false true false true false true false \$55

..def ........oct false true true false true false true false \$56

..def ........oct true true true false true false true false \$57

..def ........oct false false false true true false true false \$58

..def ........oct true false false true true false true false \$59

..def ........oct false true false true true false true false \$5a

..def ........oct true true false true true false true false \$5b

..def ........oct false false true true true false true false \$5c

..def ........oct true false true true true false true false \$5d

..def ........oct false true true true true false true false \$5e

..def ........oct true true true true true false true false \$5f

..def ........oct false false false false false true true false \$60

..def ........oct true false false false false true true false \$61

..def ........oct false true false false false true true false \$62

..def ........oct true true false false false true true false \$63

..def ........oct false false true false false true true false \$64

..def ........oct true false true false false true true false \$65

..def ........oct false true true false false true true false \$66

..def ........oct true true true false false true true false \$67

..def ........oct false false false true false true true false \$68

..def ........oct true false false true false true true false \$69

..def ........oct false true false true false true true false \$6a

..def ........oct true true false true false true true false \$6b

..def ........oct false false true true false true true false \$6c

..def ........oct true false true true false true true false \$6d

..def ........oct false true true true false true true false \$6e

..def ........oct true true true true false true true false \$6f

..def ........oct false false false false true true true false \$70

..def ........oct true false false false true true true false \$71

..def ........oct false true false false true true true false \$72

..def ........oct true true false false true true true false \$73

..def ........oct false false true false true true true false \$74

..def ........oct true false true false true true true false \$75

..def ........oct false true true false true true true false \$76

..def ........oct true true true false true true true false \$77

..def ........oct false false false true true true true false \$78

..def ........oct true false false true true true true false \$79

..def ........oct false true false true true true true false \$7a

..def ........oct true true false true true true true false \$7b

..def ........oct false false true true true true true false \$7c

..def ........oct true false true true true true true false \$7d

..def ........oct false true true true true true true false \$7e

..def ........oct true true true true true true true false \$7f

..def ........oct false false false false false false false true \$80

..def ........oct true false false false false false false true \$81

..def ........oct false true false false false false false true \$82

..def ........oct true true false false false false false true \$83

..def ........oct false false true false false false false true \$84

..def ........oct true false true false false false false true \$85

..def ........oct false true true false false false false true \$86

..def ........oct true true true false false false false true \$87

..def ........oct false false false true false false false true \$88

..def ........oct true false false true false false false true \$89

..def ........oct false true false true false false false true \$8a

..def ........oct true true false true false false false true \$8b

..def ........oct false false true true false false false true \$8c

..def ........oct true false true true false false false true \$8d

..def ........oct false true true true false false false true \$8e

..def ........oct true true true true false false false true \$8f

..def ........oct false false false false true false false true \$90

..def ........oct true false false false true false false true \$91

..def ........oct false true false false true false false true \$92

..def ........oct true true false false true false false true \$93

..def ........oct false false true false true false false true \$94

..def ........oct true false true false true false false true \$95

..def ........oct false true true false true false false true \$96

..def ........oct true true true false true false false true \$97

..def ........oct false false false true true false false true \$98

..def ........oct true false false true true false false true \$99

..def ........oct false true false true true false false true \$9a

..def ........oct true true false true true false false true \$9b

..def ........oct false false true true true false false true \$9c

..def ........oct true false true true true false false true \$9d

..def ........oct false true true true true false false true \$9e

..def ........oct true true true true true false false true \$9f

..def ........oct false false false false false true false true \$a0

..def ........oct true false false false false true false true \$a1

..def ........oct false true false false false true false true \$a2

..def ........oct true true false false false true false true \$a3

..def ........oct false false true false false true false true \$a4

..def ........oct true false true false false true false true \$a5

..def ........oct false true true false false true false true \$a6

..def ........oct true true true false false true false true \$a7

..def ........oct false false false true false true false true \$a8

..def ........oct true false false true false true false true \$a9

..def ........oct false true false true false true false true \$aa

..def ........oct true true false true false true false true \$ab

..def ........oct false false true true false true false true \$ac

..def ........oct true false true true false true false true \$ad

..def ........oct false true true true false true false true \$ae

..def ........oct true true true true false true false true \$af

..def ........oct false false false false true true false true \$b0

..def ........oct true false false false true true false true \$b1

..def ........oct false true false false true true false true \$b2

..def ........oct true true false false true true false true \$b3

..def ........oct false false true false true true false true \$b4

..def ........oct true false true false true true false true \$b5

..def ........oct false true true false true true false true \$b6

..def ........oct true true true false true true false true \$b7

..def ........oct false false false true true true false true \$b8

..def ........oct true false false true true true false true \$b9

..def ........oct false true false true true true false true \$ba

..def ........oct true true false true true true false true \$bb

..def ........oct false false true true true true false true \$bc

..def ........oct true false true true true true false true \$bd

..def ........oct false true true true true true false true \$be

..def ........oct true true true true true true false true \$bf

..def ........oct false false false false false false true true \$c0

..def ........oct true false false false false false true true \$c1

..def ........oct false true false false false false true true \$c2

..def ........oct true true false false false false true true \$c3

..def ........oct false false true false false false true true \$c4

..def ........oct true false true false false false true true \$c5

..def ........oct false true true false false false true true \$c6

..def ........oct true true true false false false true true \$c7

..def ........oct false false false true false false true true \$c8

..def ........oct true false false true false false true true \$c9

..def ........oct false true false true false false true true \$ca

..def ........oct true true false true false false true true \$cb

..def ........oct false false true true false false true true \$cc

..def ........oct true false true true false false true true \$cd

..def ........oct false true true true false false true true \$ce

..def ........oct true true true true false false true true \$cf

..def ........oct false false false false true false true true \$d0

..def ........oct true false false false true false true true \$d1

..def ........oct false true false false true false true true \$d2

..def ........oct true true false false true false true true \$d3

..def ........oct false false true false true false true true \$d4

..def ........oct true false true false true false true true \$d5

..def ........oct false true true false true false true true \$d6

..def ........oct true true true false true false true true \$d7

..def ........oct false false false true true false true true \$d8

..def ........oct true false false true true false true true \$d9

..def ........oct false true false true true false true true \$da

..def ........oct true true false true true false true true \$db

..def ........oct false false true true true false true true \$dc

..def ........oct true false true true true false true true \$dd

..def ........oct false true true true true false true true \$de

..def ........oct true true true true true false true true \$df

..def ........oct false false false false false true true true \$e0

..def ........oct true false false false false true true true \$e1

..def ........oct false true false false false true true true \$e2

..def ........oct true true false false false true true true \$e3

..def ........oct false false true false false true true true \$e4

..def ........oct true false true false false true true true \$e5

..def ........oct false true true false false true true true \$e6

..def ........oct true true true false false true true true \$e7

..def ........oct false false false true false true true true \$e8

..def ........oct true false false true false true true true \$e9

..def ........oct false true false true false true true true \$ea

..def ........oct true true false true false true true true \$eb

..def ........oct false false true true false true true true \$ec

..def ........oct true false true true false true true true \$ed

..def ........oct false true true true false true true true \$ee

..def ........oct true true true true false true true true \$ef

..def ........oct false false false false true true true true \$f0

..def ........oct true false false false true true true true \$f1

..def ........oct false true false false true true true true \$f2

..def ........oct true true false false true true true true \$f3

..def ........oct false false true false true true true true \$f4

..def ........oct true false true false true true true true \$f5

..def ........oct false true true false true true true true \$f6

..def ........oct true true true false true true true true \$f7

..def ........oct false false false true true true true true \$f8

..def ........oct true false false true true true true true \$f9

..def ........oct false true false true true true true true \$fa

..def ........oct true true false true true true true true \$fb

..def ........oct false false true true true true true true \$fc

..def ........oct true false true true true true true true \$fd

..def ........oct false true true true true true true true \$fe

..def ........oct true true true true true true true true \$ff

# a term like `:a` is both a difference list containing the character 'a' and a

# function that appends the character 'a' to the head of a list

...vireo $00 .cons $00 \'\0' \:\0

...vireo $07 .cons $07 \'\a' \:\a

...vireo $08 .cons $08 \'\b' \:\b

...vireo $09 .cons $09 \'\t' \:\t

...vireo $0a .cons $0a \'\n' \:\n

...vireo $0b .cons $0b \'\v' \:\v

...vireo $0c .cons $0c \'\f' \:\f

...vireo $0d .cons $0d \'\r' \:\r

...vireo $1b .cons $1b \'\e' \:\e

...vireo \' $20 .cons $20 \' \: # eg .putc .' ' or .puts .: nil

...vireo $21 .cons $21 \'!' \:!

...vireo $22 .cons $22 \'"' \:"

...vireo $23 .cons $23 \'#' \:#

...vireo $24 .cons $24 \'$' \:$

...vireo $25 .cons $25 \'%' \:%

...vireo $26 .cons $26 \'&' \:&

...vireo $27 .cons $27 \''' \:'

...vireo $28 .cons $28 \'(' \:(

...vireo $29 .cons $29 \')' \:)

...vireo $2a .cons $2a \'*' \:*

...vireo $2b .cons $2b \'+' \:+

...vireo $2c .cons $2c \',' \:,

...vireo $2d .cons $2d \'-' \:-

...vireo $2e .cons $2e \'.' \:.

...vireo $2f .cons $2f \'/' \:/

...vireo $30 .cons $30 \'0' \:0

...vireo $31 .cons $31 \'1' \:1

...vireo $32 .cons $32 \'2' \:2

...vireo $33 .cons $33 \'3' \:3

...vireo $34 .cons $34 \'4' \:4

...vireo $35 .cons $35 \'5' \:5

...vireo $36 .cons $36 \'6' \:6

...vireo $37 .cons $37 \'7' \:7

...vireo $38 .cons $38 \'8' \:8

...vireo $39 .cons $39 \'9' \:9

...vireo $3a .cons $3a \':' \::

...vireo $3b .cons $3b \';' \:;

...vireo $3c .cons $3c \'<' \:<

...vireo $3d .cons $3d \'=' \:=

...vireo $3e .cons $3e \'>' \:>

...vireo $3f .cons $3f \'?' \:?

...vireo $40 .cons $40 \'@' \:@

...vireo $41 .cons $41 \'A' \:A

...vireo $42 .cons $42 \'B' \:B

...vireo $43 .cons $43 \'C' \:C

...vireo $44 .cons $44 \'D' \:D

...vireo $45 .cons $45 \'E' \:E

...vireo $46 .cons $46 \'F' \:F

...vireo $47 .cons $47 \'G' \:G

...vireo $48 .cons $48 \'H' \:H

...vireo $49 .cons $49 \'I' \:I

...vireo $4a .cons $4a \'J' \:J

...vireo $4b .cons $4b \'K' \:K

...vireo $4c .cons $4c \'L' \:L

...vireo $4d .cons $4d \'M' \:M

...vireo $4e .cons $4e \'N' \:N

...vireo $4f .cons $4f \'O' \:O

...vireo $50 .cons $50 \'P' \:P

...vireo $51 .cons $51 \'Q' \:Q

...vireo $52 .cons $52 \'R' \:R

...vireo $53 .cons $53 \'S' \:S

...vireo $54 .cons $54 \'T' \:T

...vireo $55 .cons $55 \'U' \:U

...vireo $56 .cons $56 \'V' \:V

...vireo $57 .cons $57 \'W' \:W

...vireo $58 .cons $58 \'X' \:X

...vireo $59 .cons $59 \'Y' \:Y

...vireo $5a .cons $5a \'Z' \:Z

...vireo $5b .cons $5b \'[' \:[

...vireo $5c .cons $5c \'\' \:\

...vireo $5d .cons $5d \']' \:]

...vireo $5e .cons $5e \'^' \:^

...vireo $5f .cons $5f \'_' \:_

...vireo $60 .cons $60 \'`' \:`

...vireo $61 .cons $61 \'a' \:a

...vireo $62 .cons $62 \'b' \:b

...vireo $63 .cons $63 \'c' \:c

...vireo $64 .cons $64 \'d' \:d

...vireo $65 .cons $65 \'e' \:e

...vireo $66 .cons $66 \'f' \:f

...vireo $67 .cons $67 \'g' \:g

...vireo $68 .cons $68 \'h' \:h

...vireo $69 .cons $69 \'i' \:i

...vireo $6a .cons $6a \'j' \:j

...vireo $6b .cons $6b \'k' \:k

...vireo $6c .cons $6c \'l' \:l

...vireo $6d .cons $6d \'m' \:m

...vireo $6e .cons $6e \'n' \:n

...vireo $6f .cons $6f \'o' \:o

...vireo $70 .cons $70 \'p' \:p

...vireo $71 .cons $71 \'q' \:q

...vireo $72 .cons $72 \'r' \:r

...vireo $73 .cons $73 \'s' \:s

...vireo $74 .cons $74 \'t' \:t

...vireo $75 .cons $75 \'u' \:u

...vireo $76 .cons $76 \'v' \:v

...vireo $77 .cons $77 \'w' \:w

...vireo $78 .cons $78 \'x' \:x

...vireo $79 .cons $79 \'y' \:y

...vireo $7a .cons $7a \'z' \:z

...vireo $7b .cons $7b \'{' \:{

...vireo $7c .cons $7c \'|' \:|

...vireo $7d .cons $7d \'}' \:}

...vireo $7e .cons $7e \'~' \:~

 # type class definitions and utility instances

..def \equal \eq .eq equal \eq

..def \uneq \eq .eq uneq \uneq

..def .uneq \equal equal \equal # \rhs \lhs

..def .uneq .blackbird not \unequal

..def \eq \compare \ord ..ord eq compare \ord

..def \unord \ord .ord unord \unord

..def .unord \eq \compare eq \ord:eq

..def .unord \eq \compare compare \compare # \rhs \lhs

# return the right-hand side when the arguments compare equal

..def \ord \lhs \rhs ......compare ord rhs lhs rhs rhs lhs \min

..def \ord \lhs \rhs ......compare ord rhs lhs lhs rhs rhs \max

..def \ord \sgrp .sgrp .min ord \min:sgrp

..def \ord \sgrp .sgrp .max ord \max:sgrp

..def \ord \bndd .bndd \top \bot \mnid ..mnid .min:sgrp ord top \min:mnid

..def \ord \bndd .bndd \top \bot \mnid ..mnid .max:sgrp ord bot \max:mnid

# return the argument when it is equal to one or both bounds

..def \ord \lo \hi ..bluebird ..min ord hi ..max ord lo \clamp

..def \ord \lo \hi \val ..and

.isge ...compare ord lo val

.isle ...compare ord hi val

\clamped

# the reverse ordering, obtained by swapping arguments to `compare`

..def .unord \inner:eq \innercompare

..ord inner:eq .cardinal innercompare

\down:ord

..def \top \bot \bndd ..bndd top bot \bndd

..def \unbndd \bndd .bndd unbndd \unbndd

..def .unbndd \top \bot top \top

..def .unbndd \top \bot bot \bot

# the reverse bounding, obtained by swapping `top` and `bot`

..def .unbndd \innertop \innerbot

..bndd innerbot innertop

\down:bndd

# a minimalistic programmer-facing debug representation. there is no requirement

# for the output to be unambiguous.

# debug :: Dbg a => a -> Dlist U8

..def \debug \dbg .dbg debug \dbg

..def \undbg \dbg .dbg undbg \undbg

..def .undbg \debug debug \debug

# the debugged debugging, prints out a `DList U8` as itself

..def .dbg id \dbgged:dbg

# the character debugging, prints out a `U8` as itself

..def .dbg cons \chr:dbg

# places a debugging before, after or within `Dlist U8`s

..def \right .undbg \innerdebug

.dbg \inner ..bluebird .innerdebug inner right

\before:dbg

..def \left .undbg \innerdebug

.dbg \inner ..bluebird left .innerdebug inner

\after:dbg

..def \left \right .undbg \innerdebug

.dbg \inner ...becard left .innerdebug inner right

\within:dbg

..def ..within:dbg :( :) \paren:dbg

..def ..within:dbg :[ :] \brack:dbg

..def ..within:dbg :{ :} \brace:dbg

..def ..within:dbg :< :> \angle:dbg

..def ..within:dbg :" :" \quote:dbg

..def ..within:dbg :' :' \acute:dbg

..def ..within:dbg :` :` \grave:dbg

..def ..within:dbg : : \space:dbg

# sequencing of evaluation order. forcing a call to `force` forces the first

# argument then evaluates to the second argument. partially applying `force`

# effectively gives you a "forcing" identity function: a function which returns

# its argument but which also forces some other unrelated computation. `force`

# on a unit type is the identity function. `force` on a void type is void.

# `force` on a sum type forces component types by case analysis. `force` on a

# product type forces all component types and composes the results together.

# for example, forcing a list is case analysis for forcing either a `nil` or a

# `cons`, forcing a `nil` is the identity function, and forcing a `cons` is the

# composition of forcing the head and recursively forcing the tail.

# force :: a -> b -> b

..def \force \seq .seq force \seq

..def \unseq \seq .seq unseq \unseq

..def .unseq \force force \force

# the forced sequencing, forces a forcing identity function as itself

..def .seq id \forced:seq

# the lazy sequencing, doesn't actually force the argument. for example, `.force

# .list:seq lazy:seq` forces the shape of a list but doesn't force its elements

..def .seq .kestrel id \lazy:seq

# this `Enum` serves a different purpose than Haskell's `Enum`. this `Enum`

# serves as a best-effort enumeration of the values of a type in no particular

# order. this is used for ordering functions, for example. generally speaking,

# - if a type has a finite set of values, the enumeration tries to be

# exhaustive.

# - if a type has a recursively enumerable set of values, the enumertion tries

# to attain every value in finite time.

# - if a type has a non-recursively enumerable set of value, the enumeration

# tries not to be trivial.

# enumerate :: Enum a => [a]

..def \enumerate \enum .enum enumerate \enum

..def \unenum \enum .enum unenum \unenum

..def .unenum \enumerate enumerate \enumerate

# the reverse enumeration, obtained by reversing `enumerate`

..def .unenum \innerenumerate .enum

...fix \rec \zero ..list \head \tail ..rec ..cons head zero tail zero nil

innerenumerate

\down:enum

..def \sappend \sgrp .sgrp sappend \sgrp

..def \unsgrp \sgrp .sgrp unsgrp \unsgrp

..def .unsgrp \sappend sappend \sappend # \lhs \rhs

# dual semigroup, the semigroup obtained by swapping arguments to `sappend`

..def .unsgrp \sappend .sgrp .cardinal sappend \dual:sgrp

# the left-zero and right-zero semigroups over the carrier set

..def .sgrp kestrel \first:sgrp

..def .sgrp kite \last:sgrp

# can't use `cata` here because the `natf` endofunctor isn't defined yet

..def .unsgrp \sappend \elem .fix \stimes \count

..count ..bluebird .sappend elem stimes elem

\stimes

..def \sgrp \mempty \mnid ..mnid sgrp mempty \mnid

..def \unmnid \mnid .mnid unmnid \unmnid

..def .unmnid \sgrp \mempty sgrp \mnid:sgrp

..def .unmnid \sgrp \mempty mempty \mempty

# dual monoid, the monoid obtained by swapping arguments to `sappend`

..def .unmnid \sgrp \mempty ..mnid .dual:sgrp sgrp mempty \dual:mnid

# the monoid of endomorphisms under composition

..def .sgrp bluebird \endo:sgrp

..def ..mnid endo:sgrp id \endo:mnid

..def .unmnid \sgrp \mempty \elem \count

..count ..stimes sgrp elem mempty

\mtimes

..def \fmap \ftor .ftor fmap \ftor

..def \unftor \ftor .ftor unftor \unftor

..def .unftor \fmap fmap \fmap

..def .unftor \fmap ..bluebird fmap kestrel \fmapk

..def .unftor \fmap ...phi pair .fmap fst .fmap snd \unzip

# the const functor, whose `fmap` is a no-op. it is also the "base" functor for

# `Solo`, with the property `Fix (Const a) ~= Solo a`.

# `data Const a b = Const a deriving Functor`

..def .ftor kestrel \const:ftor

..def .unmnid .unsgrp \innersappend \innermempty

\aptv ...aptv const:ftor .kestrel innermempty innersappend

\const:aptv

..def \ftor \pure \apply \aptv ...aptv ftor pure apply \aptv

..def \unaptv \aptv .aptv unaptv \unaptv

..def .unaptv \ftor \pure \apply ftor \aptv:ftor

..def .unaptv \ftor \pure \apply pure \pure

..def .unaptv \ftor \pure \apply apply \apply

..def \aptv \func \arg1 \arg2

...apply aptv ...fmap .aptv:ftor aptv func arg1 arg2

\lifta2

..def \aptv ..lifta2 aptv thrush \rapply

..def \aptv ..lifta2 aptv kestrel \seql

..def \aptv ..lifta2 aptv kite \seqr

..def \aptv \left \right \inner

...seqr aptv left ...seql aptv inner right

\between

..def \aptv ..bool id .kestrel ..pure aptv unit \when

..def \aptv ..bool .kestrel ..pure aptv unit id \unless

# `(Applicative f, Monoid a) => Monoid (Ap f a)` by lifting the monoid pointwise

..def \aptv .unsgrp \innersappend .sgrp

..lifta2 aptv innersappend

\ap:sgrp

..def \aptv .unmnid \inner:sgrp \innermempty ..mnid

..ap:sgrp aptv inner:sgrp

..pure aptv innermempty

\ap:mnid

# `type Rap f a = Dual (Ap f (Dual a))`

# the monoid given by `Ap` but where effects compose in reverse

..def \inner:sgrp .dual:sgrp .ap:sgrp .dual:sgrp inner:sgrp \rap:sgrp

..def \inner:mnid .dual:mnid .ap:mnid .dual:mnid inner:mnid \rap:mnid

..def \aptv \bind \mnad ..mnad aptv bind \mnad

..def \unmnad \mnad .mnad unmnad \unmnad

..def .unmnad \aptv \bind aptv \mnad:aptv

..def .unmnad \aptv \bind bind \bind

..def \mnad \x \f ...bind mnad x .kestrel f \bindk

..def \mnad ..cardinal .bind mnad id \join

..def \mnad \f \g \x ...bind mnad .f x g \kleisli

# the monoid of Kleisli endomorphisms under Kleisli composition

..def \mnad .sgrp .kleisli mnad \kendo:sgrp

..def \mnad ..mnid .kendo:sgrp mnad .pure .mnad:aptv mnad \kendo:mnid

# the identity monad

..def .ftor id \id:ftor

..def ...aptv id:ftor id id \id:aptv

..def ..mnad id:aptv .cardinal id \id:mnad

..def \aptv \empty \alt \altv ...altv aptv empty alt \altv

..def \unaltv \altv .altv unaltv \unaltv

..def .unaltv \aptv \empty \alt aptv \altv:aptv

..def .unaltv \aptv \empty \alt empty \empty

..def .unaltv \aptv \empty \alt alt \alt # \lhs \rhs

..def \altv ..bool ..pure .altv:aptv altv unit .empty altv \guard

..def \many1 \altv \val

...alt altv ..many1 altv val ..pure .altv:aptv altv nil

\many

..def \many \altv \val

....lifta2 .altv:aptv altv cons val ..many altv val

\many1

...vireo

.fix ..bluebird many many1

.fix ..bluebird many1 many

\many \many1

..def \altv \sep \elem

....lifta2 .altv:aptv altv cons

elem

..many altv ...seqr .altv:aptv altv sep elem

\sepby1

..def \altv \sep \elem

...alt altv

...sepby1 altv sep elem

..pure .altv:aptv altv nil

\sepby

..def \altv \val

...alt altv

...fmap .aptv:ftor .altv:aptv altv some val

..pure .altv:aptv altv none

\option

# the monoid induced by `alt`

..def \altv .sgrp .alt altv \alt:sgrp

..def \altv ..mnid .alt:sgrp altv .empty altv \alt:mnid

# no need for `asum`, it'd be equivalent to `.fold .alt:mnid something:altn`

# `Comonad`, the categorical dual of `Monad`

..def \ftor \extract \extend \cmnd ...cmnd ftor extract extend \cmnd

..def \uncmnd \cmnd .cmnd uncmnd \uncmnd

..def .uncmnd \ftor \extract \extend ftor \cmnd:ftor

..def .uncmnd \ftor \extract \extend extract \extract

..def .uncmnd \ftor \extract \extend extend \extend

..def \cmnd \f \x ...extend cmnd .kestrel f x \extendk

..def \cmnd ..extend cmnd id \duplicate

..def \cmnd \f \g \x .g ...extend cmnd f x \cokleisli

# the monoid of co-Kleisli endomorphisms under co-Kleisli composition

..def \cmnd .sgrp .cokleisli cmnd \cokendo:sgrp

..def \cmnd ..mnid .cokendo:sgrp cmnd .extract cmnd \cokendo:mnid

# the identity comonad

..def ...cmnd id:ftor id id \id:cmnd

# "The Foldable class represents data structures that can be reduced to a

# summary value one element at a time." well that's the list catamorphism, so

# why not output the list directly and let the user consume it as they please?

# `foldr` and `tolist` are interdefinable and both are lazy, so we lose nothing.

# the utility functions typically defined on foldables are specialized to lists,

# and what's more is they can be written using more expressive recursion schemes

# like paramorphisms

..def \tolist \fldb .fldb tolist \fldb

..def \unfldb \fldb .fldb unfldb \unfldb

..def .unfldb \tolist tolist \tolist

# the singleton foldable, folds to a singleton list of itself

..def .fldb \val ..cons val nil \single:fldb

..def \ftor \fldb \sequence \tvsb ...tvsb ftor fldb sequence \tvsb

..def \untvsb \tvsb .tvsb untvsb \untvsb

..def .untvsb \ftor \fldb \sequence ftor \tvsb:ftor

..def .untvsb \ftor \fldb \sequence fldb \tvsb:fldb

..def .untvsb \ftor \fldb \sequence sequence \sequence

# `Distributive`, supposedly the categorical dual of `Traversable`

# distribute :: (Functor f, Distributive g) => f (g a) -> g (f a)

..def \ftor \distribute \dstv ..dstv ftor distribute \dstv

..def \undstv \dstv .dstv undstv \undstv

..def .undstv \ftor \distribute ftor \dstv:ftor

..def .undstv \ftor \distribute distribute \distribute

 # type class instances and utility functions

# catamorphisms, anamorphisms, hylomorphisms, paramorphisms, apomorphisms,

# histomorphisms and futumorphisms.

# data Fix f = Fix (f (Fix f))

# cata :: Functor f => (f a -> a) -> Fix f -> a

# ana :: Functor f => (a -> f a) -> a -> Fix f

# hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b

# para :: Functor f => (f (Pair (Fix f) a) -> a) -> Fix f -> a

# apo :: Functor f => (a -> f (Either (Fix f) a)) -> a -> Fix f

# histo :: Functor f => (f (Cofree f a) -> a) -> Fix f -> a

# futu :: Functor f => (a -> f (Free f a)) -> a -> Fix f

# `..fmap ftor cata` doesn't depend on `init`, so when it gets unrolled during

# evaluation with a concrete `init`, it also gets unrolled in this definition,

# causing a space leak (more correctly, it gets unrolled not in this definition

# but in its specialization to a functor and algebra). to avoid this we create

# an artificial dependency on `init` using `..kite init`. the other morphisms

# get same treatment

..def \ftor \alg .fix \cata \init

.alg ...fmap ftor ..kite init cata init

\cata

..def \ftor \coalg .fix \ana \seed

...fmap ftor ..kite seed ana .coalg seed

\ana

..def \ftor \alg \coalg .fix \hylo \seed

.alg ...fmap ftor ..kite seed hylo .coalg seed

\hylo

..def \ftor \ralg .fix \para \init

.ralg ...fmap ftor ..kite init ..starling pair para init

\para

..def \ftor \rcoalg .fix \apo \seed

...fmap ftor ..kite seed ..res ana id .rcoalg seed

\apo

..def \ftor \cvalg ..bluebird ann .fix \histo \init

...starling cofree cvalg ...fmap ftor ..kite init histo init

\histo

..def \ftor \cvcoalg .fix \futu \seed

..fix \rec ..fmap ftor ..kite seed ..free rec futu .cvcoalg seed

\futu

# these instances belong to `List` but they are located here at the beginning of

# the section because many `Enum` instances depend on them.

#

# the "base" functor for `List`, with the property `Fix (ListF a) ~= List a`.

# `data ListF a b = Cons a b | Nil deriving Functor`

..def .ftor

\func ..list \head \tail ..cons head .func tail nil

\listf:ftor

..def .unmnid .unsgrp \sappend \mempty

..cata listf:ftor ..list sappend mempty

\fold

..def .ftor

\func ..cata listf:ftor ..list ..bluebird cons func nil

\list:ftor

..def ...aptv

list:ftor

\val ..cons val nil

\listfunc \listarg ...cata listf:ftor ...cardinal list nil

# avoiding `fmap` for efficiency. notice the init is `acc` instead of `nil`

\func \acc ...cata listf:ftor ..list ..bluebird cons func acc listarg

listfunc

\list:aptv

..def ..mnad

list:aptv

\listarg \func ...cata listf:ftor ...cardinal list nil

\arg \acc ...cata listf:ftor ..list cons acc .func arg

listarg

\list:mnad

..def ...altv

list:aptv

nil

\listlhs \listrhs

...cata listf:ftor ..list cons listrhs listlhs

\list:altv

..def .fldb

\listval listval

\list:fldb

..def ...tvsb

list:ftor

list:fldb

\elem:aptv ..cata listf:ftor ..list

..lifta2 elem:aptv cons

..pure elem:aptv nil

\list:tvsb

..def .eq \rhs \lhs true \unit:eq

..def .eq \rhs \lhs void \void:eq

..def ..ord unit:eq \rhs \lhs et \unit:ord

..def ..ord void:eq \rhs \lhs void \void:ord

..def ..bndd unit unit \unit:bndd

..def ..bndd void void \void:bndd

..def .dbg \unit id \unit:dbg

..def .dbg \void $err \void:dbg

..def .seq \unit id \unit:seq

..def .seq \void $err \void:seq

..def .enum ..cons unit nil \unit:enum

..def .enum nil \void:enum

..def .sgrp \lhs \rhs unit \unit:sgrp

..def .sgrp \lhs \rhs void \void:sgrp

..def ..mnid unit:sgrp unit \unit:mnid

..def ..mnid void:sgrp void \void:mnid

..def .eq bet \bool:eq

..def ..ord bool:eq ..psi tcord woet \bool:ord

..def ..bndd true false \bool:bndd

..def .dbg ..bool :1 :0 \bool:dbg

..def .seq ..bool id id \bool:seq

..def .enum ..cons false ..cons true nil \bool:enum

# `and:mnid` and `or:mnid` work like `..min:mnid bool:ord bool:bndd` and

# `..max:mnid bool:ord bool:bndd`

..def .sgrp and \and:sgrp

..def .sgrp or \or:sgrp

..def .sgrp bne \bne:sgrp

..def .sgrp bet \bet:sgrp

..def ..mnid and:sgrp true \and:mnid

..def ..mnid or:sgrp false \or:mnid

..def ..mnid bne:sgrp false \bne:mnid

..def ..mnid bet:sgrp false \bet:mnid

..def .eq ..blackbird isgt teq \cmp:eq

..def ..ord cmp:eq tcord \cmp:ord

..def ..bndd gt lt \cmp:bndd

..def .dbg ...cmp :> := :< \cmp:dbg

..def .seq ...cmp id id id \cmp:seq

..def .enum ..cons lt ..cons et ..cons gt nil \cmp:enum

# `tand:mnid` and `tor:mnid` work like `..min:mnid cmp:ord cmp:bndd` and

# `..max:mnid cmp:ord cmp:bndd`

..def .sgrp tand \tand:sgrp

..def .sgrp tor \tor:sgrp

..def .sgrp tcons \tcons:sgrp

..def .sgrp txor \txor:sgrp

..def .sgrp tmul \tmul:sgrp

..def .sgrp tsum \tsum:sgrp

..def .sgrp telse \telse:sgrp

..def .sgrp tnles \tnles:sgrp

..def ..mnid tand:sgrp gt \tand:mnid

..def ..mnid tor:sgrp lt \tor:mnid

..def ..mnid txor:sgrp lt \txor:mnid

..def ..mnid tmul:sgrp gt \tmul:mnid

..def ..mnid tsum:sgrp et \tsum:mnid

..def ..mnid telse:sgrp et \telse:mnid

..def ..mnid tnles:sgrp et \tnles:mnid

..def .ftor

\func ..opt ..bluebird some func none

\opt:ftor

..def ...aptv

opt:ftor

\val .some val

\optfunc \optarg

..optfunc \func ...fmap opt:ftor func optarg none

\opt:aptv

..def ..mnad

opt:aptv

\optarg \func ..optarg func none

\opt:mnad

..def ...altv

opt:aptv

none

\optlhs \optrhs ..optlhs some optrhs

\opt:altv

..def .fldb

...opt cons id nil

\opt:fldb

..def ...tvsb

opt:ftor

opt:fldb

\elem:aptv ..opt

..fmap .aptv:ftor elem:aptv some

..pure elem:aptv none

\opt:tvsb

# `Semigroup a => Monoid (Maybe a)` by adjoining `Nothing` as neutral element

..def .unsgrp \innersappend .sgrp

\lhs \rhs ..rhs ..lhs innersappend some lhs

\optsgrp:sgrp

..def \inner:sgrp ..mnid .optsgrp:sgrp inner:sgrp none \optsgrp:mnid

# no need for `Data.Monoid.First a`, it'd be isomorphic to `Alt Maybe a` and to

# `Semigroup b => Modoid (Maybe b)` for `b ~ Data.Semigroup.First a`.

# no need for `Data.Monoid.Last a`, it'd be isomorphic to `Dual (Alt Maybe a)`

# and to `Semigroup b => Modoid (Maybe b)` for `b ~ Data.Semigroup.Last a`.

#

# these instances need to be lazy in the element instance so we can take their

# fixed points to define the equivalent instances for `Nat`

..def \elem:eq .eq

\rhs \lhs ..rhs

..lhs .cardinal .equal elem:eq .kestrel false

..lhs .kestrel false true

\opt:eq