Mercurial > hg > Members > Moririn
annotate stack.agda @ 537:fffeaf0b0024
add stackTest redBlackTreeTest
author | ryokka |
---|---|
date | Wed, 10 Jan 2018 15:44:13 +0900 |
parents | f6060e1bf900 |
children | 4f692df9b3db |
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 |
484 | 6 open import Data.Nat |
478 | 7 |
484 | 8 ex : 1 + 2 ≡ 3 |
9 ex = refl | |
179 | 10 |
501 | 11 data Bool {n : Level } : Set n where |
161 | 12 True : Bool |
13 False : Bool | |
164 | 14 |
501 | 15 record _∧_ {n : Level } (a : Set n) (b : Set n): Set n where |
485 | 16 field |
17 pi1 : a | |
18 pi2 : b | |
477 | 19 |
496 | 20 data Maybe {n : Level } (a : Set n) : Set n where |
161 | 21 Nothing : Maybe a |
22 Just : a -> Maybe a | |
23 | |
515 | 24 record StackMethods {n m : Level } (a : Set n ) {t : Set m }(stackImpl : Set n ) : Set (m Level.⊔ n) where |
161 | 25 field |
26 push : stackImpl -> a -> (stackImpl -> t) -> t | |
27 pop : stackImpl -> (stackImpl -> Maybe a -> t) -> t | |
484 | 28 pop2 : stackImpl -> (stackImpl -> Maybe a -> Maybe a -> t) -> t |
483
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
29 get : stackImpl -> (stackImpl -> Maybe a -> t) -> t |
484 | 30 get2 : stackImpl -> (stackImpl -> Maybe a -> Maybe a -> t) -> t |
531 | 31 clear : stackImpl -> (stackImpl -> t) -> t |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
32 open StackMethods |
427 | 33 |
515 | 34 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
|
35 field |
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
36 stack : si |
515 | 37 stackMethods : StackMethods {n} {m} a {t} si |
38 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
|
39 pushStack d next = push (stackMethods ) (stack ) d (\s1 -> next (record {stack = s1 ; stackMethods = stackMethods } )) |
515 | 40 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
|
41 popStack next = pop (stackMethods ) (stack ) (\s1 d1 -> next (record {stack = s1 ; stackMethods = stackMethods }) d1 ) |
515 | 42 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
|
43 pop2Stack next = pop2 (stackMethods ) (stack ) (\s1 d1 d2 -> next (record {stack = s1 ; stackMethods = stackMethods }) d1 d2) |
515 | 44 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
|
45 getStack next = get (stackMethods ) (stack ) (\s1 d1 -> next (record {stack = s1 ; stackMethods = stackMethods }) d1 ) |
515 | 46 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
|
47 get2Stack next = get2 (stackMethods ) (stack ) (\s1 d1 d2 -> next (record {stack = s1 ; stackMethods = stackMethods }) d1 d2) |
531 | 48 clearStack : (Stack a si -> t) -> t |
49 clearStack next = clear (stackMethods ) (stack ) (\s1 -> next (record {stack = s1 ; stackMethods = stackMethods } )) | |
484 | 50 |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
51 open Stack |
427 | 52 |
496 | 53 data Element {n : Level } (a : Set n) : Set n where |
161 | 54 cons : a -> Maybe (Element a) -> Element a |
55 | |
496 | 56 datum : {n : Level } {a : Set n} -> Element a -> a |
161 | 57 datum (cons a _) = a |
58 | |
496 | 59 next : {n : Level } {a : Set n} -> Element a -> Maybe (Element a) |
161 | 60 next (cons _ n) = n |
61 | |
62 | |
164 | 63 {- |
64 -- cannot define recrusive record definition. so use linked list with maybe. | |
496 | 65 record Element {l : Level} (a : Set n l) : Set n (suc l) where |
161 | 66 field |
164 | 67 datum : a -- `data` is reserved by Agda. |
161 | 68 next : Maybe (Element a) |
69 -} | |
155 | 70 |
71 | |
164 | 72 |
496 | 73 record SingleLinkedStack {n : Level } (a : Set n) : Set n where |
161 | 74 field |
75 top : Maybe (Element a) | |
76 open SingleLinkedStack | |
155 | 77 |
499 | 78 pushSingleLinkedStack : {n m : Level } {t : Set m } {Data : Set n} -> SingleLinkedStack Data -> Data -> (Code : SingleLinkedStack Data -> t) -> t |
161 | 79 pushSingleLinkedStack stack datum next = next stack1 |
80 where | |
81 element = cons datum (top stack) | |
164 | 82 stack1 = record {top = Just element} |
161 | 83 |
155 | 84 |
499 | 85 popSingleLinkedStack : {n m : Level } {t : Set m } {a : Set n} -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> t) -> t |
161 | 86 popSingleLinkedStack stack cs with (top stack) |
87 ... | Nothing = cs stack Nothing | |
88 ... | Just d = cs stack1 (Just data1) | |
154 | 89 where |
161 | 90 data1 = datum d |
91 stack1 = record { top = (next d) } | |
154 | 92 |
499 | 93 pop2SingleLinkedStack : {n m : Level } {t : Set m } {a : Set n} -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> (Maybe a) -> t) -> t |
94 pop2SingleLinkedStack {n} {m} {t} {a} stack cs with (top stack) | |
484 | 95 ... | Nothing = cs stack Nothing Nothing |
499 | 96 ... | Just d = pop2SingleLinkedStack' {n} {m} stack cs |
484 | 97 where |
499 | 98 pop2SingleLinkedStack' : {n m : Level } {t : Set m } -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> (Maybe a) -> t) -> t |
484 | 99 pop2SingleLinkedStack' stack cs with (next d) |
100 ... | Nothing = cs stack Nothing Nothing | |
511 | 101 ... | Just d1 = cs (record {top = (next d1)}) (Just (datum d)) (Just (datum d1)) |
484 | 102 |
103 | |
499 | 104 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
|
105 getSingleLinkedStack stack cs with (top stack) |
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
106 ... | Nothing = cs stack Nothing |
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
107 ... | Just d = cs stack (Just data1) |
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
108 where |
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
109 data1 = datum d |
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
110 |
499 | 111 get2SingleLinkedStack : {n m : Level } {t : Set m } {a : Set n} -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> (Maybe a) -> t) -> t |
112 get2SingleLinkedStack {n} {m} {t} {a} stack cs with (top stack) | |
483
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
113 ... | Nothing = cs stack Nothing Nothing |
499 | 114 ... | Just d = get2SingleLinkedStack' {n} {m} stack cs |
483
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
115 where |
499 | 116 get2SingleLinkedStack' : {n m : Level} {t : Set m } -> SingleLinkedStack a -> (Code : SingleLinkedStack a -> (Maybe a) -> (Maybe a) -> t) -> t |
484 | 117 get2SingleLinkedStack' stack cs with (next d) |
118 ... | Nothing = cs stack Nothing Nothing | |
119 ... | Just d1 = cs stack (Just (datum d)) (Just (datum d1)) | |
120 | |
531 | 121 clearSingleLinkedStack : {n m : Level } {t : Set m } {a : Set n} -> SingleLinkedStack a -> (SingleLinkedStack a -> t) -> t |
122 clearSingleLinkedStack stack next = next (record {top = Nothing}) | |
483
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
123 |
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
124 |
496 | 125 emptySingleLinkedStack : {n : Level } {a : Set n} -> SingleLinkedStack a |
161 | 126 emptySingleLinkedStack = record {top = Nothing} |
127 | |
509
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
128 ----- |
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
129 -- 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
|
130 -- |
515 | 131 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
|
132 singleLinkedStackSpec = record { |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
133 push = pushSingleLinkedStack |
161 | 134 ; pop = popSingleLinkedStack |
484 | 135 ; pop2 = pop2SingleLinkedStack |
483
9098ec0a9e6b
add getSingleLinkedStack,get2SingleLinkedStack. but get2SingleLinkedStack not working now
ryokka
parents:
478
diff
changeset
|
136 ; get = getSingleLinkedStack |
484 | 137 ; get2 = get2SingleLinkedStack |
531 | 138 ; clear = clearSingleLinkedStack |
503
413ce51da50b
separate methods in stack.agda
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
502
diff
changeset
|
139 } |
161 | 140 |
515 | 141 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
|
142 createSingleLinkedStack = record { |
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
143 stack = emptySingleLinkedStack ; |
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
144 stackMethods = singleLinkedStackSpec |
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
145 } |
51f0d5e5d1e5
stack proof on indeterminate stack state
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
504
diff
changeset
|
146 |