1// Package markov is a deterministic Markov-chain text generator — a port of2// Go's canonical example "Generating arbitrary text: a Markov chain algorithm"3// (https://go.dev/doc/codewalk/markov/) with math/rand replaced by a4// 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 to8// follow it (duplicates kept, so frequency biases the walk), storing that map9// in a persistent avl.Tree. Build folds text into the chain; Generate walks it10// from the start prefix, picking one suffix per step from a small LCG seeded by11// 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 Build15// to grow the corpus and Generate with a height-derived seed. For a complete,16// live example see the demo realm17// [r/moul/x/daily/markovdemo](/r/moul/x/daily/markovdemo/v0).18package markov1920import (21 "strings"2223 "gno.land/p/nt/avl/v0"24)2526// PrefixLen is the number of words in a prefix. Two is the classic choice from27// the Go codewalk: long enough to sound plausible, short enough to keep the28// chain well-connected.29const PrefixLen = 23031// Prefix is a sliding window of the last PrefixLen words seen. It mirrors the32// Prefix type in the original program.33type Prefix []string3435// key joins the prefix into the string used as the chain's map key. Two empty36// strings (the initial prefix) join to a single space " ", which is exactly37// the start-of-text key both Build and Generate begin from.38func (p Prefix) key() string { return strings.Join(p, " ") }3940// 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] = word44}4546// 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 the48// original []string in the chain map).49type suffixList struct {50 words []string51}5253// 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 calls55// extend one continuous corpus rather than restarting; words is the running56// word count.57type Chain struct {58 table avl.Tree59 prefix Prefix60 words int61}6263// New returns an empty Chain ready to Build into.64func New() *Chain {65 return &Chain{prefix: make(Prefix, PrefixLen)}66}6768// 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 returns70// the number of words added. This is the analogue of Chain.Build from the71// codewalk.72func (c *Chain) Build(text string) int {73 added := 074 for _, w := range strings.Fields(text) {75 k := c.prefix.key()76 var sl *suffixList77 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 added89}9091// Generate walks the chain from the start prefix, picking one suffix per step92// via an LCG seeded by seed, and returns up to n words. It stops early if it93// reaches a prefix with no recorded suffixes (a dead end). Pure: the same94// (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 nil98 }99 p := make(Prefix, PrefixLen)100 rng := seed101 out := make([]string, 0, n)102 for i := 0; i < n; i++ {103 k := p.key()104 if !c.table.Has(k) {105 break106 }107 choices := c.table.Get(k).(*suffixList).words108 if len(choices) == 0 {109 break110 }111 rng = nextRand(rng)112 // use high bits of the LCG state — its low bits have short periods113 idx := int((rng >> 33) % uint64(len(choices)))114 next := choices[idx]115 out = append(out, next)116 p.shift(next)117 }118 return out119}120121// Stats returns (totalWords, prefixCount) for the current chain.122func (c *Chain) Stats() (int, int) {123 return c.words, c.table.Size()124}125126// Iterate calls fn for each prefix in ascending key order, passing the prefix127// key and the list of words recorded to follow it. Returning true from fn stops128// 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}134135// nextRand is a 64-bit linear congruential generator (the PCG/Knuth136// multiplier + increment). Deterministic and dependency-free — all the137// entropy comes from the caller's seed.138func nextRand(s uint64) uint64 {139 return s*6364136223846793005 + 1442695040888963407140}141Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.