Mercurial > hg > Gears > GearsAgda
annotate stack.agda @ 720:e9d781c38629
Ok this is a termination bug og agda
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 16 May 2022 17:55:19 +0900 |
parents | 73fc32092b64 |
children | 0b791ae19543 |
rev | line source |
---|---|
499 | 1 open import Level renaming (suc to succ ; zero to Zero ) |
496 | 2 module stack where |
154 | 3 |
161 | 4 open import Relation.Binary.PropositionalEquality |
477 | 5 open import Relation.Binary.Core |
575 | 6 open import Data.Nat hiding (compare) |
7 open import Data.Maybe | |
478 | 8 |
484 | 9 ex : 1 + 2 ≡ 3 |
10 ex = refl | |
179 | 11 |
575 | 12 -- data Bool {n : Level } : Set n where |
13 -- True : Bool | |
14 -- False : Bool | |
164 | 15 |
575 | 16 -- record _∧_ {n : Level } (a : Set n) (b : Set n): Set n where |
17 -- field | |
18 -- pi1 : a | |
19 -- pi2 : b | |
477 | 20 |
575 | 21 -- data _∨_ {n : Level } (a : Set n) (b : Set n): Set n where |
22 -- pi1 : a -> a ∨ b | |
23 -- pi2 : b -> a ∨ b | |
554
988c12d7f887
use another nat comparator
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
544
diff
changeset
|
24 |
575 | 25 -- data Maybe {n : Level } (a : Set n) : Set n where |
26 -- nothing : Maybe a | |
27 -- just : a -> Maybe a | |
161 | 28 |
574 | 29 record StackMethods {n m : Level } (a : Set n ) {t : Set m } (stackImpl : Set n ) : Set (m Level.⊔ n) where |
161 | 30 field |
31 push : stackImpl -> a -> (stackImpl -> t) -> t | |
32 pop : stackImpl -> (stackImpl -> Maybe a -> t) -> t | |
484 | 33 pop2 : stackImpl -> (stackImpl -> Maybe a -> Maybe a -> t) -> t |
483
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
34 get : stackImpl -> (stackImpl -> Maybe a -> t) -> t |
484 | 35 get2 : stackImpl -> (stackImpl -> Maybe a -> Maybe a -> t) -> t |
531 | 36 clear : stackImpl -> (stackImpl -> t) -> t |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
37 open StackMethods |
427 | 38 |
515 | 39 record Stack {n m : Level } (a : Set n ) {t : Set m } (si : Set n ) : Set (m Level.⊔ n) where |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
40 field |
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
41 stack : si |
515 | 42 stackMethods : StackMethods {n} {m} a {t} si |
43 pushStack : a -> (Stack a si -> t) -> t | |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
44 pushStack d next = push (stackMethods ) (stack ) d (\s1 -> next (record {stack = s1 ; stackMethods = stackMethods } )) |
515 | 45 popStack : (Stack a si -> Maybe a -> t) -> t |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
46 popStack next = pop (stackMethods ) (stack ) (\s1 d1 -> next (record {stack = s1 ; stackMethods = stackMethods }) d1 ) |
515 | 47 pop2Stack : (Stack a si -> Maybe a -> Maybe a -> t) -> t |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
48 pop2Stack next = pop2 (stackMethods ) (stack ) (\s1 d1 d2 -> next (record {stack = s1 ; stackMethods = stackMethods }) d1 d2) |
515 | 49 getStack : (Stack a si -> Maybe a -> t) -> t |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
50 getStack next = get (stackMethods ) (stack ) (\s1 d1 -> next (record {stack = s1 ; stackMethods = stackMethods }) d1 ) |
515 | 51 get2Stack : (Stack a si -> Maybe a -> Maybe a -> t) -> t |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
52 get2Stack next = get2 (stackMethods ) (stack ) (\s1 d1 d2 -> next (record {stack = s1 ; stackMethods = stackMethods }) d1 d2) |
531 | 53 clearStack : (Stack a si -> t) -> t |
54 clearStack next = clear (stackMethods ) (stack ) (\s1 -> next (record {stack = s1 ; stackMethods = stackMethods } )) | |
484 | 55 |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
56 open Stack |
427 | 57 |
544 | 58 {-- |
496 | 59 data Element {n : Level } (a : Set n) : Set n where |
161 | 60 cons : a -> Maybe (Element a) -> Element a |
61 | |
544 | 62 |
496 | 63 datum : {n : Level } {a : Set n} -> Element a -> a |
161 | 64 datum (cons a _) = a |
65 | |
496 | 66 next : {n : Level } {a : Set n} -> Element a -> Maybe (Element a) |
161 | 67 next (cons _ n) = n |
544 | 68 --} |
161 | 69 |
70 | |
164 | 71 -- cannot define recrusive record definition. so use linked list with maybe. |
544 | 72 record Element {l : Level} (a : Set l) : Set l where |
73 inductive | |
74 constructor cons | |
161 | 75 field |
164 | 76 datum : a -- `data` is reserved by Agda. |
161 | 77 next : Maybe (Element a) |
155 | 78 |
544 | 79 open Element |
155 | 80 |
164 | 81 |
496 | 82 record SingleLinkedStack {n : Level } (a : Set n) : Set n where |
161 | 83 field |
84 top : Maybe (Element a) | |
85 open SingleLinkedStack | |
155 | 86 |
499 | 87 pushSingleLinkedStack : {n m : Level } {t : Set m } {Data : Set n} -> SingleLinkedStack Data -> Data -> (Code : SingleLinkedStack Data -> t) -> t |
161 | 88 pushSingleLinkedStack stack datum next = next stack1 |
89 where | |
90 element = cons datum (top stack) | |
575 | 91 stack1 = record {top = just element} |
161 | 92 |
155 | 93 |
499 | 94 popSingleLinkedStack : {n m : Level } {t : Set m } {a : Set n} -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> t) -> t |
161 | 95 popSingleLinkedStack stack cs with (top stack) |
575 | 96 ... | nothing = cs stack nothing |
97 ... | just d = cs stack1 (just data1) | |
154 | 98 where |
161 | 99 data1 = datum d |
100 stack1 = record { top = (next d) } | |
154 | 101 |
499 | 102 pop2SingleLinkedStack : {n m : Level } {t : Set m } {a : Set n} -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> (Maybe a) -> t) -> t |
103 pop2SingleLinkedStack {n} {m} {t} {a} stack cs with (top stack) | |
575 | 104 ... | nothing = cs stack nothing nothing |
105 ... | just d = pop2SingleLinkedStack' {n} {m} stack cs | |
484 | 106 where |
499 | 107 pop2SingleLinkedStack' : {n m : Level } {t : Set m } -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> (Maybe a) -> t) -> t |
484 | 108 pop2SingleLinkedStack' stack cs with (next d) |
575 | 109 ... | nothing = cs stack nothing nothing |
110 ... | just d1 = cs (record {top = (next d1)}) (just (datum d)) (just (datum d1)) | |
484 | 111 |
112 | |
499 | 113 getSingleLinkedStack : {n m : Level } {t : Set m } {a : Set n} -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> t) -> t |
483
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
114 getSingleLinkedStack stack cs with (top stack) |
575 | 115 ... | nothing = cs stack nothing |
116 ... | just d = cs stack (just data1) | |
483
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
117 where |
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
118 data1 = datum d |
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
119 |
499 | 120 get2SingleLinkedStack : {n m : Level } {t : Set m } {a : Set n} -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> (Maybe a) -> t) -> t |
121 get2SingleLinkedStack {n} {m} {t} {a} stack cs with (top stack) | |
575 | 122 ... | nothing = cs stack nothing nothing |
123 ... | just d = get2SingleLinkedStack' {n} {m} stack cs | |
483
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
124 where |
499 | 125 get2SingleLinkedStack' : {n m : Level} {t : Set m } -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> (Maybe a) -> t) -> t |
484 | 126 get2SingleLinkedStack' stack cs with (next d) |
575 | 127 ... | nothing = cs stack nothing nothing |
128 ... | just d1 = cs stack (just (datum d)) (just (datum d1)) | |
484 | 129 |
531 | 130 clearSingleLinkedStack : {n m : Level } {t : Set m } {a : Set n} -> SingleLinkedStack a -> (SingleLinkedStack a -> t) -> t |
575 | 131 clearSingleLinkedStack stack next = next (record {top = nothing}) |
483
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
132 |
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
133 |
496 | 134 emptySingleLinkedStack : {n : Level } {a : Set n} -> SingleLinkedStack a |
575 | 135 emptySingleLinkedStack = record {top = nothing} |
161 | 136 |
509
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
137 ----- |
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
138 -- Basic stack implementations are specifications of a Stack |
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
139 -- |
515 | 140 singleLinkedStackSpec : {n m : Level } {t : Set m } {a : Set n} -> StackMethods {n} {m} a {t} (SingleLinkedStack a) |
509
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
141 singleLinkedStackSpec = record { |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
142 push = pushSingleLinkedStack |
161 | 143 ; pop = popSingleLinkedStack |
484 | 144 ; pop2 = pop2SingleLinkedStack |
483
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
145 ; get = getSingleLinkedStack |
484 | 146 ; get2 = get2SingleLinkedStack |
531 | 147 ; clear = clearSingleLinkedStack |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
148 } |
161 | 149 |
515 | 150 createSingleLinkedStack : {n m : Level } {t : Set m } {a : Set n} -> Stack {n} {m} a {t} (SingleLinkedStack a) |
509
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
151 createSingleLinkedStack = record { |
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
152 stack = emptySingleLinkedStack ; |
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
153 stackMethods = singleLinkedStackSpec |
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
154 } |
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
155 |