No account? Create an account
 Lindsey Kuper [entries|archive|friends|userinfo] Lindsey Kuper

 [ website | composition.al ] [ userinfo | livejournal userinfo ] [ archive | journal archive ]

Equivalent unzippers [Oct. 21st, 2010|11:50 pm]
Lindsey Kuper
 [ Tags | programming ]

In an effort to become more familiar with Coq, I've been working my way through the Software Foundations book. So far, it's been more about proving things with Coq than it's been about programming with it (although the distinction is blurry). Yesterday, though, I got to this problem. As the text explains, `combine`, better known as `zip`, is a function that takes two lists and combines them into a list of pairs. (For instance, given `[0, 1, 3, 18]` and `[true, false, false, true]`, it takes those two lists and "zips" them together, producing `[(0, true), (1, false), (3, false), (18, true)]`.)

The problem asks you to do the inverse: given the list of pairs, unzip it to produce the pair of lists. At first, the only way I could think of to do it was with `map`:

```Fixpoint map {X Y: Type} (fn : X -> Y) (lx : list X) : list Y :=
match lx with
| [] => []
| x::tx => fn x :: map fn tx
end.

Fixpoint split {X Y : Type} (lxy : list (X*Y))
: (list X * list Y) :=
(map fst lxy, map snd lxy).```

Later, I realized that I could do it in one pass provided I have a couple of accumulator arguments:

```Fixpoint split' {X Y : Type} (lxy : list (X*Y))
: (list X * list Y) :=
let fix f (res1 : list X) (res2 : list Y) (lxy : list (X*Y)) :=
match lxy with
| [] => (res1, res2)
| xy::txy => f (res1 ++ [(fst xy)]) (res2 ++ [(snd xy)]) txy
end
in f [] [] lxy.```

So, that was fun. But the larger point is that since I'm doing it in Coq, pretty soon I'll be able to do a machine-assisted proof that `split` and `split'` are equivalent, not to mention a proof that `split` (or `split'`) actually is the inverse of `combine`. That will be even better.

(Deleted comment)
 From: 2010-10-22 01:58 pm (UTC) (Link)

Because Chris showed-and-telled, I wrote it in Agda as well. Most of it is boilerplate because I 1) perversely insisted on using my own library and 2) I lazily haven't added lists to that library yet.

```module Kuper where

{- Bolierplate -}

open import Prelude

data List (A : Set) : Set where
[] : List A
_::_ : A → List A → List A

[_] : ∀{A} → A → List A
[ x ] = x :: []

_++_ : ∀{A} → List A -> List A -> List A
[] ++ ys = ys
(x :: xs) ++ ys = x :: (xs ++ ys)

append-cong2 : ∀{A} {a : A} {as bs : List A}
→ as ≡ bs
→ (a :: as) ≡ (a :: bs)
append-cong2 Refl = Refl

append-nil : ∀{A} {as : List A} → as ++ [] ≡ as
append-nil {as = []} = Refl
append-nil {as = a :: as} = append-cong2 (append-nil {as = as})

assoc-append : ∀{A} {as bs cs : List A}
→ (as ++ (bs ++ cs)) ≡ ((as ++ bs) ++ cs)
assoc-append {as = []} = Refl
assoc-append {as = a :: as} = append-cong2 (assoc-append {as = as})

map : ∀{A B} → (A → B) → List A → List B
map f [] = []
map f (x :: xs) = f x :: map f xs

{- Functions -}

split : ∀{A B} → List (A × B) → List A × List B
split lxy = (map fst lxy , map snd lxy)

split' : ∀{A B} → List (A × B) → List A → List B → List A × List B
split' [] xs ys = (xs , ys)
split' ((x , y) :: lxy) xs ys = split' lxy (xs ++ [ x ]) (ys ++ [ y ])

{- Equivalence -}

split-eq-lem : ∀{A B} (lx : List A) (ly : List B) (lxy : List (A × B))
→ (lx ++ map fst lxy , ly ++ map snd lxy) ≡ split' lxy lx ly
split-eq-lem lx ly [] = Product.pair-cong append-nil append-nil
split-eq-lem lx ly ((x , y) :: lxy) =
Product.pair-cong (assoc-append {as = lx}) (assoc-append {as = ly})
≡≡ split-eq-lem (lx ++ [ x ]) (ly ++ [ y ]) lxy

split-eq : ∀{A B} (lxy : List (A × B)) → split lxy ≡ split' lxy [] []
split-eq lxy = split-eq-lem [] [] lxy
```

Question: the most natural way to express this function, in Agda, was neither of your options. Is the following definition naturally expressible in Coq? This comparison example has taught me at least as much about Coq as I think I knew before, which is to say I know very little.

```  splitA : ∀{A B} → List (A × B) → List A × List B
splitA [] = ([] , [])
splitA ((x , y) :: lxy) = (x :: fst lxly) , (y :: snd lxly)
where lxly = splitA lxy
```
 From: 2010-10-22 02:24 pm (UTC) (Link)
