control.random ⟷ Mathlib.Control.Random

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -3,7 +3,7 @@ Copyright (c) 2020 Simon Hudon. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Simon Hudon
 -/
-import Control.Uliftable
+import Control.ULiftable
 import Data.Bitvec.Basic
 import Data.Stream.Defs
 import Tactic.NormNum
@@ -290,7 +290,7 @@ instance intBoundedRandom : BoundedRandom ℤ
     where randomR g inst x y hxy := do
     let ⟨z, h₀, h₁⟩ ← @BoundedRandom.randomR ℕ _ _ g inst 0 (Int.natAbs <| y - x) (by decide)
     pure
-        ⟨z + x, Int.le_add_of_nonneg_left (Int.coe_nat_nonneg _),
+        ⟨z + x, Int.le_add_of_nonneg_left (Int.natCast_nonneg _),
           Int.add_le_of_le_sub_right <|
             le_trans (Int.ofNat_le_ofNat_of_le h₁)
               (le_of_eq <| Int.ofNat_natAbs_eq_of_nonneg (Int.sub_nonneg_of_le hxy))⟩

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -318,7 +318,7 @@ theorem bool_ofNat_mem_Icc_of_mem_Icc_toNat (x y : Bool) (n : ℕ) :
   by
   simp only [and_imp, Set.mem_Icc]; intro h₀ h₁
   constructor <;> [have h₂ := Bool.ofNat_le_ofNat h₀; have h₂ := Bool.ofNat_le_ofNat h₁] <;>
-      rw [Bool.ofNat_toNat] at h₂  <;>
+      rw [Bool.ofNat_toNat] at h₂ <;>
     exact h₂
 #align bool_of_nat_mem_Icc_of_mem_Icc_to_nat bool_ofNat_mem_Icc_of_mem_Icc_toNat
 
@@ -332,29 +332,27 @@ instance : BoundedRandom Bool
       @BoundedRandom.randomR ℕ _ _ g _inst x.toNat y.toNat (Bool.toNat_le_toNat p)
 
 /-- generate a random bit vector of length `n` -/
-def Std.BitVec.random (n : ℕ) : RandG g (Std.BitVec n) :=
-  Std.BitVec.ofFin <$> Rand.random (Fin <| 2 ^ n)
-#align bitvec.random Std.BitVec.random
+def BitVec.random (n : ℕ) : RandG g (BitVec n) :=
+  BitVec.ofFin <$> Rand.random (Fin <| 2 ^ n)
+#align bitvec.random BitVec.random
 
 /-- generate a random bit vector of length `n` -/
-def Std.BitVec.randomR {n : ℕ} (x y : Std.BitVec n) (h : x ≤ y) : RandG g (x .. y) :=
-  have h' : ∀ a : Fin (2 ^ n), a ∈ (x.toFin .. y.toFin) → Std.BitVec.ofFin a ∈ (x .. y) :=
+def BitVec.randomR {n : ℕ} (x y : BitVec n) (h : x ≤ y) : RandG g (x .. y) :=
+  have h' : ∀ a : Fin (2 ^ n), a ∈ (x.toFin .. y.toFin) → BitVec.ofFin a ∈ (x .. y) :=
     by
     simp only [and_imp, Set.mem_Icc]; intro z h₀ h₁
-    replace h₀ := Std.BitVec.ofFin_le_ofFin_of_le h₀
-    replace h₁ := Std.BitVec.ofFin_le_ofFin_of_le h₁
-    rw [Std.BitVec.ofFin_toFin] at h₀ h₁ ; constructor <;> assumption
-  Subtype.map Std.BitVec.ofFin h' <$>
-    Rand.randomR x.toFin y.toFin (Std.BitVec.toFin_le_toFin_of_le h)
-#align bitvec.random_r Std.BitVec.randomR
+    replace h₀ := BitVec.ofFin_le_ofFin_of_le h₀
+    replace h₁ := BitVec.ofFin_le_ofFin_of_le h₁
+    rw [BitVec.ofFin_toFin] at h₀ h₁; constructor <;> assumption
+  Subtype.map BitVec.ofFin h' <$> Rand.randomR x.toFin y.toFin (BitVec.toFin_le_toFin_of_le h)
+#align bitvec.random_r BitVec.randomR
 
 open Nat
 
-instance randomBitvec (n : ℕ) : Random (Std.BitVec n)
-    where Randomₓ _ inst := @Std.BitVec.random _ inst n
+instance randomBitvec (n : ℕ) : Random (BitVec n) where Randomₓ _ inst := @BitVec.random _ inst n
 #align random_bitvec randomBitvec
 
-instance boundedRandomBitvec (n : ℕ) : BoundedRandom (Std.BitVec n)
-    where randomR _ inst x y p := @Std.BitVec.randomR _ inst _ _ _ p
+instance boundedRandomBitvec (n : ℕ) : BoundedRandom (BitVec n)
+    where randomR _ inst x y p := @BitVec.randomR _ inst _ _ _ p
 #align bounded_random_bitvec boundedRandomBitvec
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -84,7 +84,7 @@ class BoundedRandom (α : Type u) [Preorder α] where
   randomR : ∀ (g) [RandomGen g] (x y : α), x ≤ y → RandG g (x .. y)
 #align bounded_random BoundedRandomₓ
 
-/- ./././Mathport/Syntax/Translate/Command.lean:404:30: infer kinds are unsupported in Lean 4: #[`Randomₓ] [] -/
+/- ./././Mathport/Syntax/Translate/Command.lean:400:30: infer kinds are unsupported in Lean 4: #[`Randomₓ] [] -/
 /-- `random α` gives us machinery to generate values of type `α` -/
 class Random (α : Type u) where
   Randomₓ : ∀ (g : Type) [RandomGen g], RandG g α

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -84,7 +84,7 @@ class BoundedRandom (α : Type u) [Preorder α] where
   randomR : ∀ (g) [RandomGen g] (x y : α), x ≤ y → RandG g (x .. y)
 #align bounded_random BoundedRandomₓ
 
