blob: 1916e78a59cd91cc756c4e0a3220bef9b916245f [file]
/-
Copyright (c) 2024 Lean FRO, LLC. or its affiliates. All Rights Reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Kim Morrison
-/
module
prelude
public import Lean.Meta.DiscrTree.Basic
public section
namespace Lean.Meta.DiscrTree
namespace Trie
/--
Monadically fold the keys and values stored in a `Trie`.
-/
partial def foldM [Monad m] (initialKeys : Array Key)
(f : σ → Array Key → α → m σ) : (init : σ) → Trie α → m σ
| init, Trie.node vs children => do
let s ← vs.foldlM (init := init) fun s v => f s initialKeys v
children.foldlM (init := s) fun s (k, t) =>
t.foldM (initialKeys.push k) f s
/--
Fold the keys and values stored in a `Trie`.
-/
@[inline]
def fold (initialKeys : Array Key) (f : σ → Array Key → α → σ) (init : σ) (t : Trie α) : σ :=
Id.run <| t.foldM initialKeys (init := init) fun s k a => return f s k a
/--
Monadically fold the values stored in a `Trie`.
-/
partial def foldValuesM [Monad m] (f : σ → α → m σ) : (init : σ) → Trie α → m σ
| init, node vs children => do
let s ← vs.foldlM (init := init) f
children.foldlM (init := s) fun s (_, c) => c.foldValuesM (init := s) f
/--
Fold the values stored in a `Trie`.
-/
@[inline]
def foldValues (f : σ → α → σ) (init : σ) (t : Trie α) : σ :=
Id.run <| t.foldValuesM (init := init) (pure <| f · ·)
/--
The number of values stored in a `Trie`.
-/
partial def size : Trie α → Nat
| Trie.node vs children =>
children.foldl (init := vs.size) fun n (_, c) => n + size c
end Trie
/--
Monadically fold over the keys and values stored in a `DiscrTree`.
-/
@[inline]
def foldM [Monad m] (f : σ → Array Key → α → m σ) (init : σ)
(t : DiscrTree α) : m σ :=
t.root.foldlM (init := init) fun s k t => t.foldM #[k] (init := s) f
/--
Fold over the keys and values stored in a `DiscrTree`
-/
@[inline]
def fold (f : σ → Array Key → α → σ) (init : σ) (t : DiscrTree α) : σ :=
Id.run <| t.foldM (init := init) fun s keys a => return f s keys a
/--
Monadically fold over the values stored in a `DiscrTree`.
-/
@[inline]
def foldValuesM [Monad m] (f : σ → α → m σ) (init : σ) (t : DiscrTree α) :
m σ :=
t.root.foldlM (init := init) fun s _ t => t.foldValuesM (init := s) f
/--
Fold over the values stored in a `DiscrTree`.
-/
@[inline]
def foldValues (f : σ → α → σ) (init : σ) (t : DiscrTree α) : σ :=
Id.run <| t.foldValuesM (init := init) (pure <| f · ·)
/--
Check for the presence of a value satisfying a predicate.
-/
@[inline]
def containsValueP (t : DiscrTree α) (f : α → Bool) : Bool :=
t.foldValues (init := false) fun r a => r || f a
/--
Extract the values stored in a `DiscrTree`.
-/
@[inline]
def values (t : DiscrTree α) : Array α :=
t.foldValues (init := #[]) fun as a => as.push a
/--
Extract the keys and values stored in a `DiscrTree`.
-/
@[inline]
def toArray (t : DiscrTree α) : Array (Array Key × α) :=
t.fold (init := #[]) fun as keys a => as.push (keys, a)
/--
Get the number of values stored in a `DiscrTree`. O(n) in the size of the tree.
-/
@[inline]
def size (t : DiscrTree α) : Nat :=
t.root.foldl (init := 0) fun n _ t => n + t.size
variable {m : Type → Type} [Monad m]
/-- Apply a monadic function to the array of values at each node in a `DiscrTree`. -/
partial def Trie.mapArraysM (t : DiscrTree.Trie α) (f : Array α → m (Array β)) :
m (DiscrTree.Trie β) :=
match t with
| .node vs children =>
return .node (← f vs) (← children.mapM fun (k, t') => do pure (k, ← t'.mapArraysM f))
/-- Apply a monadic function to the array of values at each node in a `DiscrTree`. -/
def mapArraysM (d : DiscrTree α) (f : Array α → m (Array β)) : m (DiscrTree β) := do
pure { root := ← d.root.mapM (fun t => t.mapArraysM f) }
/-- Apply a function to the array of values at each node in a `DiscrTree`. -/
def mapArrays (d : DiscrTree α) (f : Array α → Array β) : DiscrTree β :=
Id.run <| d.mapArraysM fun A => pure (f A)
end Lean.Meta.DiscrTree