first attempt to define bff (with holes)
[~helmut/bidiragda.git] / Bidir.agda
1 module Bidir where
2
3 open import Data.Bool hiding (_≟_)
4 open import Data.Nat
5 open import Data.Maybe
6 open import Data.List hiding (replicate)
7 open import Data.Product hiding (zip ; map)
8 open import Function
9 open import Relation.Nullary
10 open import Relation.Binary.Core
11
12 module NatMap where
13
14   NatMap : Set → Set
15   NatMap A = List (ℕ × A)
16
17   lookup : {A : Set} → ℕ → NatMap A → Maybe A
18   lookup n []       = nothing
19   lookup n ((m , a) ∷ xs) with n ≟ m
20   lookup n ((.n , a) ∷ xs) | yes refl = just a
21   lookup n ((m , a) ∷ xs)  | no ¬p    = lookup n xs
22
23   notMember : {A : Set} → ℕ → NatMap A → Bool
24   notMember n m = not (maybeToBool (lookup n m))
25
26   -- For now we simply prepend the element. This may lead to duplicates.
27   insert : {A : Set} → ℕ → A → NatMap A → NatMap A
28   insert n a m = (n , a) ∷ m
29
30   fromAscList : {A : Set} → List (ℕ × A) → NatMap A
31   fromAscList []       = []
32   fromAscList ((n , a) ∷ xs) = insert n a (fromAscList xs)
33
34   empty : {A : Set} → NatMap A
35   empty = []
36
37   union : {A : Set} → NatMap A → NatMap A → NatMap A
38   union []       m = m
39   union ((n , a) ∷ xs) m = insert n a (union xs m)
40
41 open NatMap
42
43 checkInsert : {A : Set} → ((x y : A) → Dec (x ≡ y)) → ℕ → A → NatMap A → Maybe (NatMap A)
44 checkInsert eq i b m with lookup i m
45 checkInsert eq i b m | just c with eq b c
46 checkInsert eq i b m | just .b | yes refl = just m
47 checkInsert eq i b m | just c  | no p    = nothing
48 checkInsert eq i b m | nothing = just (insert i b m)
49
50 assoc : {A : Set} → ((x y : A) → Dec (x ≡ y)) → List ℕ → List A → Maybe (NatMap A)
51 assoc _  []       []       = just empty
52 assoc eq (i ∷ is) (b ∷ bs) = maybe′ (checkInsert eq i b) nothing (assoc eq is bs)
53 assoc _  _        _        = nothing
54
55 generate : {A : Set} → (ℕ → A) → List ℕ → NatMap A
56 generate f []       = empty
57 generate f (n ∷ ns) = insert n (f n) (generate f ns)
58
59 -- this lemma is probably wrong, because two different NatMaps may represent the same semantic value.
60 lemma-1 : {τ : Set} → (eq : (x y : τ) → Dec (x ≡ y)) → (f : ℕ → τ) → (is : List ℕ) → assoc eq is (map f is) ≡ just (generate f is)
61 lemma-1 eq f []        = refl
62 lemma-1 eq f (i ∷ is′) = {!!}
63
64 idrange : ℕ → List ℕ
65 idrange zero = []
66 idrange (suc n) = zero ∷ (map suc (idrange n))
67
68 bff : ({A : Set} → List A → List A) → ({B : Set} → ((x y : B) → Dec (x ≡ y)) → List B → List B → Maybe (List B))
69 bff get eq s v = let s′ = idrange (length s)
70                      g  = fromAscList (zip s′ s)
71                      h  = assoc eq (get s′) v
72                      h′ = maybe′ (λ jh → just (union jh g)) nothing h
73                  in maybe′ (λ jh′ → just (map {!!} s′)) nothing h′