Yikes. That program is a pretty strong argument for tactical theorem proving! (As an aside: your natural definition works, but makes you rewrite with the extensionality of pairs to deal with let-bindings showing up in mildly annoying fashion.)
```Set Implicit Arguments.
Unset Strict Implicit.
Import Prenex Implicits.
Require Import List.

Fixpoint split (X Y : Type) (xys : list (X * Y)) :=
match xys with
| nil => (nil, nil)
| cons (x,y) xys' =>
let (xs', ys') := split xys' in (cons x xs', cons y ys')
end.

Fixpoint zip (X Y : Type) (xs : list X) (ys : list Y) {struct xs} :=
match xs, ys with
| nil, _ => nil
| _, nil => nil
| (cons x xs'), (cons y ys') => cons (x,y) (zip xs' ys')
end.

Lemma pair_ext : forall (A B : Type) (a : A * B), a = (fst a, snd a).
Proof.
intros A B [u v]; simpl; auto. (* Why isn't this in the stdlib??? *)
Qed.

Lemma zipsplit : forall (X Y : Type) (xys : list (X * Y)),
let (xs, ys) := split xys in zip xs ys = xys.
Proof.
intros X Y; simpl; induction xys; [simpl; auto | unfold split; fold split].
rewrite (pair_ext a); rewrite (pair_ext (split xys)) in IHxys |- *.
simpl; rewrite IHxys; reflexivity.
Qed.
``` From: 2010-10-22 03:24 pm (UTC) (Link)
Question: the most natural way to express this function, in Agda, was neither of your options. Is the following definition naturally expressible in Coq?

I would hesitate to say that either of my options were the most natural way to express it in Coq, either. Well, the first one isn't bad. But the "most natural way" probably involves, first of all, letting the type inferencer do more work, and second, relying on libraries more. So, more like Neel did it, probably.
 From: 2010-10-22 09:25 pm (UTC) (Link)
Dan pointed out that if I want to prove equivalence of split and splitA the proof is actually very, very nice. I needed an annoying lemma whose proof is Refl = refl in this setup, but the proof is dead simple if that is factored out.

```  cong-lem : ∀{A B} {x : A} {y : B} {xs1 xs2 : List A} {ys1 ys2 : List B}
→ (xs1 , ys1) ≡ (xs2 , ys2)
→ IdT {A = List A × List B} (x :: xs1 , y :: ys1) (x :: xs2 , y :: ys2)
cong-lem Refl = refl

split-eqA : ∀{A B} → (lxy : List (A × B)) → split lxy ≡ splitA lxy
split-eqA [] = refl
split-eqA ((x , y) :: lxy) = cong-lem (split-eqA lxy)
``` From: 2010-10-22 02:56 pm (UTC) (Link)

Ooh, me next, me next!

Here it is in miniKanren:

```(import (minikanren vanilla))

(define zipo
(lambda (pairoflists listofpairs)
(matche `(,pairoflists ,listofpairs)
[( (() ()) () )]
[( ((,X . ,Xs) (,Y . ,Ys)) ((,X ,Y) . ,XYs) )
(zipo `(,Xs ,Ys) XYs)])))

> (run* (q) (zipo '((1 3 5) (2 4 6)) q))
(((1 2) (3 4) (5 6)))
> (run* (q) (zipo q '((1 2) (3 4) (5 6))))
(((1 3 5) (2 4 6)))
``` From: 2010-10-22 06:48 pm (UTC) (Link)

Meanwhile I've taken a try at it in Isabelle/HOL using Isar. I make no claim on how "native" this is, given my relative lack of experience in the system.

```theory Kuper
imports Main

begin

fun ksplit :: "('a * 'b) list ⇒ 'a list * 'b list"
where "ksplit ABs = (map fst ABs, map snd ABs)"

fun ksplit' :: "('a * 'b) list ⇒ 'a list * 'b list"
where
"ksplit' [] = ([], [])" |
"ksplit' ((a, b) # ABs) =
(case ksplit' ABs of
(As, Bs) ⇒ (a # As, b # Bs))"

theorem ksplit_ksplit' : "ksplit l = ksplit' l"
proof (induct l rule: ksplit'.induct)
case 1 thus ?case by simp
next
case (2 a b ABs)
assume H : "ksplit ABs = ksplit' ABs"
then have "ksplit' ABs = (map fst ABs, map snd ABs)" by simp
then have "ksplit' ((a, b) # ABs) = (a # map fst ABs, b # map snd ABs)" by simp
thus ?case by simp
qed

end```
(Deleted comment)
 From: 2010-10-22 06:02 am (UTC) (Link)
Do you actually get to prove that two coq functions are equivalent? How do you take apart the construction of split and split' to reason about them? I didn't think you could deal with meta level functions like that, but I've never really used Coq. From: 2010-10-22 03:12 pm (UTC) (Link)
Yeah, you do. How you "take apart" the definitions depends, but it's a matter of showing that given the same arguments they produce the same results. Look at how Neel did it up above. His `split'` (the one that uses `map`) is basically my `split`, while his `split` is sort of like my `split'` but prettier. Mine might be harder to prove stuff about -- I'm not really sure yet. From: 2010-10-22 06:04 pm (UTC) (Link)
The real problem is that zip() is of arity 2, and not arity n. An n-arity zip() is its own inverse! :)
(Deleted comment)
(Deleted comment) From: 2010-10-22 11:35 pm (UTC) (Link)
Eh, I posted the ACL2 version, and given the lack of higher-order functions, it's even less interesting (especially if you had to define your own `mapcar` and `mapcdr`).
From:
2010-10-26 06:52 pm (UTC)

### Proof language for non-PL-researchers?

Hey Lindsey et al!
If I wanted to learn one of these wild proof languages, say for doing geometric/computer-graphics proofs, what language would you recommend? I started working through a tutorial for that Omega language, which I understand is rather different from what the folks in this thread are using... but the documentation made it seem to be a better choice for a beginner.

If I'm concerned mostly with ease of use (and libraries for dealing with real numbers, I guess) what should I use? From: 