def insert_by_perm

bend-mathlib@0.8.1.0 · perm.bend:90

import Base
import bendlib-kernel-list@1.0.0.0/list.bend as K

90# Inserting x into xs permutes x <> xs.
91def insert_by_perm(~A: Data, ~le: A -> A -> Bool, +x: A, +xs: List<&2, A>) -> K.perm(A, x <> xs, insert_by(~A, ~le, x, xs)):
92  match xs:
93    case Nil{}:
94      perm_refl(A, x <> Nil{})
95    case +y <> t:
96      internal_ins_pick(A, le(x, y), x, y, t, insert_by(~A, ~le, x, t), insert_by_perm(~A, ~le, x, t))