markov.gno

  1// Package markov is a deterministic Markov-chain text generator — a port of
  2// Go's canonical example "Generating arbitrary text: a Markov chain algorithm"
  3// (https://go.dev/doc/codewalk/markov/) with math/rand replaced by a
  4// caller-supplied seed.
  5//
  6// It is a pure library: it imports no chain APIs and reads no ambient state.
  7// A [Chain] maps every PrefixLen-word prefix to the list of words observed to
  8// follow it (duplicates kept, so frequency biases the walk), storing that map
  9// in a persistent avl.Tree. Build folds text into the chain; Generate walks it
 10// from the start prefix, picking one suffix per step from a small LCG seeded by
 11// the uint64 the caller passes — so generation is deterministic and replayable,
 12// and the caller decides where entropy comes from (on-chain, the block height).
 13//
 14// A realm wires it up by holding a *Chain in a package-level var, calling Build
 15// to grow the corpus and Generate with a height-derived seed. For a complete,
 16// live example see the demo realm
 17// [r/moul/x/daily/markovdemo](/r/moul/x/daily/markovdemo/v0).
 18package markov
 19
 20import (
 21	"strings"
 22
 23	"gno.land/p/nt/avl/v0"
 24)
 25
 26// PrefixLen is the number of words in a prefix. Two is the classic choice from
 27// the Go codewalk: long enough to sound plausible, short enough to keep the
 28// chain well-connected.
 29const PrefixLen = 2
 30
 31// Prefix is a sliding window of the last PrefixLen words seen. It mirrors the
 32// Prefix type in the original program.
 33type Prefix []string
 34
 35// key joins the prefix into the string used as the chain's map key. Two empty
 36// strings (the initial prefix) join to a single space " ", which is exactly
 37// the start-of-text key both Build and Generate begin from.
 38func (p Prefix) key() string { return strings.Join(p, " ") }
 39
 40// shift drops the oldest word and appends word, advancing the window by one.
 41func (p Prefix) shift(word string) {
 42	copy(p, p[1:])
 43	p[len(p)-1] = word
 44}
 45
 46// suffixList is the value stored per prefix: every word observed to follow it,
 47// in order (duplicates kept so frequency biases the random walk, just like the
 48// original []string in the chain map).
 49type suffixList struct {
 50	words []string
 51}
 52
 53// Chain is a Markov chain over a persistent avl.Tree. table maps prefix key ->
 54// *suffixList; prefix is the rolling build window so successive Build calls
 55// extend one continuous corpus rather than restarting; words is the running
 56// word count.
 57type Chain struct {
 58	table  avl.Tree
 59	prefix Prefix
 60	words  int
 61}
 62
 63// New returns an empty Chain ready to Build into.
 64func New() *Chain {
 65	return &Chain{prefix: make(Prefix, PrefixLen)}
 66}
 67
 68// Build tokenizes text on whitespace and folds each word into the chain,
 69// recording it as a suffix of the current prefix and then shifting. It returns
 70// the number of words added. This is the analogue of Chain.Build from the
 71// codewalk.
 72func (c *Chain) Build(text string) int {
 73	added := 0
 74	for _, w := range strings.Fields(text) {
 75		k := c.prefix.key()
 76		var sl *suffixList
 77		if c.table.Has(k) {
 78			sl = c.table.Get(k).(*suffixList)
 79		} else {
 80			sl = &suffixList{}
 81		}
 82		sl.words = append(sl.words, w)
 83		c.table.Set(k, sl)
 84		c.prefix.shift(w)
 85		c.words++
 86		added++
 87	}
 88	return added
 89}
 90
 91// Generate walks the chain from the start prefix, picking one suffix per step
 92// via an LCG seeded by seed, and returns up to n words. It stops early if it
 93// reaches a prefix with no recorded suffixes (a dead end). Pure: the same
 94// (n, seed) always yields the same words for a given chain.
 95func (c *Chain) Generate(n int, seed uint64) []string {
 96	if n <= 0 {
 97		return nil
 98	}
 99	p := make(Prefix, PrefixLen)
100	rng := seed
101	out := make([]string, 0, n)
102	for i := 0; i < n; i++ {
103		k := p.key()
104		if !c.table.Has(k) {
105			break
106		}
107		choices := c.table.Get(k).(*suffixList).words
108		if len(choices) == 0 {
109			break
110		}
111		rng = nextRand(rng)
112		// use high bits of the LCG state — its low bits have short periods
113		idx := int((rng >> 33) % uint64(len(choices)))
114		next := choices[idx]
115		out = append(out, next)
116		p.shift(next)
117	}
118	return out
119}
120
121// Stats returns (totalWords, prefixCount) for the current chain.
122func (c *Chain) Stats() (int, int) {
123	return c.words, c.table.Size()
124}
125
126// Iterate calls fn for each prefix in ascending key order, passing the prefix
127// key and the list of words recorded to follow it. Returning true from fn stops
128// the iteration early; Iterate reports whether it was stopped that way.
129func (c *Chain) Iterate(fn func(prefix string, suffixes []string) bool) bool {
130	return c.table.Iterate("", "", func(k string, v interface{}) bool {
131		return fn(k, v.(*suffixList).words)
132	})
133}
134
135// nextRand is a 64-bit linear congruential generator (the PCG/Knuth
136// multiplier + increment). Deterministic and dependency-free — all the
137// entropy comes from the caller's seed.
138func nextRand(s uint64) uint64 {
139	return s*6364136223846793005 + 1442695040888963407
140}