Bird R., de Moor O. — Algebra of programming :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Bird R., de Moor O. — Algebra of programming

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Algebra of programming

Авторы: Bird R., de Moor O.

Аннотация:

Describes an algebraic approach to programming that permits the calculation of programs. Introduces the fundamentals of algebra for programming. Presents paradigms and strategies of program construction that form the core of Algorithm Design. Discusses functions and categories; applications; relations and allegories; datatypes; recursive programs, optimization issues, thinning algorithms, dynamic programming and greedy algorithms. Appropriate for all programmers.

Язык:

Рубрика: Computer science/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1997

Количество страниц: 314

Добавлена в каталог: 22.01.2014

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

problem      62 259
$\mu$ -calculus$      161
Absorption law for A      105
Absorption law for products      41 114
Accumulation parameter      7 12 74 77 139
Ackermann's function      6
Addition modulo p      45
Algebra      46
Allegory      81—85
Anti-symmetry      86
Arrows of a category      25
ASCII      1
bags      130
Banana-split law      55 56 78
Base functor      52
Bifunctor      31 40 50
Bijection      29 75
Binary thinning theorem      202
Bitonic tours problem      212
Boolean allegory      101 122
Boolean operators      67
Bottom element      43
Branch-and-bound      243
Bus-stop problem      217
Cancellation law for coproducts      42 118
Cancellation law for division      99
Cancellation law for power transpose      104
Cancellation law for products      39 41 43 116
Carrier (of an algebra)      45
Cartesian closed category      72 75 78
Cartesian product function      125
Case operator      41 42 122
Catamorphism      46
Category      25—30
Closure      157—162
Co-algebra      52
combinatorial functions      123
Company party problem      175
Concatenation      8 70
conditionals      21 66 122
Connected relation      151
Cons-lists      7
Constant arrow      38
Constant functor      31
constructor      1
Constructor classes      23
Context condition      167 223
Continuous mapping      141
contravariance      83
Converse function theorem      128
Coproduct      41—42
Coreflexive      86 122
Currying      2—3 16 44 70 71
Data compression problem      238
datatype      1—3 36—38
Datatype, parameterised      3 49
Datatype, with laws      53
De Morgan's law      101
Decimal representation      11 17 62 137
Dedekinds rule      see "Modular law"
Detab-entab problem      246
Diagonal rule      161
Diagram      27—28
Diagram, commuting      27
Diagram, pasting      35
Diagrammatic form      2
Difunctional arrow      142
Difunctional closure      142
Disjoint union      1 38 42
Distributive category      67
Distributivity      172
Divide and conquer      137 144 146
Domain      26 86
Dominance relation      217
Duality      28—30 41 52 118
Dynamic programming      219
Dynamic programming theorem      220
Eilenberg-Wright Lemma      122
Empty object      38
Entire arrow      88
Epi-monic factorisation      96
Epic arrow      28
EQUIVALENCE      86
Evaluating polynomials      58 62
Exchange law      45
Existential image functor      32 35 105
Existential quantification      102
Exponential      44 72 117
Exponential functor      113
exponentiation      144
F-algebra      45
Factorial function      4 5 57
fibonacci function      4 5
Fixed point induction      141 259
Fixed point, greatest      140
Fixed point, least      140 142
Fixed point, unique      140 146 221
fixpoint      49
FLOOR      65
Fokkinga's Theorem      58
Fold operator      5
Font conventions for datatypes      3
Font conventions for identifiers      30
Forest      15
Function space      see "Exponential"
Functional application      2
Functional composition      2
functor      30—33
Fusion (with the power functor)      168
Fusion law for catamorphisms      48 141
Fusion law for coproducts      42
Fusion law for exponentials      72
Fusion law for power transpose      104
Fusion law for products      39
Fusion law for terminal objects      37 40
Fusion law for type functors      51
Galois connection      100 109
Gofer, xii      1 23 165
Graph algorithms      157
Graph functor      32
Greedoids      191
Greedy theorem      173 245
Haskell      1 22
Hom sentence      95
Homomorphism      5 30 45—46
HOPE      1
Horners rule      58
Horners rule, generalisation of      62
Hylomorphism      142 162
Hylomorphism theorem      144
Hyperproduct      62
Idempotent arrow      90
Identity functor      31 49
Iinjection      17 28 65 68
IMP      see "Simple arrow"
Inclusion functor      32 35
Indirect equality      65 107
Indirect proof      82 102
Induction      147
Inductive relation      147—151 158
Inequation      82
Infinite lists      52
Initial algebra      45—49
Initial object      37—38
Initial type      51
Insertion sort      157
Inverse      16—18 29
Involution      83 101
Isomorphism      29 33 48
Iterative definition      12 14