-/- ./././Mathport/Syntax/Translate/Command.lean:394:30: infer kinds are unsupported in Lean 4: #[`Randomₓ] [] -/
+/- ./././Mathport/Syntax/Translate/Command.lean:404:30: infer kinds are unsupported in Lean 4: #[`Randomₓ] [] -/
 /-- `random α` gives us machinery to generate values of type `α` -/
 class Random (α : Type u) where
   Randomₓ : ∀ (g : Type) [RandomGen g], RandG g α

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -79,20 +79,16 @@ local infixl:41 " .. " => Set.Icc
 
 open Stream'
 
-#print BoundedRandom /-
 /-- `bounded_random α` gives us machinery to generate values of type `α` between certain bounds -/
 class BoundedRandom (α : Type u) [Preorder α] where
   randomR : ∀ (g) [RandomGen g] (x y : α), x ≤ y → RandG g (x .. y)
-#align bounded_random BoundedRandom
--/
+#align bounded_random BoundedRandomₓ
 
-#print Random /-
-/- ./././Mathport/Syntax/Translate/Command.lean:394:30: infer kinds are unsupported in Lean 4: #[`Random] [] -/
+/- ./././Mathport/Syntax/Translate/Command.lean:394:30: infer kinds are unsupported in Lean 4: #[`Randomₓ] [] -/
 /-- `random α` gives us machinery to generate values of type `α` -/
 class Random (α : Type u) where
-  Random : ∀ (g : Type) [RandomGen g], RandG g α
-#align random Random
--/
+  Randomₓ : ∀ (g : Type) [RandomGen g], RandG g α
+#align random Randomₓ
 
 /-- shift_31_left = 2^31; multiplying by it shifts the binary
 representation of a number left by 31 bits, dividing by it shifts it
@@ -121,7 +117,7 @@ section Random
 
 variable [Random α]
 
-export Random (Random)
+export Random (Randomₓ)
 
 /-- Generate a random value of type `α`. -/
 def random : RandG g α :=
@@ -300,7 +296,8 @@ instance intBoundedRandom : BoundedRandom ℤ
               (le_of_eq <| Int.ofNat_natAbs_eq_of_nonneg (Int.sub_nonneg_of_le hxy))⟩
 #align int_bounded_random intBoundedRandom
 
-instance finRandom (n : ℕ) [NeZero n] : Random (Fin n) where Random g inst := @Fin.random g inst _ _
+instance finRandom (n : ℕ) [NeZero n] : Random (Fin n)
+    where Randomₓ g inst := @Fin.random g inst _ _
 #align fin_random finRandom
 
 instance finBoundedRandom (n : ℕ) : BoundedRandom (Fin n)
@@ -326,7 +323,7 @@ theorem bool_ofNat_mem_Icc_of_mem_Icc_toNat (x y : Bool) (n : ℕ) :
 #align bool_of_nat_mem_Icc_of_mem_Icc_to_nat bool_ofNat_mem_Icc_of_mem_Icc_toNat
 
 instance : Random Bool
-    where Random g inst :=
+    where Randomₓ g inst :=
     (Bool.ofNat ∘ Subtype.val) <$> @BoundedRandom.randomR ℕ _ _ g inst 0 1 (Nat.zero_le _)
 
 instance : BoundedRandom Bool
