[Agda] Questions about unification

[András Kovács]

I don't understand, "pruning" means looking at metavariables and their
substitutions on the right hand side of an equation, and removing
dependencies on out-of-scope variables; see the example Ulf wrote before.
Variables inside the substitution on the left hand side of an equation
aren't targets of pruning in any way.

2016-11-28 8:49 GMT+01:00 Roman <effectfully at gmail.com>:

> I wonder, why prune when you can just solve? Consider the flexRigid case
>
>     U [vs] =?= t
>
> where `vs` is a list of variables (not necessarily different). We
> traverse `t` and check whether
>
>   1) each variable in `t` occurs at least ones in `vs`. If not so,
> then throw a "can't unify" error.
>   2) each variable in `t` occurs exactly ones in `vs`.
>     2.1) If so, we have a solution. I.e. this equation:
>
>         U [x, y, w, w] =?= App (Var x) (Var y)
>
>       gets solved by
>
>         U [x, y, _, _] := App (Var x) (Var y)
>
>       without any explicit pruning.
>     2.2) If not so, then we can prune sometimes. E.g.
>
>         U [x, y, w, w] =?= App (Var x) (Var w)
>
>       results in pruning of `y` if the type of `w` doesn't depend on it.
>
> Does this sound right?
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20161128/f4b0f2b9/attachment.html