initial commit

16 files changed, 300 insertions, 0 deletions

diff --git a/license b/license
new file mode 100644
index 0000000..4250710
--- /dev/null
+++ b/license
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2024 Marvin Borner
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/package.json b/package.json
new file mode 100644
index 0000000..53c6df9
--- /dev/null
+++ b/package.json
@@ -0,0 +1,22 @@
+{
+  "name": "picomonad",
+  "version": "1.0.0",
+  "description": "The tiniest monad implementations",
+  "type": "module",
+  "scripts": {
+    "test": "echo \"Error: no test specified\" && exit 1"
+  },
+  "repository": {
+    "type": "git",
+    "url": "git+https://github.com/marvinborner/picomonad.git"
+  },
+  "keywords": [
+    "monad"
+  ],
+  "author": "Marvin Borner",
+  "license": "MIT",
+  "bugs": {
+    "url": "https://github.com/marvinborner/picomonad/issues"
+  },
+  "homepage": "https://github.com/marvinborner/picomonad#readme"
+}
diff --git a/readme.txt b/readme.txt
new file mode 100644
index 0000000..354b121
--- /dev/null
+++ b/readme.txt
@@ -0,0 +1,8 @@
+picomonad
+---------
+
+the tiniest monads!
+
+explanation in https://text.marvinborner.de/2024-11-18-00.html
+
+see more samples in samples/
diff --git a/samples/either.js b/samples/either.js
new file mode 100644
index 0000000..e9ad679
--- /dev/null
+++ b/samples/either.js
@@ -0,0 +1,19 @@
+import * as either from "../src/either.js"
+import * as fs from "fs"
+
+function divide(a, b) {
+    if (b === 0)
+        return either.Left("Error: Division by zero!")
+    return either.Right(a / b)
+}
+
+// try piping 42 or 0 into stdin
+const input = +fs.readFileSync(0, "utf-8");
+const result = either.DO(function* () {
+    const a = yield divide(42, input)
+    const b = yield divide(42, a)
+    const c = yield divide(b, a)
+    return c
+})
+
+console.log(either.show(result));
diff --git a/samples/io.js b/samples/io.js
new file mode 100644
index 0000000..a2a0ff0
--- /dev/null
+++ b/samples/io.js
@@ -0,0 +1,42 @@
+import * as io from "../src/io.js"
+import * as fs from "fs"
+
+const writeLine = str => io.DO(function* () {
+    const head = str[0]
+    const tail = str.slice(1)
+
+    yield io.write(head)
+    yield tail === "" ? io.write('\n') : writeLine(tail)
+})
+
+const readLine = io.bind(io.read)(ch =>
+    ch === '\r' ? io.unit("")
+                : io.bind(readLine)(line => io.unit(ch + line))
+)
+
+const nodeEffects = () => {
+    process.stdin.setRawMode(true)
+    const buffer = Buffer.alloc(1)
+    const fd = fs.openSync("/dev/tty", "rs")
+    return {
+        write: process.stdout.write.bind(process.stdout),
+        read: () => {
+            fs.readSync(fd, buffer, 0, 1)
+            return buffer.toString("utf8")
+        }
+    }
+}
+
+const Person = name => age => person => person(name)(age)
+
+const constructPerson = io.DO(function* () {
+    yield writeLine("Please enter your name!")
+    const name = yield readLine
+    yield writeLine(`Hello ${name}! Now please enter your age.`)
+    const age = yield readLine
+    return Person(name)(age) // arbitrary data!
+})
+
+console.log(constructPerson(nodeEffects())(st => v => v(
+    name => age => `Person(name: ${name}, age: ${age})`
+)));
diff --git a/samples/maybe.js b/samples/maybe.js
new file mode 100644
index 0000000..0276f94
--- /dev/null
+++ b/samples/maybe.js
@@ -0,0 +1,18 @@
+import * as maybe from "../src/maybe.js"
+import * as fs from "fs"
+
+function divide(a, b) {
+    if (b === 0)
+        return maybe.Nothing
+    return maybe.Just(a / b)
+}
+
+const input = +fs.readFileSync(0, "utf-8");
+const result = maybe.DO(function* () {
+    const a = yield divide(42, input)
+    const b = yield divide(42, a)
+    const c = yield divide(b, a)
+    return c
+})
+
+console.log(maybe.show(result))
diff --git a/samples/parser.js b/samples/parser.js
new file mode 100644
index 0000000..80d4aaa
--- /dev/null
+++ b/samples/parser.js
@@ -0,0 +1,13 @@
+import * as parser from "../src/parser.js"
+import * as fs from "fs"
+
+// try piping "Hello, World" into stdin!
+const input = fs.readFileSync(0, "utf-8");
+
+const parse = parser.DO(function* () {
+    const p = yield parser.string("Hello")
+    yield parser.char(',')
+    yield parser.char(' ')
+    return p
+})
+console.log(parser.show(parse(input)))
diff --git a/samples/state_lambda.js b/samples/state_lambda.js
new file mode 100644
index 0000000..8cebcec
--- /dev/null
+++ b/samples/state_lambda.js
@@ -0,0 +1,37 @@
+// translating de Bruijn levels in lambda terms to unique variables
+import * as state from '../src/state.js'
+
+const Abs = n => m => abs => app => lvl => abs(n)(m)
+const App = f => x => abs => app => lvl => app(f)(x)
+const Lvl =      l => abs => app => lvl => lvl(l)
+
+const transform = term => term
+    // case: Abstraction
+    (_ => m => state.DO(function* () {
+        const {ctr, stk} = yield state.get
+        yield state.put({ctr: ctr + 1, stk: [ctr, ...stk]})
+        const _m = yield transform(m)
+        yield state.modify(({ctr}) => ({ctr, stk}))
+        return Abs(ctr)(_m)
+    }))
+    // case: Application
+    (f => x => state.ap
+        (state.fmap(App)(transform(f)))
+        (transform(x))
+    )
+    // case: de Bruijn level
+    (l => state.DO(function* () {
+        const {stk} = yield state.get
+        return Lvl(stk[stk.length - l - 1])
+    }))
+
+const prettyTerm = term => term
+    (n => m => `λ${n}.${prettyTerm(m)}`)
+    (f => x => `(${prettyTerm(f)} ${prettyTerm(x)})`)
+    (l => l)
+
+// (λλ(0 0) λ0)
+const term = App(Abs()(Abs()(App(Lvl(0))(Lvl(0)))))(Abs()(Lvl(0)))
+
+console.log(transform(term)({ctr: 0, stk: []})(_ => t => prettyTerm(t)))
+// (λ0.λ1.(0 0) λ2.2)
diff --git a/samples/state_rng.js b/samples/state_rng.js
new file mode 100644
index 0000000..efb8ff3
--- /dev/null
+++ b/samples/state_rng.js
@@ -0,0 +1,14 @@
+import * as state from '../src/state.js'
+
+const rng = max => seed => (1103515245 * seed + 12345) % max
+const rand = seed => (g => state.State(g)(g))(rng(1000)(seed))
+
+// or, simply:
+const threeNumbers = state.DO(function* () {
+    const a = yield rand
+    const b = yield rand
+    const c = yield rand
+    return [a, b, c]
+})
+
+console.log(threeNumbers(161)(st => v => v)) // [790, 895, 620]
diff --git a/samples/state_writer.js b/samples/state_writer.js
new file mode 100644
index 0000000..081e9f1
--- /dev/null
+++ b/samples/state_writer.js
@@ -0,0 +1,13 @@
+import * as state from '../src/state.js'
+
+const log = (a, str) => st => state.State(a)(st + str)
+
+const deepthought = state.DO(function* () {
+    const answer = yield log(42, "Finding answer... ")
+    const correct = yield log(answer == 42, "Checking answer... ")
+    if (correct) yield log(null, "Is correct!") 
+    else yield log(null, "Is false!")
+    return answer
+})
+
+console.log(deepthought("")(log => answer => ({answer, log})))
diff --git a/src/either.js b/src/either.js
new file mode 100644
index 0000000..75b3c4c
--- /dev/null
+++ b/src/either.js
@@ -0,0 +1,17 @@
+import * as wrapper from "./wrapper.js"
+
+export const Left  = v => left => right => left(v)
+export const Right = v => left => right => right(v)
+
+export const isLeft  = either => either(true)(_ => false)
+export const isRight = either => either(false)(_ => true)
+
+export const getLeft  = left  => left(v => v)()
+export const getRight = right => right()(v => v)
+
+export const show = either => either(v => "Left " + v)(v => "Right " + v)
+
+export const unit = Right
+export const bind = mx => f => mx(Left)(f)
+
+export const DO = wrapper.DO(unit, bind)
diff --git a/src/io.js b/src/io.js
new file mode 100644
index 0000000..27f46b6
--- /dev/null
+++ b/src/io.js
@@ -0,0 +1,9 @@
+import * as state from "./state.js"
+
+export const read =        st => s => s(st)(st.read())
+export const write = ch => st => s => s(st)(st.write(ch))
+
+export const unit = state.unit
+export const bind = state.bind
+
+export const DO = state.DO
diff --git a/src/maybe.js b/src/maybe.js
new file mode 100644
index 0000000..3d83b20
--- /dev/null
+++ b/src/maybe.js
@@ -0,0 +1,16 @@
+import * as wrapper from "./wrapper.js"
+
+export const Nothing   = nothing => just => nothing
+export const Just = v => nothing => just => just(v)
+
+export const isNothing = maybe => maybe(true)(_ => false)
+export const isJust    = maybe => maybe(false)(_ => true)
+
+export const getValue = just => just()(v => v)
+
+export const show = maybe => maybe("Nothing")(v => "Just " + v)
+
+export const unit = Just
+export const bind = mx => f => mx(mx)(f)
+
+export const DO = wrapper.DO(unit, bind)
diff --git a/src/parser.js b/src/parser.js
new file mode 100644
index 0000000..a15c8e2
--- /dev/null
+++ b/src/parser.js
@@ -0,0 +1,28 @@
+import * as wrapper from "../src/wrapper.js"
+import * as either from "../src/either.js"
+
+export const show = either =>
+    either(v => "Error: " + v)(v => v(cur => rst => ({ cur, rst })))
+
+export const unit = cur => rst => either.Right(s => s(cur)(rst))
+export const bind = p => f => s => either.bind(p(s))(right => right(cur => rst => f(cur)(rst)))
+
+export const DO = wrapper.DO(unit, bind)
+
+export const satisfy = pred => s => {
+    if (s === "") return either.Left("end of input")
+    const head = s[0]
+    const tail = s.slice(1)
+    return pred(head) ? either.Right(s => s(head)(tail))
+                      : either.Left("unexpected " + head)
+}
+
+export const char = ch => satisfy(c => c == ch)
+
+export const string = str => DO(function* () {
+    const head = str[0]
+    const tail = str.slice(1)
+    yield char(head)
+    return yield tail === "" ? unit(str)
+                             : bind(string(tail))(_ => unit(str))
+})
diff --git a/src/state.js b/src/state.js
new file mode 100644
index 0000000..8db6be4
--- /dev/null
+++ b/src/state.js
@@ -0,0 +1,15 @@
+import * as wrapper from "./wrapper.js"
+
+export const State = v => st => s => s(st)(v)
+
+export const get =         st => s => s(st)(st)
+export const put =  _st => st => s => s(_st)()
+export const modify = f => st => s => s(f(st))()
+
+export const fmap = f => g => st0 => g(st0)(st1 => a => s => s(st1)(f(a)))
+export const ap = f0 => x0 => st0 => f0(st0)(st1 => f1 => x0(st1)(st2 => x1 => s => s(st2)(f1(x1))))
+
+export const unit = State
+export const bind = run => f => s0 => run(s0)(s1 => v => f(v)(s1))
+
+export const DO = wrapper.DO(unit, bind)
diff --git a/src/wrapper.js b/src/wrapper.js
new file mode 100644
index 0000000..8ab8eac
--- /dev/null
+++ b/src/wrapper.js
@@ -0,0 +1,8 @@
+export const DO = (unit, bind) => f => {
+    const gen = f()
+    const next = acc => {
+        const {done, value} = gen.next(acc)
+        return done ? unit(value) : bind(value)(next)
+    }
+    return next()
+}