190: Effect Handler — Logging and Nondeterminism

// Effect Handler — Logging and Nondeterminism
//
// Two separate effect systems:
//   1. Logging: collect log messages without interrupting computation
//   2. Nondeterminism: Choose from a list — the handler produces ALL results
//
// Simulated with the interpreter pattern.  Each "perform" is encoded as a
// data constructor; the handler interprets the tree.

// ── Logging Effect ────────────────────────────────────────────────────────────

enum LogStep<A> {
    Done(A),
    Log(String, Box<dyn FnOnce() -> LogStep<A>>),
}

fn log_done<A>(x: A) -> LogStep<A> {
    LogStep::Done(x)
}

fn log_msg<A: 'static>(msg: impl Into<String>, next: LogStep<A>) -> LogStep<A> {
    LogStep::Log(msg.into(), Box::new(move || next))
}

fn log_bind<A: 'static, B: 'static, F: FnOnce(A) -> LogStep<B> + 'static>(
    step: LogStep<A>,
    f: F,
) -> LogStep<B> {
    match step {
        LogStep::Done(x) => f(x),
        LogStep::Log(msg, cont) => {
            LogStep::Log(msg, Box::new(move || log_bind(cont(), f)))
        }
    }
}

/// Run a logging program: collect all log messages.
fn collect_logs<A>(mut step: LogStep<A>) -> (A, Vec<String>) {
    let mut logs = Vec::new();
    loop {
        match step {
            LogStep::Done(x) => return (x, logs),
            LogStep::Log(msg, cont) => {
                logs.push(msg);
                step = cont();
            }
        }
    }
}

// ── Nondeterminism via the list monad ────────────────────────────────────────
//
// "Choose" from a list = branch on every element.
// The handler runs all branches and concatenates results.
// This is exactly the list monad: bind = flat_map.

fn nd_return<A: Clone>(x: A) -> Vec<A> {
    vec![x]
}

fn nd_bind<A, B, F: Fn(A) -> Vec<B>>(xs: Vec<A>, f: F) -> Vec<B> {
    xs.into_iter().flat_map(f).collect()
}

/// "perform Choose xs" — returns all values as separate branches
fn nd_choose<A: Clone>(xs: Vec<A>) -> Vec<A> {
    xs
}

/// "guard" — keep only branches where the predicate holds
fn nd_guard(cond: bool) -> Vec<()> {
    if cond { vec![()] } else { vec![] }
}

fn main() {
    // ── Logging handler demo ───────────────────────────────────────────
    let program1 = {
        let x = 42_i32;
        log_bind(
            log_msg("starting", log_done(())),
            move |_| {
                log_bind(
                    log_msg(format!("x = {}", x), log_done(())),
                    move |_| {
                        log_bind(
                            log_msg("done", log_done(())),
                            move |_| log_done(x * 2),
                        )
                    },
                )
            },
        )
    };
    let (result, logs) = collect_logs(program1);
    println!("result={}, logs=[{}]", result, logs.join("; "));

    println!();

    // ── Nondeterminism via list monad ──────────────────────────────────
    // program2: choose x from [1,2,3], choose y from [10,20], return x+y
    let results = nd_bind(nd_choose(vec![1, 2, 3]), |x| {
        nd_bind(nd_choose(vec![10, 20]), move |y| nd_return(x + y))
    });
    let strs: Vec<String> = results.iter().map(|n| n.to_string()).collect();
    println!("all results: [{}]", strs.join("; "));

    println!();

    // ── Nondeterminism: filter (guard) ────────────────────────────────
    // Find pairs (a,b) where a+b == 5, a in [1..4], b in [1..4]
    let pairs = nd_bind(nd_choose(vec![1, 2, 3, 4]), |a| {
        nd_bind(nd_choose(vec![1, 2, 3, 4]), move |b| {
            nd_bind(nd_guard(a + b == 5), move |_| nd_return((a, b)))
        })
    });
    println!("pairs summing to 5: {:?}", pairs);

    println!();

    // ── All Pythagorean triples ≤ 10 ─────────────────────────────────
    let triples = nd_bind(nd_choose((1..=10).collect()), |a| {
        nd_bind(nd_choose((a..=10).collect()), move |b| {
            nd_bind(nd_choose((b..=10).collect()), move |c| {
                nd_bind(nd_guard(a * a + b * b == c * c), move |_| nd_return((a, b, c)))
            })
        })
    });
    println!("Pythagorean triples ≤10: {:?}", &triples[..triples.len().min(5)]);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_collect_logs_captures_messages() {
        let prog = log_bind(
            log_msg("msg1", log_done(())),
            |_| log_bind(log_msg("msg2", log_done(())), |_| log_done(99_i32)),
        );
        let (val, logs) = collect_logs(prog);
        assert_eq!(val, 99);
        assert_eq!(logs, vec!["msg1", "msg2"]);
    }

    #[test]
    fn test_nondeterminism_all_combinations() {
        let results = nd_bind(nd_choose(vec![1, 2, 3]), |x| {
            nd_bind(nd_choose(vec![10, 20]), move |y| nd_return(x + y))
        });
        assert_eq!(results.len(), 6);
        assert!(results.contains(&11)); // 1+10
        assert!(results.contains(&23)); // 3+20
    }

    #[test]
    fn test_guard_filters_correctly() {
        let pairs = nd_bind(nd_choose(vec![1, 2, 3, 4]), |a| {
            nd_bind(nd_choose(vec![1, 2, 3, 4]), move |b| {
                nd_bind(nd_guard(a + b == 5), move |_| nd_return((a, b)))
            })
        });
        assert_eq!(pairs.len(), 4); // (1,4),(2,3),(3,2),(4,1)
        assert!(pairs.contains(&(1, 4)));
        assert!(pairs.contains(&(4, 1)));
    }

    #[test]
    fn test_log_preserves_order() {
        let prog = log_bind(
            log_msg("first", log_done(())),
            |_| log_bind(
                log_msg("second", log_done(())),
                |_| log_bind(
                    log_msg("third", log_done(())),
                    |_| log_done(0_i32),
                ),
            ),
        );
        let (_, logs) = collect_logs(prog);
        assert_eq!(logs, vec!["first", "second", "third"]);
    }
}