aboutsummaryrefslogtreecommitdiff
path: root/README.md
blob: bf50f615e1c3c1493e9c052b308dc60d49fc6c7a (about) (plain)
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
# algebraic-structures

Provides useful algebraic structures for programming using parametric modules in Chicken Scheme.

## Install

Run `chicken-install` in the project's root directory.

```
$ cd algebraic-structures
$ chicken-install
```

## Usage

### Define Semigroup, Monoid and Group

```scheme
(import (algebraic-structures semigroup)
        (algebraic-structures monoid)
        (algebraic-structures group)
        (algebraic-structures monoid fold)
        (algebraic-structures list foldable))

(module (mod7 semigroup) = (algebraic-structures semigroup)
  (import scheme
          (chicken module))
  (export op)

  (define (op x y)
    (assert (integer? x))
    (assert (integer? y))
    (assert (not (zero? x)))
    (assert (not (zero? y)))
    (modulo (* x y) 7)))

(module (mod7 monoid) = (algebraic-structures monoid)
  (import scheme
          (chicken module)
          (chicken base)
          (only (mod7 semigroup)))
  (reexport (mod7 semigroup))
  (export unit)

  (define unit 1))

(module (mod7 group) = (algebraic-structures group)
  (import scheme
          (chicken base)
          (chicken module)
          matchable
          (only (mod7 monoid)))
  (reexport (mod7 monoid))
  (export inv)

  (define (inv n)
    (assert (integer? n))
    (assert (not (zero? n)))
    (match (modulo n 7)
      (1 1)
      (2 4)
      (3 5)
      (4 2)
      (5 3)
      (6 6))))

(module (mod7 fold) = ((algebraic-structures monoid fold) (mod7 monoid) (algebraic-structures list foldable)))

(import (prefix (mod7 group) mod7:)
        (prefix (mod7 fold) mod7:))
```

In REPL:

```
> (map (cut mod7:pow 3 op) '(0 1 2 3 4 5 6 7 8 9 10 11))
(1 3 2 6 4 5 1 3 2 6 4 5)
> (mod7:fold '(1 2 3 4 5 6))
6
```

### Monad Syntax

```scheme
(import (srfi 41)
        (prefix (algebraic-structures stream monad) stream:)
        (prefix (algebraic-structures stream alternative) stream:))

(define (pythagorean-triples)
  (stream:do (b <- (stream-from 1))
             (a <- (stream-range 1 b))
             (let c^2 = (+ (* a a) (* b b)))
             (let-values (c r) = (exact-integer-sqrt c^2))
             (stream:guard (zero? r))
             (stream (list a b c))))
```

In REPL:

```
> (stream->list (stream-take 10 (pythagorean-triples)))
((3 4 5) (6 8 10) (5 12 13) (9 12 15) (8 15 17) (12 16 20) (15 20 25) (20 21 29) (7 24 25) (10 24 26))
```

## Supported Features

- Semigroup: `(algebraic-structures semigroup)`
    - Number (product): `(algebraic-structures number product semigroup)`
    - Number (sum): `(algebraic-structures number sum semigroup)`
    - List: `(algebraic-structures list semigroup)`
    - Vector: `(algebraic-structures vector semigroup)`
    - Stream: `(algebraic-structures stream semigroup)`
- Semigroup.reduce: `(algebraic-structures semigroup reduce)`
- Monoid: `(algebraic-structures monoid)`
    - Number (product): `(algebraic-structures number product monoid)`
    - Number (sum): `(algebraic-structures number sum monoid)`
    - List: `(algebraic-structures list monoid)`
    - Vector: `(algebraic-structures vector monoid)`
    - Stream: `(algebraic-structures stream monoid)`
- Monoid.fold: `(algebraic-structures monoid fold)`
- Group
    - Number (product): `(algebraic-structures number product group)`
    - Number (sum): `(algebraic-structures number sum group)`
- Foldable: `(algebraic-structures foldable)` 
    - List: `(algebraic-structures list foldable)`
    - Vector: `(algebraic-structures vector foldable)`
    - Stream: `(algebraic-structures stream foldable)`
- Reducible: `(algebraic-structures reducible)` 
    - List: `(algebraic-structures list reducible)`
    - Vector: `(algebraic-structures vector reducible)`
    - Stream: `(algebraic-structures stream reducible)`
- Functor: `(algebraic-structures functor)` 
    - List: `(algebraic-structures list functor)`
    - Vector: `(algebraic-structures vector functor)`
    - Stream: `(algebraic-structures stream functor)`
- Applicative: `(algebraic-structures applicative)` 
    - List: `(algebraic-structures list applicative)`
    - List (zip): `(algebraic-structures list zip applicative)`
    - Vector (zip): `(algebraic-structures vector zip applicative)`
    - Stream: `(algebraic-structures stream applicative)`
    - Stream (zip): `(algebraic-structures stream zip applicative)`
- Monad: `(algebraic-structures monad)` 
    - List: `(algebraic-structures list monad)`
    - Stream: `(algebraic-structures stream monad)`
- Alternative: `(algebraic-structures alternative)` 
    - List: `(algebraic-structures list alternative)`
    - Stream: `(algebraic-structures stream alternative)`

## Examples

- Group
    - [mod7](./examples/mod7.scm)
- Monad
    - [optional](./examples/optional.scm)
    - [state](./examples/state.scm)
- Monad (`do` syntax)
    - [pythagorean-triples](./examples/pythagorean-triples.scm)