Zulip Chat Archive
Stream: lean4
Topic: beginner universe question: comparing two nats
Michal Wallace (tangentstorm) (Oct 31 2023 at 17:54):
I am trying to describe a data structure similar to a binary decision diagram, but for representing Boolean expressions in algebraic normal form:
-- ANF: algebraic normal form (a fully expanded sum-of-products polynomial)
-- basically a binary tree, where the V (variable) is ANDed to the HI branch,
-- and the result is XORed to the LO branch.
-- I (looks like a 1) represents "true"
-- O (looks like a 0) represents "false"
inductive ANF : Type
| I : ANF
| O : ANF
| vhl (v : nat) (hi : ANF) (lo : ANF) : ANF
def anf_not (x: ANF) : ANF :=
match x with
| ANF.I => ANF.O
| ANF.O => ANF.I
| ANF.vhl v hi lo => ANF.vhl v hi (anf_not lo)
def anf_xor (x: ANF) (y: ANF) : ANF :=
match x with
| ANF.O => y
| ANF.I => anf_not y
| ANF.vhl v1 hi1 lo1 =>
match y with
| ANF.O => x
| ANF.I => anf_not x
| ANF.vhl v2 hi2 lo2 =>
-- construct a new node with the larger number on top
if v1 > v2 -- <- type mismatch nat+ vs nat+1
then ANF.O -- just a placeholder expression
else ANF.I -- just placeholder expression
The full error I get:
type mismatch
v2
has type
nat✝ : Prop
but is expected to have type
nat✝¹ : Prop
I am aware that there is a concept called universes, but I'm surprised that I'm running into them right off the bat like this, and I have no idea what to do to fix it. Can someone help me understand what's going on here, and what to do instead?
Matthew Ballard (Oct 31 2023 at 17:57):
Capitalize nat
Michal Wallace (tangentstorm) (Oct 31 2023 at 18:01):
well... that did the trick. But why?
Michal Wallace (tangentstorm) (Oct 31 2023 at 18:02):
oh... i see... if it's lowercase, it's just a variable. Thanks, @Matthew Ballard !
Matthew Ballard (Oct 31 2023 at 18:02):
Lean doesn't know what nat
is and tries to make something up for it.
Matthew Ballard (Oct 31 2023 at 18:03):
set_option autoImplicit false
will make it error instead
Matthew Ballard (Oct 31 2023 at 18:04):
And tell you the underlying issue is that nat
is not defined
Last updated: Dec 20 2023 at 11:08 UTC