batteries icon indicating copy to clipboard operation
batteries copied to clipboard

feat: `List.insertP` and lemmas

Open fgdorais opened this issue 1 year ago • 1 comments

List.insertP is a generalized, tail-recursive version of the insert step in insertion-sort. Sample use:

def insertionSort [LT α] [DecidableRel (α:=α) (· < ·)] (l : List α) := 
  l.foldl (fun s a => s.insertP (a < ·) a) [] -- fully tail recursive and stable!

It will be useful to streamline and optimize ac_rfl once moved to Std.

PS: Perhaps someone has a better name?

fgdorais avatar Jan 30 '24 07:01 fgdorais

The ac_rfl move has been canceled so there is no immediate need for this. It's still a useful addition so I'm reluctant to close but closing might be better than rotting.

fgdorais avatar Feb 17 '24 17:02 fgdorais