AFTD Auto-Formalizing Theoretical Domains

Cslib.FreeM

inductiveimported Lean

The Free monad over a type constructor F. A FreeM F a is a tree of operations from the type constructor F, with leaves of type a. It has two constructors: pure for wrapping a value of type a, and liftBind for representing an operation from F followed by a continuation. This construction provides a free monad for any type constructor F, allowing for composable effect descriptions that can be interpreted later. Unlike the traditional free monad, this does not require F to be a functor.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
set_option genInjectivity false in
set_option genSizeOfSpec false in
inductive Cslib.FreeM.{u, v, w} (F : Type u → Type v) (α : Type w)
Defined in
CSLib, `Cslib.FreeM`
Lean proof
By Tanner Duve, Eric Wieser, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2025 Tanner Duve. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
none listed
Used by 84

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
set_option genInjectivity false in
set_option genSizeOfSpec false in
/-- The Free monad over a type constructor `F`. A `FreeM F a` is a tree of operations from the type constructor `F`, with leaves of type `a`. It has two constructors: `pure` for wrapping a value of type `a`, and `liftBind` for representing an operation from `F` followed by a continuation. This construction provides a free monad for any type constructor `F`, allowing for composable effect descriptions that can be interpreted later. Unlike the traditional free monad, this does not require `F` to be a functor. -/
inductive Cslib.FreeM.{u, v, w} (F : Type u → Type v) (α : Type w) where
  /-- The action that does nothing and returns `a`. -/
  | protected pure (a : α) : FreeM F α
  /-- Invoke the operation `op` with contuation `cont`.

  Note that Lean's inductive types prevent us splitting this into separate bind and lift
  constructors. -/
  | liftBind {ι : Type u} (op : F ι) (cont : ι → FreeM F α) : FreeM F α
See it in the graphDiscuss this resultChallenge it