choice

Source: /nix/store/mls72plk3raskl1r5afh3cl9ik3rn969-source/nix/choice.nix

Module Description

Logic programming and non-deterministic choice combinators.

Built on streams (interleave/done/flatMap), this module provides miniKanren-style combinators for logic programming, backtracking, and exploring multiple solution paths fairly.

Core Concepts

• mzero: Empty/failure (no solutions) = stream.done
• mplus: Fair choice/OR = stream.interleave
• mprod: Conjunction/AND = stream.flatMap

Choice effects return streams of solutions. Use observe to extract the first solution, or observeAll to collect all solutions.

Example

# Try multiple options, first success wins
runFx (observe (
  orElse
    (if false then pure 1 else mzero)
    (pure 2)
))  # => 2

# Generate multiple solutions
runFx (observeAll (
  choice [
    (pure 1)
    (pure 2)
    (pure 3)
  ]
))  # => [1 2 3]

# Conditional choice with guard
numberBetween = n:
  flatMap (x:
    mapM (_: guard (x >= 1 && x <= n)) (pure x)
  ) (choice (map pure (range 1 10)));

Namespace Contents

• mzero - Failure/no solutions
• mplus - Fair binary choice (try both)
• orElse - Try first, fallback to second on failure
• choice - First successful from list
• guard - Conditional continuation
• observe - Extract first solution
• observeAll - Collect all solutions
• ifte - If-then-else for logic
• once - At most one solution

Combinators

choice

N-ary choice - select from list of alternatives.

Tries each alternative in order (fairly interleaved). Returns stream of all solutions from all branches. Empty list produces mzero.

Type Signature

[Fx<S, Stream<S, V>>] -> Fx<S, Stream<S, V>>

Parameters

• alternatives: List of effects to try

Example

runFx (observeAll (
  choice [
    (pure 1)
    (pure 2)
    (pure 3)
  ]
))  # => [1 2 3]

# Empty choice = failure
runFx (observe (choice []))  # => null

See Also

• orElse - Binary choice
• mplus - Fair binary combination

guard

Conditional continuation - succeed if condition holds.

If the predicate is true, continue with computation. Otherwise, fail (produce mzero). Common in logic programming for pruning invalid solution paths.

Type Signature

Bool -> Fx<{}, Stream<{}, {}>>

Parameters

• cond: Boolean condition

Example

# Filter solutions
validNumbers = flatMap (n:
  mapM (_: pure n) (guard (n > 0 && n < 10))
) allNumbers;

See Also

• mzero - Unconditional failure
• Logic programming: constraint satisfaction

ifte

If-then-else for logic programming.

Tests a condition effect. If it produces at least one solution, runs the ‘then’ branch with that solution. Otherwise runs the ‘else’ branch.

Type Signature

Fx<S, Stream<S, V>> -> (V -> Fx<S, Stream<S, U>>) -> Fx<S, Stream<S, U>> -> Fx<S, Stream<S, U>>

Parameters

• cond: Condition to test
• thenBranch: Function applied to first solution if condition succeeds
• elseBranch: Executed if condition produces no solutions

Example

ifte
  (guard (x > 0))
  (_: pure "positive")
  (pure "non-positive")

See Also

• orElse - Simpler fallback pattern
• once - Take first solution

mplus

Fair binary choice - combines two alternatives.

miniKanren-style mplus that fairly interleaves solutions from both branches. Essential for complete search over infinite solution spaces.

Type Signature

Stream<S, V> -> Stream<S, V> -> Stream<S, V>

Parameters

• s1: First alternative
• s2: Second alternative

Example

runFx (observeAll (
  mplus
    (pure 1)
    (pure 2)
))  # => [1 2]

See Also

• orElse - For non-stream effects
• choice - N-ary choice
• Logic programming: fair disjunction (OR)

mzero

Empty choice / failure - yields no solutions.

Represents a computation that fails or has no valid results. Identity element for mplus (choice).

Type Signature

Stream<{}, V> (for any V)

Example

runFx (observe mzero)  # => null (no solution)
runFx (observe (mplus mzero (pure 42)))  # => 42

See Also

• mplus - Combine alternatives
• guard - Conditional failure

observe

Extract the first solution from a choice computation.

Runs the effect and returns the first value from the result stream, or null if no solutions exist. Use this to “commit” to the first successful branch.

Type Signature

Fx<S, Stream<S, V>> -> Fx<S, V | null>

Parameters

• e: Choice effect

Example

runFx (observe (
  choice [
    mzero
    (pure 42)
    (pure 99)
  ]
))  # => 42 (first success)

See Also

• observeAll - Collect all solutions
• once - At most one solution

observeAll

Collect all solutions from a choice computation.

Runs the effect and collects all values from the result stream into a list. Use this to explore the complete solution space.

Type Signature

Fx<S, Stream<S, V>> -> Fx<S, [V]>

Parameters

• e: Choice effect

Example

runFx (observeAll (
  choice [
    (pure 1)
    (pure 2)
    (pure 3)
  ]
))  # => [1 2 3]

See Also

• observe - Just first solution
• Logic programming: solution enumeration

once

At most one solution - commits to first success.

Runs the effect but takes only the first solution if any exists. Useful for pruning the search space when you don’t need all alternatives.

Type Signature

Fx<S, Stream<S, V>> -> Fx<S, Stream<S, V>>

Parameters

• e: Effect to limit

Example

runFx (observeAll (
  once (
    choice [
      (pure 1)
      (pure 2)
      (pure 3)
    ]
  )
))  # => [1]  (only first)

See Also

• observe - Extract first (doesn’t return stream)
• ifte - Conditional based on first solution

orElse

Try first effect, fallback to second on failure.

Attempts the first computation. If it produces no solutions (empty stream), tries the second. More efficient than mplus when you only need the first success.

Type Signature

Fx<S, Stream<S, V>> -> Fx<S, Stream<S, V>> -> Fx<S, Stream<S, V>>

Parameters

• e1: Primary effect
• e2: Fallback effect

Example

divide = x: y:
  orElse
    (if y != 0 then pure (x / y) else mzero)
    (pure 0);  # fallback value

See Also

• mplus - Fair interleaving
• choice - Multiple alternatives

Generated from /nix/store/mls72plk3raskl1r5afh3cl9ik3rn969-source/nix/choice.nix