blob: eb1d3881fbf4f2b91c5bc638115db5df914ada2f [file]
/-
Copyright (c) 2021 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura
-/
/-
NondetT monad transformer.
It is uses `unsafe` features to workaround the positivity constraints
in the definition of `Alts`.
-/
namespace Std
namespace NondetT
universe u
private def AltsCore := PNonScalar.{u}
inductive Alts (m : Type u → Type u) (α : Type u)
| nil : Alts m α
| cons (head : α) (tail : m AltsCore) : Alts m α
| delayed (t : Thunk (m AltsCore)) : Alts m α
namespace Alts
variable {m : Type u → Type u} {α : Type u}
@[inline]
unsafe def ofAltsCore (x : m AltsCore.{u}) : m (Alts m α) :=
unsafeCast x
@[inline]
unsafe def toAltsCore (x : m (Alts m α)) : m AltsCore.{u} :=
unsafeCast x
mutual
unsafe def run' [Monad m] : Alts m α → m (Option (α × m (Alts m α)))
| nil => pure none
| cons x xs => pure $ some (x, ofAltsCore xs)
| delayed xs => runUnsafe (ofAltsCore xs.get)
unsafe def runUnsafe [Monad m] (x : m (Alts m α)) : m (Option (α × m (Alts m α))) := do
run' (← x)
end
unsafe def ofList [Monad m] : List α → m (Alts m α)
| [] => pure Alts.nil
| a::as => pure $ Alts.cons a (toAltsCore (ofList as))
mutual
unsafe def append' [Monad m] : Alts m α → m (Alts m α) → m (Alts m α)
| nil, bs => bs
| cons a as, bs => pure $ delayed $ Thunk.mk fun _ => toAltsCore $ pure $ cons a $ toAltsCore $ append (ofAltsCore as) bs
| delayed as, bs => pure $ delayed $ Thunk.mk fun _ => toAltsCore $ append (ofAltsCore as.get) bs
unsafe def append [Monad m] (xs ys : m (Alts m α)) : m (Alts m α) := do
append' (← xs) ys
end
mutual
unsafe def join' [Monad m] : Alts m (m (Alts m α)) → m (Alts m α)
| nil => pure nil
| cons x xs => pure $ delayed $ Thunk.mk fun _ => toAltsCore $ append x $ join $ ofAltsCore xs
| delayed xs => pure $ delayed $ Thunk.mk fun _ => toAltsCore (α := α) $ join (ofAltsCore xs.get)
unsafe def join [Monad m] (xs : m (Alts m (m (Alts m α)))) : m (Alts m α) := do
join' (← xs)
end
mutual
unsafe def map' [Monad m] (f : α → β) : Alts m α → m (Alts m β)
| nil => pure nil
| cons x xs => pure $ delayed $ Thunk.mk fun _ => toAltsCore $ pure $ cons (f x) $ toAltsCore $ map f (ofAltsCore xs)
| delayed xs => pure $ delayed $ Thunk.mk fun _ => toAltsCore $ map f (ofAltsCore xs.get)
unsafe def map [Monad m] (f : α → β) (xs : m (Alts m α)) : m (Alts m β) := do
map' f (← xs)
end
@[inline]
protected unsafe def pure [Monad m] (a : α) : m (Alts m α) := do
pure $ Alts.cons a $ toAltsCore (α := α) Alts.nil
end Alts
end NondetT
open NondetT (Alts)
def NondetT (m : Type u → Type u) (α : Type u) := m (Alts m α)
namespace NondetT
instance [Pure m] : Inhabited (NondetT m α) where
default := (pure Alts.nil : m (Alts m α))
@[inline]
unsafe def appendUnsafe [Monad m] (x y : NondetT m α) : NondetT m α :=
Alts.append x y
@[implementedBy appendUnsafe]
protected constant append [Monad m] (x y : NondetT m α) : NondetT m α
@[inline]
unsafe def joinUnsafe [Monad m] (x : NondetT m (NondetT m α)) : NondetT m α :=
Alts.join x
@[implementedBy joinUnsafe]
protected constant join [Monad m] (x : NondetT m (NondetT m α)) : NondetT m α
@[inline]
unsafe def mapUnsafe [Monad m] (f : α → β) (x : NondetT m α) : NondetT m β :=
Alts.map f x
@[implementedBy mapUnsafe]
protected constant map [Monad m] (f : α → β) (x : NondetT m α) : NondetT m β
@[inline]
unsafe def pureUnsafe [Monad m] (a : α) : NondetT m α :=
Alts.pure a
@[implementedBy pureUnsafe]
protected constant pure [Monad m] (a : α) : NondetT m α
@[inline]
protected def failure [Monad m] : NondetT m α := id (α := m (Alts m α)) $
pure Alts.nil
instance [Monad m] : Monad (NondetT m) where
bind x f := NondetT.join (NondetT.map f x)
pure := NondetT.pure
map := NondetT.map
instance [Monad m] : Alternative (NondetT m) where
failure := NondetT.failure
orElse := NondetT.append
@[inline]
unsafe def runUnsafe [Monad m] (x : NondetT m α) : m (Option (α × NondetT m α)) :=
Alts.runUnsafe x
@[implementedBy runUnsafe]
protected constant run [Monad m] (x : NondetT m α) : m (Option (α × NondetT m α))
protected def run' [Monad m] (x : NondetT m α) : m (Option α) := do
match (← x.run) with
| some (a, _) => pure (some a)
| none => pure none
@[inline]
unsafe def chooseUnsafe [Monad m] (as : List α) : NondetT m α :=
Alts.ofList as
@[implementedBy chooseUnsafe]
constant chooseImp [Monad m] (as : List α) : NondetT m α
class Choose (m : Type u → Type u) :=
(choose : List α → m α)
export Choose (choose)
instance [MonadLift m n] [Choose m] : Choose n where
choose := fun as => liftM (m := m) $ choose as
instance [Monad m] : Choose (NondetT m) where
choose := chooseImp
@[inline]
unsafe def liftUnsafe [Monad m] (x : m α) : NondetT m α := id (α := m (Alts m α)) do
let a ← x
Alts.pure a
@[implementedBy liftUnsafe]
protected constant lift [Monad m] (x : m α) : NondetT m α
instance [Monad m] : MonadLift m (NondetT m) where
monadLift := NondetT.lift
end NondetT
end Std