hoose :: forall dom a
    .  (AlphaEq dom dom dom [(VarId,VarId)], Project Let dom)
    => (forall c. ASTF dom c -> Bool)
    -> PrjDict dom
    -> MkInjDict dom
    -> MkSubEnv dom
    -> ASTF dom a
    -> Maybe (Chosen dom a)
choose hoistOver pd mkId mkSub a = chooseEnvSub initEnv a
  where
    initEnv = Env
        { inLambda     = False
        , counter      = \(ASTE b) -> count b a
        , dependencies = empty
        }

    chooseEnv :: Env dom -> ASTF dom b -> Maybe (Chosen dom a)
    chooseEnv env b = this `mplus` that  -- Prefer `this` because it must be larger than `that`
      where
        this = do
            guard $ liftable pd env b
            id <- mkId b a
            return $ Chosen id b
        that = do
            guard $ hoistOver b
            chooseEnvSub env b

    -- | Like 'chooseEnv', but does not consider the top expression for sharing
    chooseEnvSub :: Env dom -> ASTF dom b -> Maybe (Chosen dom a)
    chooseEnvSub env a
        = Prelude.foldr (\(ASTE b, e) a -> chooseEnv e b `mplus` a) Nothing
        (simpleMatch (subTermsEnv pd mkSub env) a :: [(ASTE dom, Env dom)])



-- | Perform common sub-expression elimination and variable hoisting

choose :: forall dom a
    .  (AlphaEq dom dom dom [(VarId,VarId)], Project Let dom)
    => (forall c. ASTF dom c -> Bool)
    -> PrjDict dom
    -> MkInjDict dom
    -> MkSubEnv dom
    -> ASTF dom a
    -> Maybe (Chosen dom a)
choose hoistOver pd mkId mkSub a = chooseEnvSub initEnv a
  where
    initEnv = Env
        { inLambda     = False
        , counter      = \(ASTE b) -> count b a
        , dependencies = empty
        }

    chooseEnv :: Env dom -> ASTF dom b -> Maybe (Chosen dom a)
    chooseEnv env b = this `mplus` that  -- Prefer `this` because it must be larger than `that`
      where
        this = do
            guard $ liftable pd env b
            id <- mkId b a
            return $ Chosen id b
        that = do
            guard $ hoistOver b
            chooseEnvSub env b

    -- | Like 'chooseEnv', but does not consider the top expression for sharing
    chooseEnvSub :: Env dom -> ASTF dom b -> Maybe (Chosen dom a)
    chooseEnvSub env a
        = Prelude.foldr (\(ASTE b, e) a -> chooseEnv e b `mplus` a) Nothing
        (simpleMatch (subTermsEnv pd mkSub env) a :: [(ASTE dom, Env dom)])



-- | Perform common sub-expression elimination and variable hoisting
choose hoistOver pd mkId mkSub a = chooseEnvSub initEnv a
  where
    initEnv = Env
        { inLambda     = False
        , counter      = \(ASTE b) -> count b a
        , dependencies = empty
        }

    chooseEnv :: Env dom -> ASTF dom b -> Maybe (Chosen dom a)
    chooseEnv env b = this `mplus` that  -- Prefer `this` because it must be larger than `that`
      where
        this = do
            guard $ liftable pd env b
            id <- mkId b a
            return $ Chosen id b
        that = do
            guard $ hoistOver b
            chooseEnvSub env b

    -- | Like 'chooseEnv', but does not consider the top expression for sharing
    chooseEnvSub :: Env dom -> ASTF dom b -> Maybe (Chosen dom a)
    chooseEnvSub env a
        = Prelude.foldr (\(ASTE b, e) a -> chooseEnv e b `mplus` a) Nothing
        (simpleMatch (subTermsEnv pd mkSub env) a :: [(ASTE dom, Env dom)])



-- | Perform common sub-expression elimination and variable hoisting