Zulip Chat Archive

Stream: lean4

Topic: Termination in Computed Fields


Andrés Goens (Dec 01 2022 at 15:02):

Is there a way to show termination for a computed_field function? A simple example for the depth of a tree:

inductive NatTree where
    | leaf (val : Nat) : NatTree
    | parent (val : Nat) (children : List NatTree) : NatTree
with
    @[computed_field] depth : NatTree  Nat
      | .leaf _ => 1
      | .parent _ []  => 1
      -- | .parent a (ch::chs) => 1 + max (depth ch) (depth $ NatTree.parent a chs)
      -- computed field NatTree.depth does not reduce for constructor NatTree.parent
      | .parent a ch@(_::_) => 1 + (ch.map depth).maximum?.get!
        decreasing_by sorry
      --^ expected command

The first option would go through with structural recursion but won't work (I imagine that's the same as the TODO for patterns like .app (.app a b) c), whereas the second option won't go through without termination and it seems I can't add some termination to that.


Last updated: Dec 20 2023 at 11:08 UTC