[Agda] Questions about unification

Andreas Abel abela at chalmers.se
Mon Nov 28 09:15:19 CET 2016


 > Does this sound right?

Yes.  That is what should be implemented in Agda.

On 28.11.2016 08:49, Roman wrote:
> 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
>


-- 
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

andreas.abel at gu.se
http://www2.tcs.ifi.lmu.de/~abel/


More information about the Agda mailing list