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′