[Agda] How can we define a type of symmetric binary operations in
Agda ?
Dr. ÉRDI Gergő
gergo at erdi.hu
Wed May 6 05:51:51 CEST 2015
Hang on a sec, in retrospect, isn't this exactly the same as defining a
function in terms of min(x,y) and abs(x-y)?
I'll have to see how awkward it is in practice to prove it, but any
commutative function
f : Nat -> Nat -> X
can be written as
f x y = h (min x y) (diff x y)
Which is of course also
h $ symIter (\b -> (b, 0)) (\(b,s) -> (b,su s)) x y
(Which is also a proof if symIter's completeness)
On May 5, 2015 8:26 PM, "Dr. ERDI Gergo" <gergo at erdi.hu> wrote:
> On Tue, 5 May 2015, Conor McBride wrote:
>
> Here's an old exercise of mine. Given
>>
>> data Nat : Set where
>> ze : Nat
>> su : Nat -> Nat
>>
>> symIter : {X : Set} -> (Nat -> X) -> (X -> X) -> Nat -> Nat -> X
>> symIter zen more ze n = zen n
>> symIter zen more m ze = zen m
>> symIter zen more (su m) (su n) = more (symIter zen more m n)
>>
>> Then define max, min, addition and multiplication by instantiating zen and
>> more appropriately.
>>
>
> OK, I've done this exercise now. Multiplication is the odd one out that
> was tricky to implement; I wonder if there's a more straightforward way
> than mine?
>
> https://gist.github.com/gergoerdi/46ad83513fd9db65c286
>
> Now the real question is, what is the general, (semi-)mechanizable way of
> going from (some description of) an argument type A to the definition of
>
> symIter :: {X : Set} -> (A -> X) -> (X -> X) -> A -> A -> X
>
> ?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20150506/fae3ffd6/attachment.html
More information about the Agda
mailing list