@@ -354,7 +351,7 @@ def Std.BitVec.randomR {n : ℕ} (x y : Std.BitVec n) (h : x ≤ y) : RandG g (x
 open Nat
 
 instance randomBitvec (n : ℕ) : Random (Std.BitVec n)
-    where Random _ inst := @Std.BitVec.random _ inst n
+    where Randomₓ _ inst := @Std.BitVec.random _ inst n
 #align random_bitvec randomBitvec
 
 instance boundedRandomBitvec (n : ℕ) : BoundedRandom (Std.BitVec n)

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -335,27 +335,29 @@ instance : BoundedRandom Bool
       @BoundedRandom.randomR ℕ _ _ g _inst x.toNat y.toNat (Bool.toNat_le_toNat p)
 
 /-- generate a random bit vector of length `n` -/
-def Bitvec.random (n : ℕ) : RandG g (Bitvec n) :=
-  Bitvec.ofFin <$> Rand.random (Fin <| 2 ^ n)
-#align bitvec.random Bitvec.random
+def Std.BitVec.random (n : ℕ) : RandG g (Std.BitVec n) :=
+  Std.BitVec.ofFin <$> Rand.random (Fin <| 2 ^ n)
+#align bitvec.random Std.BitVec.random
 
 /-- generate a random bit vector of length `n` -/
-def Bitvec.randomR {n : ℕ} (x y : Bitvec n) (h : x ≤ y) : RandG g (x .. y) :=
-  have h' : ∀ a : Fin (2 ^ n), a ∈ (x.toFin .. y.toFin) → Bitvec.ofFin a ∈ (x .. y) :=
+def Std.BitVec.randomR {n : ℕ} (x y : Std.BitVec n) (h : x ≤ y) : RandG g (x .. y) :=
+  have h' : ∀ a : Fin (2 ^ n), a ∈ (x.toFin .. y.toFin) → Std.BitVec.ofFin a ∈ (x .. y) :=
     by
     simp only [and_imp, Set.mem_Icc]; intro z h₀ h₁
-    replace h₀ := Bitvec.ofFin_le_ofFin_of_le h₀
-    replace h₁ := Bitvec.ofFin_le_ofFin_of_le h₁
-    rw [Bitvec.ofFin_toFin] at h₀ h₁ ; constructor <;> assumption
-  Subtype.map Bitvec.ofFin h' <$> Rand.randomR x.toFin y.toFin (Bitvec.toFin_le_toFin_of_le h)
-#align bitvec.random_r Bitvec.randomR
+    replace h₀ := Std.BitVec.ofFin_le_ofFin_of_le h₀
+    replace h₁ := Std.BitVec.ofFin_le_ofFin_of_le h₁
+    rw [Std.BitVec.ofFin_toFin] at h₀ h₁ ; constructor <;> assumption
+  Subtype.map Std.BitVec.ofFin h' <$>
+    Rand.randomR x.toFin y.toFin (Std.BitVec.toFin_le_toFin_of_le h)
+#align bitvec.random_r Std.BitVec.randomR
 
 open Nat
 
-instance randomBitvec (n : ℕ) : Random (Bitvec n) where Random _ inst := @Bitvec.random _ inst n
+instance randomBitvec (n : ℕ) : Random (Std.BitVec n)
+    where Random _ inst := @Std.BitVec.random _ inst n
 #align random_bitvec randomBitvec
 
-instance boundedRandomBitvec (n : ℕ) : BoundedRandom (Bitvec n)
-    where randomR _ inst x y p := @Bitvec.randomR _ inst _ _ _ p
+instance boundedRandomBitvec (n : ℕ) : BoundedRandom (Std.BitVec n)
+    where randomR _ inst x y p := @Std.BitVec.randomR _ inst _ _ _ p
 #align bounded_random_bitvec boundedRandomBitvec
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

@@ -3,10 +3,10 @@ Copyright (c) 2020 Simon Hudon. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Simon Hudon
 -/
-import Mathbin.Control.Uliftable
-import Mathbin.Data.Bitvec.Basic
-import Mathbin.Data.Stream.Defs
-import Mathbin.Tactic.NormNum
+import Control.Uliftable
+import Data.Bitvec.Basic
+import Data.Stream.Defs
+import Tactic.NormNum
 
 #align_import control.random from "leanprover-community/mathlib"@"9240e8be927a0955b9a82c6c85ef499ee3a626b8"
 
@@ -87,7 +87,7 @@ class BoundedRandom (α : Type u) [Preorder α] where
 -/
 
 #print Random /-
-/- ./././Mathport/Syntax/Translate/Command.lean:393:30: infer kinds are unsupported in Lean 4: #[`Random] [] -/
+/- ./././Mathport/Syntax/Translate/Command.lean:394:30: infer kinds are unsupported in Lean 4: #[`Random] [] -/
 /-- `random α` gives us machinery to generate values of type `α` -/
 class Random (α : Type u) where
   Random : ∀ (g : Type) [RandomGen g], RandG g α

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

@@ -2,17 +2,14 @@
 Copyright (c) 2020 Simon Hudon. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Simon Hudon
-
-! This file was ported from Lean 3 source module control.random
-! leanprover-community/mathlib commit 9240e8be927a0955b9a82c6c85ef499ee3a626b8
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Control.Uliftable
 import Mathbin.Data.Bitvec.Basic
 import Mathbin.Data.Stream.Defs
 import Mathbin.Tactic.NormNum
 
+#align_import control.random from "leanprover-community/mathlib"@"9240e8be927a0955b9a82c6c85ef499ee3a626b8"
+
 /-!
 # Rand Monad and Random Class
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/9240e8be927a0955b9a82c6c85ef499ee3a626b8

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Simon Hudon
 
 ! This file was ported from Lean 3 source module control.random
-! leanprover-community/mathlib commit 70fd9563a21e7b963887c9360bd29b2393e6225a
+! leanprover-community/mathlib commit 9240e8be927a0955b9a82c6c85ef499ee3a626b8
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -16,6 +16,9 @@ import Mathbin.Tactic.NormNum
 /-!
 # Rand Monad and Random Class
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This module provides tools for formulating computations guided by randomness and for
 defining objects that can be created randomly.
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/f2ad3645af9effcdb587637dc28a6074edc813f9

@@ -65,7 +65,7 @@ def Rand :=
 #align rand Rand
 -/
 
-instance (g : Type) : Uliftable (RandG.{u} g) (RandG.{v} g) :=
+instance (g : Type) : ULiftable (RandG.{u} g) (RandG.{v} g) :=
   @StateT.uliftable' _ _ _ _ _ (Equiv.ulift.trans Equiv.ulift.symm)
 
 open ULift hiding Inhabited
@@ -130,7 +130,7 @@ def random : RandG g α :=
 
 /-- generate an infinite series of random values of type `α` -/
 def randomSeries : RandG g (Stream' α) := do
-  let gen ← Uliftable.up (split g)
+  let gen ← ULiftable.up (split g)
   pure <| Stream'.corecState (Random.random α g) gen
 #align rand.random_series Rand.randomSeries
 
@@ -146,7 +146,7 @@ def randomR [Preorder α] [BoundedRandom α] (x y : α) (h : x ≤ y) : RandG g
 /-- generate an infinite series of random values of type `α` between `x` and `y` inclusive. -/
 def randomSeriesR [Preorder α] [BoundedRandom α] (x y : α) (h : x ≤ y) :
     RandG g (Stream' (x .. y)) := do
-  let gen ← Uliftable.up (split g)
+  let gen ← ULiftable.up (split g)
   pure <| corec_state (BoundedRandom.randomR g x y h) gen
 #align rand.random_series_r Rand.randomSeriesR
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

@@ -75,7 +75,6 @@ def RandG.next {g : Type} [RandomGen g] : RandG g ℕ :=
   ⟨Prod.map id up ∘ RandomGen.next ∘ down⟩
 #align rand_g.next RandG.next
 
--- mathport name: «expr .. »
 local infixl:41 " .. " => Set.Icc
 
 open Stream'
@@ -88,7 +87,7 @@ class BoundedRandom (α : Type u) [Preorder α] where
 -/
 
 #print Random /-
-/- ./././Mathport/Syntax/Translate/Command.lean:394:30: infer kinds are unsupported in Lean 4: #[`Random] [] -/
+/- ./././Mathport/Syntax/Translate/Command.lean:393:30: infer kinds are unsupported in Lean 4: #[`Random] [] -/
 /-- `random α` gives us machinery to generate values of type `α` -/
 class Random (α : Type u) where
   Random : ∀ (g : Type) [RandomGen g], RandG g α

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

@@ -88,7 +88,7 @@ class BoundedRandom (α : Type u) [Preorder α] where
 -/
 
 #print Random /-
-/- ./././Mathport/Syntax/Translate/Command.lean:393:30: infer kinds are unsupported in Lean 4: #[`Random] [] -/
+/- ./././Mathport/Syntax/Translate/Command.lean:394:30: infer kinds are unsupported in Lean 4: #[`Random] [] -/
 /-- `random α` gives us machinery to generate values of type `α` -/
 class Random (α : Type u) where
   Random : ∀ (g : Type) [RandomGen g], RandG g α

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

@@ -321,8 +321,8 @@ theorem bool_ofNat_mem_Icc_of_mem_Icc_toNat (x y : Bool) (n : ℕ) :
     n ∈ (x.toNat .. y.toNat) → Bool.ofNat n ∈ (x .. y) :=
   by
   simp only [and_imp, Set.mem_Icc]; intro h₀ h₁
-  constructor <;> [have h₂ := Bool.ofNat_le_ofNat h₀;have h₂ := Bool.ofNat_le_ofNat h₁] <;>
-      rw [Bool.ofNat_toNat] at h₂ <;>
+  constructor <;> [have h₂ := Bool.ofNat_le_ofNat h₀; have h₂ := Bool.ofNat_le_ofNat h₁] <;>
+      rw [Bool.ofNat_toNat] at h₂  <;>
     exact h₂
 #align bool_of_nat_mem_Icc_of_mem_Icc_to_nat bool_ofNat_mem_Icc_of_mem_Icc_toNat
 
@@ -347,7 +347,7 @@ def Bitvec.randomR {n : ℕ} (x y : Bitvec n) (h : x ≤ y) : RandG g (x .. y) :
     simp only [and_imp, Set.mem_Icc]; intro z h₀ h₁
     replace h₀ := Bitvec.ofFin_le_ofFin_of_le h₀
     replace h₁ := Bitvec.ofFin_le_ofFin_of_le h₁
-    rw [Bitvec.ofFin_toFin] at h₀ h₁; constructor <;> assumption
+    rw [Bitvec.ofFin_toFin] at h₀ h₁ ; constructor <;> assumption
   Subtype.map Bitvec.ofFin h' <$> Rand.randomR x.toFin y.toFin (Bitvec.toFin_le_toFin_of_le h)
 #align bitvec.random_r Bitvec.randomR
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

@@ -157,7 +157,6 @@ namespace Io
 
 private def accum_char (w : ℕ) (c : Char) : ℕ :=
   c.toNat + 256 * w
-#align io.accum_char io.accum_char
 
 /-- create and seed a random number generator -/
 def mkGenerator : Io StdGen := do

mathlib commit https://github.com/leanprover-community/mathlib/commit/8d33f09cd7089ecf074b4791907588245aec5d1b

@@ -322,7 +322,7 @@ theorem bool_ofNat_mem_Icc_of_mem_Icc_toNat (x y : Bool) (n : ℕ) :
     n ∈ (x.toNat .. y.toNat) → Bool.ofNat n ∈ (x .. y) :=
   by
   simp only [and_imp, Set.mem_Icc]; intro h₀ h₁
-  constructor <;> [have h₂ := Bool.ofNat_le_ofNat h₀, have h₂ := Bool.ofNat_le_ofNat h₁] <;>
+  constructor <;> [have h₂ := Bool.ofNat_le_ofNat h₀;have h₂ := Bool.ofNat_le_ofNat h₁] <;>
       rw [Bool.ofNat_toNat] at h₂ <;>
     exact h₂
 #align bool_of_nat_mem_Icc_of_mem_Icc_to_nat bool_ofNat_mem_Icc_of_mem_Icc_toNat

mathlib commit https://github.com/leanprover-community/mathlib/commit/09079525fd01b3dda35e96adaa08d2f943e1648c

@@ -88,7 +88,7 @@ class BoundedRandom (α : Type u) [Preorder α] where
 -/
 
 #print Random /-
-/- ./././Mathport/Syntax/Translate/Command.lean:388:30: infer kinds are unsupported in Lean 4: #[`Random] [] -/
+/- ./././Mathport/Syntax/Translate/Command.lean:393:30: infer kinds are unsupported in Lean 4: #[`Random] [] -/
 /-- `random α` gives us machinery to generate values of type `α` -/
 class Random (α : Type u) where
   Random : ∀ (g : Type) [RandomGen g], RandG g α

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

https://leanprover.zulipchat.com/#narrow/stream/287929-mathlib4/topic/Bug.20in.20randFin/near/428340514

@@ -95,7 +95,7 @@ def randBound (α : Type u)
   (BoundedRandom.randomR lo hi h : RandGT g _ _)
 
 def randFin {n : Nat} [RandomGen g] : RandGT g m (Fin n.succ) :=
-  fun ⟨g⟩ ↦ pure <| randNat g 0 n.succ |>.map Fin.ofNat ULift.up
+  fun ⟨g⟩ ↦ pure <| randNat g 0 n |>.map Fin.ofNat ULift.up
 
 instance {n : Nat} : Random m (Fin n.succ) where
   random := randFin

Per the style guidelines, λ is disallowed in mathlib. This is close to exhaustive; I left some tactic code alone when it seemed to me that tactic could be upstreamed soon.

Notes

• In lines I was modifying anyway, I also converted => to ↦.
• Also contains some mild in-passing indentation fixes in Mathlib/Order/SupClosed.
• Some doc comments still contained Lean 3 syntax λ x, , which I also replaced.

@@ -95,7 +95,7 @@ def randBound (α : Type u)
   (BoundedRandom.randomR lo hi h : RandGT g _ _)
 
 def randFin {n : Nat} [RandomGen g] : RandGT g m (Fin n.succ) :=
-  λ ⟨g⟩ => pure <| randNat g 0 n.succ |>.map Fin.ofNat ULift.up
+  fun ⟨g⟩ ↦ pure <| randNat g 0 n.succ |>.map Fin.ofNat ULift.up
 
 instance {n : Nat} : Random m (Fin n.succ) where
   random := randFin

Data.Nat.Basic is currently made of two things:

• Basic lemmas that continue the theory in Std (and could belong there, really)
• Basic algebraic order instances

I need the first ones earlier in the algebraic order hierarchy, hence the split.

Part of #9411. Similar to #9443

@@ -3,15 +3,8 @@ Copyright (c) 2022 Henrik Böving. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Henrik Böving
 -/
-
-import Mathlib.Init.Order.Defs
-import Mathlib.Init.Data.Nat.Lemmas
-import Mathlib.Init.Data.Int.Order
 import Mathlib.Control.ULiftable
 import Mathlib.Data.Fin.Basic
-import Mathlib.Data.Nat.Basic
-import Mathlib.Order.ULift
-import Mathlib.Logic.Equiv.Functor
 
 #align_import control.random from "leanprover-community/mathlib"@"fdc286cc6967a012f41b87f76dcd2797b53152af"
 

See Zulip thread for the discussion.

@@ -126,13 +126,13 @@ instance : BoundedRandom m Nat where
 
 instance : BoundedRandom m Int where
   randomR lo hi h _ := do
-    let ⟨z, _, h2⟩ ← randBound Nat 0 (Int.natAbs $ hi - lo) (Nat.zero_le _)
+    let ⟨z, _, h2⟩ ← randBound Nat 0 (Int.natAbs <| hi - lo) (Nat.zero_le _)
     pure ⟨
       z + lo,
       Int.le_add_of_nonneg_left (Int.ofNat_zero_le z),
-      Int.add_le_of_le_sub_right $ Int.le_trans
+      Int.add_le_of_le_sub_right <| Int.le_trans
         (Int.ofNat_le.mpr h2)
-        (le_of_eq $ Int.natAbs_of_nonneg $ Int.sub_nonneg_of_le h)⟩
+        (le_of_eq <| Int.natAbs_of_nonneg <| Int.sub_nonneg_of_le h)⟩
 
 instance {n : Nat} : BoundedRandom m (Fin n) where
   randomR lo hi h _ := do
@@ -168,6 +168,6 @@ def runRand (cmd : RandT m α) : m α := do
   pure res
 
 def runRandWith (seed : Nat) (cmd : RandT m α) : m α := do
-  pure $ (← cmd.run (ULift.up $ mkStdGen seed)).1
+  pure <| (← cmd.run (ULift.up <| mkStdGen seed)).1
 
 end IO

This covers these changes in Std: https://github.com/leanprover/std4/compare/6b4cf96c89e53cfcd73350bbcd90333a051ff4f0...[9dd24a34](https://github.com/leanprover-community/mathlib/commit/9dd24a3493cceefa2bede383f21e4ef548990b68)

• Int.ofNat_natAbs_eq_of_nonneg has become Int.natAbs_of_nonneg (and one argument has become implicit)
• List.map_id'' and List.map_id' have exchanged names. (Yay naming things using primes!)
• Some meta functions have moved to Std and can be deleted here.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -132,7 +132,7 @@ instance : BoundedRandom m Int where
       Int.le_add_of_nonneg_left (Int.ofNat_zero_le z),
       Int.add_le_of_le_sub_right $ Int.le_trans
         (Int.ofNat_le.mpr h2)
-        (le_of_eq $ Int.ofNat_natAbs_eq_of_nonneg _ $ Int.sub_nonneg_of_le h)⟩
+        (le_of_eq $ Int.natAbs_of_nonneg $ Int.sub_nonneg_of_le h)⟩
 
 instance {n : Nat} : BoundedRandom m (Fin n) where
   randomR lo hi h _ := do

This follows the pattern that is already present in the haskell version

@@ -11,6 +11,7 @@ import Mathlib.Control.ULiftable
 import Mathlib.Data.Fin.Basic
 import Mathlib.Data.Nat.Basic
 import Mathlib.Order.ULift
+import Mathlib.Logic.Equiv.Functor
 
 #align_import control.random from "leanprover-community/mathlib"@"fdc286cc6967a012f41b87f76dcd2797b53152af"
 
@@ -22,12 +23,13 @@ defining objects that can be created randomly.
 
 ## Main definitions
 
-* `Rand` and `RandG` monad for computations guided by randomness;
+* `RandT` and `RandGT` monad transformers for computations guided by randomness;
+* `Rand` and `RandG` monads as special cases of the above
 * `Random` class for objects that can be generated randomly;
   * `random` to generate one object;
 * `BoundedRandom` class for objects that can be generated randomly inside a range;
   * `randomR` to generate one object inside a range;
-* `IO.runRand` to run a randomized computation inside the `IO` monad;
+* `IO.runRand` to run a randomized computation inside any monad that has access to `stdGenRef`.
 
 ## References
 
@@ -37,37 +39,49 @@ defining objects that can be created randomly.
 
 set_option autoImplicit true
 
-/-- A monad to generate random objects using the generic generator type `g` -/
-abbrev RandG (g : Type) := StateM (ULift g)
+/-- A monad transformer to generate random objects using the generic generator type `g` -/
+abbrev RandGT (g : Type) := StateT (ULift g)
+/-- A monad to generate random objects using the generator type `g`.  -/
+abbrev RandG (g : Type) := RandGT g Id
 
-/-- A monad to generate random objects using the generator type `Rng` -/
-abbrev Rand (α : Type u) := RandG StdGen α
+/-- A monad transformer to generate random objects using the generator type `StdGen`.
+`RandT m α` should be thought of a random value in `m α`. -/
+abbrev RandT := RandGT StdGen
 
-/-- `Random α` gives us machinery to generate values of type `α` -/
-class Random (α : Type u) where
-  random [RandomGen g] : RandG g α
+/-- A monad to generate random objects using the generator type `StdGen`.  -/
+abbrev Rand := RandG StdGen
 
-/-- `BoundedRandom α` gives us machinery to generate values of type `α` between certain bounds -/
-class BoundedRandom (α : Type u) [Preorder α] where
-  randomR {g : Type} (lo hi : α) (h : lo ≤ hi) [RandomGen g] : RandG g {a // lo ≤ a ∧ a ≤ hi}
+instance [MonadLift m n] : MonadLiftT (RandGT g m) (RandGT g n) where
+  monadLift x := fun s => x s
+
+/-- `Random m α` gives us machinery to generate values of type `α` in the monad `m`.
+
+Note that `m` is a parameter as some types may only be sampleable with access to a certain monad. -/
+class Random (m) (α : Type u) where
+  random [RandomGen g] : RandGT g m α
+
+/-- `BoundedRandom m α` gives us machinery to generate values of type `α` between certain bounds in
+the monad `m`. -/
+class BoundedRandom (m) (α : Type u) [Preorder α] where
+  randomR {g : Type} (lo hi : α) (h : lo ≤ hi) [RandomGen g] : RandGT g m {a // lo ≤ a ∧ a ≤ hi}
 
 namespace Rand
   /-- Generate one more `Nat` -/
-  def next [RandomGen g] : RandG g Nat := do
+  def next [RandomGen g] [Monad m] : RandGT g m Nat := do
     let rng := (← get).down
     let (res, new) := RandomGen.next rng
     set (ULift.up new)
     pure res
 
   /-- Create a new random number generator distinct from the one stored in the state -/
-  def split {g : Type} [RandomGen g] : RandG g g := do
+  def split {g : Type} [RandomGen g] [Monad m] : RandGT g m g := do
     let rng := (← get).down
     let (r1, r2) := RandomGen.split rng
     set (ULift.up r1)
     pure r2
 
   /-- Get the range of Nat that can be generated by the generator `g` -/
-  def range {g : Type} [RandomGen g] : RandG g (Nat × Nat) := do
+  def range {g : Type} [RandomGen g] [Monad m] : RandGT g m (Nat × Nat) := do
     let rng := (← get).down
     pure <| RandomGen.range rng
 end Rand
@@ -76,39 +90,42 @@ namespace Random
 
 open Rand
 
+variable [Monad m]
+
 /-- Generate a random value of type `α`. -/
-def rand (α : Type u) [Random α] [RandomGen g] : RandG g α := Random.random
+def rand (α : Type u) [Random m α] [RandomGen g] : RandGT g m α := Random.random
 
 /-- Generate a random value of type `α` between `x` and `y` inclusive. -/
-def randBound (α : Type u) [Preorder α] [BoundedRandom α] (lo hi : α) (h : lo ≤ hi) [RandomGen g] :
-    RandG g {a // lo ≤ a ∧ a ≤ hi} :=
-  BoundedRandom.randomR lo hi h
+def randBound (α : Type u)
+    [Preorder α] [BoundedRandom m α] (lo hi : α) (h : lo ≤ hi) [RandomGen g] :
+    RandGT g m {a // lo ≤ a ∧ a ≤ hi} :=
+  (BoundedRandom.randomR lo hi h : RandGT g _ _)
 
-def randFin {n : Nat} [RandomGen g] : RandG g (Fin n.succ) :=
-  λ ⟨g⟩ => randNat g 0 n.succ |>.map Fin.ofNat ULift.up
+def randFin {n : Nat} [RandomGen g] : RandGT g m (Fin n.succ) :=
+  λ ⟨g⟩ => pure <| randNat g 0 n.succ |>.map Fin.ofNat ULift.up
 
-instance {n : Nat} : Random (Fin n.succ) where
+instance {n : Nat} : Random m (Fin n.succ) where
   random := randFin
 
-def randBool [RandomGen g] : RandG g Bool :=
+def randBool [RandomGen g] : RandGT g m Bool :=
   return (← rand (Fin 2)) == 1
 
-instance : Random Bool where
+instance : Random m Bool where
   random := randBool
 
-instance {α : Type u} [Random α] : Random (ULift.{v} α) where
+instance {α : Type u} [ULiftable m m'] [Random m α] : Random m' (ULift.{v} α) where
   random := ULiftable.up random
 
-instance : BoundedRandom Nat where
-  randomR := λ lo hi h _ => do
+instance : BoundedRandom m Nat where
+  randomR lo hi h _ := do
     let z ← rand (Fin (hi - lo).succ)
     pure ⟨
       lo + z.val, Nat.le_add_right _ _,
       Nat.add_le_of_le_sub' h (Nat.le_of_succ_le_succ z.isLt)
     ⟩
 
-instance : BoundedRandom Int where
-  randomR := λ lo hi h _ => do
+instance : BoundedRandom m Int where
+  randomR lo hi h _ := do
     let ⟨z, _, h2⟩ ← randBound Nat 0 (Int.natAbs $ hi - lo) (Nat.zero_le _)
     pure ⟨
       z + lo,
@@ -117,31 +134,40 @@ instance : BoundedRandom Int where
         (Int.ofNat_le.mpr h2)
         (le_of_eq $ Int.ofNat_natAbs_eq_of_nonneg _ $ Int.sub_nonneg_of_le h)⟩
 
-instance {n : Nat} : BoundedRandom (Fin n) where
-  randomR := λ lo hi h _ => do
+instance {n : Nat} : BoundedRandom m (Fin n) where
+  randomR lo hi h _ := do
     let ⟨r, h1, h2⟩ ← randBound Nat lo.val hi.val h
     pure ⟨⟨r, Nat.lt_of_le_of_lt h2 hi.isLt⟩, h1, h2⟩
 
-instance {α : Type u} [Preorder α] [BoundedRandom α] : BoundedRandom (ULift.{v} α) where
+instance {α : Type u} [Preorder α] [ULiftable m m'] [BoundedRandom m α] [Monad m'] :
+    BoundedRandom m' (ULift.{v} α) where
   randomR lo hi h := do
     let ⟨x⟩ ← ULiftable.up.{v} (BoundedRandom.randomR lo.down hi.down h)
     pure ⟨ULift.up x.val, x.prop⟩
 
 end Random
 
-/-- Computes a `Rand α` using the global `stdGenRef` as RNG.
-    Note that:
-    - `stdGenRef` is not necessarily properly seeded on program startup
-      as of now and will therefore be deterministic.
-    - `stdGenRef` is not thread local, hence two threads accessing it
-      at the same time will get the exact same generator.
+namespace IO
+
+variable {m : Type* → Type*} {m₀ : Type → Type}
+variable [Monad m] [MonadLiftT (ST RealWorld) m₀] [ULiftable m₀ m]
+
+/--
+Computes a `RandT m α` using the global `stdGenRef` as RNG.
+
+Note that:
+- `stdGenRef` is not necessarily properly seeded on program startup
+  as of now and will therefore be deterministic.
+- `stdGenRef` is not thread local, hence two threads accessing it
+  at the same time will get the exact same generator.
 -/
-def IO.runRand (cmd : Rand α) : BaseIO α := do
-  let stdGen ← stdGenRef.get
-  let rng := ULift.up stdGen
-  let (res, new) := Id.run <| StateT.run cmd rng
-  stdGenRef.set new.down
+def runRand (cmd : RandT m α) : m α := do
+  let stdGen ← ULiftable.up (stdGenRef.get : m₀ _)
+  let (res, new) ← StateT.run cmd stdGen
+  let _ ← ULiftable.up (stdGenRef.set new.down : m₀ _)
   pure res
 
-def IO.runRandWith (seed : Nat) (cmd : Rand α) : BaseIO α := do
-  pure $ (cmd.run (ULift.up $ mkStdGen seed)).1
+def runRandWith (seed : Nat) (cmd : RandT m α) : m α := do
+  pure $ (← cmd.run (ULift.up $ mkStdGen seed)).1
+
+end IO

The most useful universe argument to up and down (the one in the ULift type) is now first.

Combined with the outParam, this makes using ULiftable.up more ergonomic downstream, removing a handful of type annotations.

@@ -97,7 +97,7 @@ instance : Random Bool where
   random := randBool
 
 instance {α : Type u} [Random α] : Random (ULift.{v} α) where
-  random {g} := ULiftable.up (random : RandG g α)
+  random := ULiftable.up random
 
 instance : BoundedRandom Nat where
   randomR := λ lo hi h _ => do
@@ -123,10 +123,9 @@ instance {n : Nat} : BoundedRandom (Fin n) where
     pure ⟨⟨r, Nat.lt_of_le_of_lt h2 hi.isLt⟩, h1, h2⟩
 
 instance {α : Type u} [Preorder α] [BoundedRandom α] : BoundedRandom (ULift.{v} α) where
-  randomR {g} lo hi h := do
-    let ⟨v⟩
-      ← (ULiftable.up (BoundedRandom.randomR lo.down hi.down h : RandG g _) : RandG g (ULift.{v} _))
-    pure ⟨ULift.up v.val, v.prop⟩
+  randomR lo hi h := do
+    let ⟨x⟩ ← ULiftable.up.{v} (BoundedRandom.randomR lo.down hi.down h)
+    pure ⟨ULift.up x.val, x.prop⟩
 
 end Random
 

Co-authored-by: Moritz Firsching <firsching@google.com>

@@ -54,21 +54,21 @@ class BoundedRandom (α : Type u) [Preorder α] where
 namespace Rand
   /-- Generate one more `Nat` -/
   def next [RandomGen g] : RandG g Nat := do
-    let rng := (←get).down
+    let rng := (← get).down
     let (res, new) := RandomGen.next rng
     set (ULift.up new)
     pure res
 
   /-- Create a new random number generator distinct from the one stored in the state -/
   def split {g : Type} [RandomGen g] : RandG g g := do
-    let rng := (←get).down
+    let rng := (← get).down
     let (r1, r2) := RandomGen.split rng
     set (ULift.up r1)
     pure r2
 
   /-- Get the range of Nat that can be generated by the generator `g` -/
   def range {g : Type} [RandomGen g] : RandG g (Nat × Nat) := do
-    let rng := (←get).down
+    let rng := (← get).down
     pure <| RandomGen.range rng
 end Rand
 

@@ -104,7 +104,7 @@ instance : BoundedRandom Nat where
     let z ← rand (Fin (hi - lo).succ)
     pure ⟨
       lo + z.val, Nat.le_add_right _ _,
-      Nat.add_le_of_le_sub_left h (Nat.le_of_succ_le_succ z.isLt)
+      Nat.add_le_of_le_sub' h (Nat.le_of_succ_le_succ z.isLt)
     ⟩
 
 instance : BoundedRandom Int where

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Henrik Böving
 -/
 
-import Mathlib.Init.Algebra.Order
+import Mathlib.Init.Order.Defs
 import Mathlib.Init.Data.Nat.Lemmas
 import Mathlib.Init.Data.Int.Order
 import Mathlib.Control.ULiftable

Autoimplicits are highly controversial and also defeat the performance-improving work in #6474.

The intent of this PR is to make autoImplicit opt-in on a per-file basis, by disabling it in the lakefile and enabling it again with set_option autoImplicit true in the few files that rely on it.

That also keeps this PR small, as opposed to attempting to "fix" files to not need it any more.

I claim that many of the uses of autoImplicit in these files are accidental; situations such as:

• Assuming variables are in scope, but pasting the lemma in the wrong section
• Pasting in a lemma from a scratch file without checking to see if the variable names are consistent with the rest of the file
• Making a copy-paste error between lemmas and forgetting to add an explicit arguments.

Having set_option autoImplicit false as the default prevents these types of mistake being made in the 90% of files where autoImplicits are not used at all, and causes them to be caught by CI during review.

I think there were various points during the port where we encouraged porters to delete the universes u v lines; I think having autoparams for universe variables only would cover a lot of the cases we actually use them, while avoiding any real shortcomings.

A Zulip poll (after combining overlapping votes accordingly) was in favor of this change with 5:5:18 as the no:dontcare:yes vote ratio.

While this PR was being reviewed, a handful of files gained some more likely-accidental autoImplicits. In these places, set_option autoImplicit true has been placed locally within a section, rather than at the top of the file.

@@ -35,6 +35,8 @@ defining objects that can be created randomly.
 
 -/
 
+set_option autoImplicit true
+
 /-- A monad to generate random objects using the generic generator type `g` -/
 abbrev RandG (g : Type) := StateM (ULift g)
 

@@ -7,8 +7,10 @@ Authors: Henrik Böving
 import Mathlib.Init.Algebra.Order
 import Mathlib.Init.Data.Nat.Lemmas
 import Mathlib.Init.Data.Int.Order
+import Mathlib.Control.ULiftable
 import Mathlib.Data.Fin.Basic
 import Mathlib.Data.Nat.Basic
+import Mathlib.Order.ULift
 
 #align_import control.random from "leanprover-community/mathlib"@"fdc286cc6967a012f41b87f76dcd2797b53152af"
 
@@ -92,6 +94,9 @@ def randBool [RandomGen g] : RandG g Bool :=
 instance : Random Bool where
   random := randBool
 
+instance {α : Type u} [Random α] : Random (ULift.{v} α) where
+  random {g} := ULiftable.up (random : RandG g α)
+
 instance : BoundedRandom Nat where
   randomR := λ lo hi h _ => do
     let z ← rand (Fin (hi - lo).succ)
@@ -115,6 +120,12 @@ instance {n : Nat} : BoundedRandom (Fin n) where
     let ⟨r, h1, h2⟩ ← randBound Nat lo.val hi.val h
     pure ⟨⟨r, Nat.lt_of_le_of_lt h2 hi.isLt⟩, h1, h2⟩
 
+instance {α : Type u} [Preorder α] [BoundedRandom α] : BoundedRandom (ULift.{v} α) where
+  randomR {g} lo hi h := do
+    let ⟨v⟩
+      ← (ULiftable.up (BoundedRandom.randomR lo.down hi.down h : RandG g _) : RandG g (ULift.{v} _))
+    pure ⟨ULift.up v.val, v.prop⟩
+
 end Random
 
 /-- Computes a `Rand α` using the global `stdGenRef` as RNG.

• depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -2,11 +2,6 @@
 Copyright (c) 2022 Henrik Böving. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Henrik Böving
-
-! This file was ported from Lean 3 source module control.random
-! leanprover-community/mathlib commit fdc286cc6967a012f41b87f76dcd2797b53152af
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 
 import Mathlib.Init.Algebra.Order
@@ -15,6 +10,8 @@ import Mathlib.Init.Data.Int.Order
 import Mathlib.Data.Fin.Basic
 import Mathlib.Data.Nat.Basic
 
+#align_import control.random from "leanprover-community/mathlib"@"fdc286cc6967a012f41b87f76dcd2797b53152af"
+
 /-!
 # Rand Monad and Random Class
 

Grepping for [^ .:{-] [^ :] and reviewing the results. Once I started I couldn't stop. :-)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -79,7 +79,7 @@ open Rand
 def rand (α : Type u) [Random α] [RandomGen g] : RandG g α := Random.random
 
 /-- Generate a random value of type `α` between `x` and `y` inclusive. -/
-def randBound (α : Type u) [Preorder α]  [BoundedRandom α] (lo hi : α) (h : lo ≤ hi) [RandomGen g] :
+def randBound (α : Type u) [Preorder α] [BoundedRandom α] (lo hi : α) (h : lo ≤ hi) [RandomGen g] :
     RandG g {a // lo ≤ a ∧ a ≤ hi} :=
   BoundedRandom.randomR lo hi h
 

Just so these get marked off the dashboard. These files have already been ported by hand.

Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -2,7 +2,13 @@
 Copyright (c) 2022 Henrik Böving. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Henrik Böving
+
+! This file was ported from Lean 3 source module control.random
+! leanprover-community/mathlib commit fdc286cc6967a012f41b87f76dcd2797b53152af
+! Please do not edit these lines, except to modify the commit id
+! if you have ported upstream changes.
 -/
+
 import Mathlib.Init.Algebra.Order
 import Mathlib.Init.Data.Nat.Lemmas
 import Mathlib.Init.Data.Int.Order
@@ -11,17 +17,23 @@ import Mathlib.Data.Nat.Basic
 
 /-!
 # Rand Monad and Random Class
+
 This module provides tools for formulating computations guided by randomness and for
 defining objects that can be created randomly.
+
 ## Main definitions
-  * `Rand` and `RandG` monad for computations guided by randomness;
-  * `Random` class for objects that can be generated randomly;
-    * `random` to generate one object;
-  * `BoundedRandom` class for objects that can be generated randomly inside a range;
-    * `randomR` to generate one object inside a range;
-  * `IO.runRand` to run a randomized computation inside the `IO` monad;
+
+* `Rand` and `RandG` monad for computations guided by randomness;
+* `Random` class for objects that can be generated randomly;
+  * `random` to generate one object;
+* `BoundedRandom` class for objects that can be generated randomly inside a range;
+  * `randomR` to generate one object inside a range;
+* `IO.runRand` to run a randomized computation inside the `IO` monad;
+
 ## References
-  * Similar library in Haskell: https://hackage.haskell.org/package/MonadRandom
+
+* Similar library in Haskell: https://hackage.haskell.org/package/MonadRandom
+
 -/
 
 /-- A monad to generate random objects using the generic generator type `g` -/