Jointly monic arrows      92
Kleene's theorem      141
Knapsack problem      205
Knaster-Tarski Theorem      140
Lambek's Lemma      49 142
Large category      31
Lawvere's Recursion Theorem      78
Lax natural transformation      132 148 182
Layered network problem      196
Lazy functional programming      43 45
Lexical ordering      98 175
Linear functor      202
Linear order      152
List comprehension      13
Locale      91
Locally complete allegory      96
Longest upsequence problem      217
Loops      12 264
Lower adjoint      101
Maximum      166
Maximum segment sum problem      174
Membership relation      32 34 103 147—151
Memoisation      219
Mergesort      156
Merging loops      56
Minimal elements      170
Minimum tardiness problem      253
Miranda      1
Modular identity      88
Modular law      84
Modulus computation      145
Monad      52
Monic arrow      28
Monotonic algebra      172
Monotonic functor      see "Relator"
Monotonicity of composition      82
Monotonicity of division      99
Natural isomorphism      34 67
Natural transformation      19 33—35
Naturality condition      34 133
negation operator      2
Non-empty lists      13
Non-empty power object      107
Non-strict constructor      43
Non-strict semantics      22
Nondeterminism      81
Objects of a category      25
One-pass program      56
Opposite category      28
Optimal bracketing problem      230
Orwell      1
Pair operator      39 43
Paragraph problem      190 207
Parallel loop fusion      78
Partial function      26 30 88
Partial order      44 86 108
Partitions      128
Pattern matching      2 66
permutations      130
Ping-pong argument      82
Point-free      19—22
Pointwise      19—22
Polymorphism      18—19 34 35
Polynomial functor      44—45
Power allegory      103 117
Power functor      105
Power object      103
Power relator      119
Power transpose      103
Powerset functor      32
Predicate calculus      28
Predicate transformer      108
Prefix      126
Preorder      30 33 38 75 86 98 108 170
Principle of optimality      219
Problem reduction generator      217
PRODUCT      38—41
Product category      27 40
Projection function      6 39 40 45
Quicksort      154
Rally driver's problem      217
RANGE      26 86
Reciprocal      see "Relational converse"
Recursion      4 137
Recursion, mutual      15
Recursion, non-structural      139
Recursion, primitive      5 6
Recursion, structural      5 10 56
refinement      18 138 194
Reflection law for catamorphisms      48
Reflection law for coprodcuts      42
Reflection law for exponentials      72
Reflection law for products      39
Reflection law for terminal objects      37 40
Reflexivity      86
Regular category      108
Relational algebra      121
Relational catamorphism      121
Relational converse      43 83
Relational coproduct      117
Relational difference      100 159
relational division      98
Relational implication      97
Relational inclusion      82
Relational join      96
Relational meet      83
Relational negation      101
Relational product      114
Relations (as data)      161
Relator      111 134
Retraction      30
Rolling rule      159 161
Ruby      58 78 135
Ruby triangles      58
Rule of floors      63 65
Schroder's rule      103
Security van problem      184
Selection sort      152
Semi-commuting diagram      82
Sequential decision process      217
Set comprehension      104
Set theory      95 104 162 169
Shortest paths problem      179
Shunting rules      89
Simple arrow      88
singleton set      36 37 106
SmL      1
Snoc-lists      7
Sorting      151—157
Sorting sets      200
Source operator      25
Source type      2
spans      40
Squaring functor      31
Strict functional programming      22
String edit problem      225
strings      47
Strong functor      76
Structural recursion theorem      73
Subcategory      26 32 88
Subsequences      123
Substitution rule      162
Suffix      126
Supersequences      132
Supremum operator      170
Surjection      17 28
Surjective relation      149
Symmetry      28 86
Tabulation (of an arrow)      91
Tabulation scheme      6 219 227 233

1 2

О проекте