diff options
Diffstat (limited to 'src/algebra/tree.spad.pamphlet')
| -rw-r--r-- | src/algebra/tree.spad.pamphlet | 98 |
1 files changed, 49 insertions, 49 deletions
diff --git a/src/algebra/tree.spad.pamphlet b/src/algebra/tree.spad.pamphlet index 5b573f8f..d4f187c0 100644 --- a/src/algebra/tree.spad.pamphlet +++ b/src/algebra/tree.spad.pamphlet @@ -64,10 +64,10 @@ Tree(S: SetCategory): T==C where children t == t case empty => error "cannot take the children of an empty tree" (t.node.args)@List(%) - setchildren_!(t,lt) == + setchildren!(t,lt) == t case empty => error "cannot set children of an empty tree" (t.node.args:=lt;t pretend %) - setvalue_!(t,s) == + setvalue!(t,s) == t case empty => error "cannot set value of an empty tree" (t.node.value:=s;s) count(n: S, t: %) == @@ -83,10 +83,10 @@ Tree(S: SetCategory): T==C where map(fn, t) == t case empty => t tree(fn value t,[map(fn, c) for c in children t]) - map_!(fn, t) == + map!(fn, t) == t case empty => t - setvalue_!(t, fn value t) - for c in children t repeat map_!(fn, c) + setvalue!(t, fn value t) + for c in children t repeat map!(fn, c) tree(s,lt) == [[s,lt]] tree(s) == [[s,[]]] tree(ls) == @@ -350,11 +350,11 @@ BinaryTreeCategory(S: SetCategory): Category == BinaryRecursiveAggregate(S) with empty? t => empty() node(copy left t, value t, copy right t) if % has shallowlyMutable then - map_!(f,t) == + map!(f,t) == empty? t => t t.value := f(t.value) - map_!(f,left t) - map_!(f,right t) + map!(f,left t) + map!(f,right t) t if % has finiteAggregate then treeCount : (%, NonNegativeInteger) -> NonNegativeInteger @@ -400,17 +400,17 @@ BinaryTree(S: SetCategory): Exports == Implementation where value t== empty? t => error "binaryTree:no value" value first t - setvalue_! (t,nd)== + setvalue! (t,nd)== empty? t => error "binaryTree:no value to set" - setvalue_!(first(t:Rep),nd) + setvalue!(first(t:Rep),nd) nd - setleft_!(t1,t2) == + setleft!(t1,t2) == empty? t1 => error "binaryTree:no left to set" - setchildren_!(first(t1:Rep),t2:Rep) + setchildren!(first(t1:Rep),t2:Rep) t1 - setright_!(t1,t2) == + setright!(t1,t2) == empty? t1 => error "binaryTree:no right to set" - setrest_!(t1:List Tree S,t2) + setrest!(t1:List Tree S,t2) @ \section{domain BSTREE BinarySearchTree} @@ -428,9 +428,9 @@ BinarySearchTree(S: OrderedSet): Exports == Implementation where finiteAggregate binarySearchTree: List S -> % ++ binarySearchTree(l) \undocumented - insert_!: (S,%) -> % + insert!: (S,%) -> % ++ insert!(x,b) inserts element x as leaves into binary search tree b. - insertRoot_!: (S,%) -> % + insertRoot!: (S,%) -> % ++ insertRoot!(x,b) inserts element x as a root of binary search tree b. split: (S,%) -> Record(less: %, greater: %) ++ split(x,b) splits binary tree b into two trees, one with elements greater @@ -440,14 +440,14 @@ BinarySearchTree(S: OrderedSet): Exports == Implementation where binarySearchTree(u:List S) == null u => empty() tree := binaryTree(first u) - for x in rest u repeat insert_!(x,tree) + for x in rest u repeat insert!(x,tree) tree - insert_!(x,t) == + insert!(x,t) == empty? t => binaryTree(x) x >= value t => - setright_!(t,insert_!(x,right t)) + setright!(t,insert!(x,right t)) t - setleft_!(t,insert_!(x,left t)) + setleft!(t,insert!(x,left t)) t split(x,t) == empty? t => [empty(),empty()] @@ -456,7 +456,7 @@ BinarySearchTree(S: OrderedSet): Exports == Implementation where [node(left t, value t, a.less), a.greater] a := split(x,left t) [a.less, node(a.greater, value t, right t)] - insertRoot_!(x,t) == + insertRoot!(x,t) == a := split(x,t) node(a.less, x, a.greater) @@ -475,22 +475,22 @@ BinaryTournament(S: OrderedSet): Exports == Implementation where binaryTournament: List S -> % ++ binaryTournament(ls) creates a binary tournament with the ++ elements of ls as values at the nodes. - insert_!: (S,%) -> % + insert!: (S,%) -> % ++ insert!(x,b) inserts element x as leaves into binary tournament b. Implementation == BinaryTree(S) add Rep := BinaryTree(S) binaryTournament(u:List S) == null u => empty() tree := binaryTree(first u) - for x in rest u repeat insert_!(x,tree) + for x in rest u repeat insert!(x,tree) tree - insert_!(x,t) == + insert!(x,t) == empty? t => binaryTree(x) x > value t => - setleft_!(t,copy t) - setvalue_!(t,x) - setright_!(t,empty()) - setright_!(t,insert_!(x,right t)) + setleft!(t,copy t) + setvalue!(t,x) + setright!(t,empty()) + setright!(t,insert!(x,right t)) t @ @@ -515,16 +515,16 @@ BalancedBinaryTree(S: SetCategory): Exports == Implementation where balancedBinaryTree: (NonNegativeInteger, S) -> % ++ balancedBinaryTree(n, s) creates a balanced binary tree with ++ n nodes each with value s. - setleaves_!: (%, List S) -> % + setleaves!: (%, List S) -> % ++ setleaves!(t, ls) sets the leaves of t in left-to-right order ++ to the elements of ls. - mapUp_!: (%, (S,S) -> S) -> S + mapUp!: (%, (S,S) -> S) -> S ++ mapUp!(t,f) traverses balanced binary tree t in an "endorder" ++ (left then right then node) fashion returning t with the value ++ at each successive interior node of t replaced by ++ f(l,r) where l and r are the values at the immediate ++ left and right nodes. - mapUp_!: (%, %, (S,S,S,S) -> S) -> % + mapUp!: (%, %, (S,S,S,S) -> S) -> % ++ mapUp!(t,t1,f) traverses t in an "endorder" (left then right then node) ++ fashion returning t with the value at each successive interior ++ node of t replaced by @@ -532,14 +532,14 @@ BalancedBinaryTree(S: SetCategory): Exports == Implementation where ++ left and right nodes. Values l1 and r1 are values at the ++ corresponding nodes of a balanced binary tree t1, of identical ++ shape at t. - mapDown_!: (%,S,(S,S) -> S) -> % + mapDown!: (%,S,(S,S) -> S) -> % ++ mapDown!(t,p,f) returns t after traversing t in "preorder" ++ (node then left then right) fashion replacing the successive ++ interior nodes as follows. The root value x is ++ replaced by q := f(p,x). The mapDown!(l,q,f) and ++ mapDown!(r,q,f) are evaluated for the left and right subtrees ++ l and r of t. - mapDown_!: (%,S, (S,S,S) -> List S) -> % + mapDown!: (%,S, (S,S,S) -> List S) -> % ++ mapDown!(t,p,f) returns t after traversing t in "preorder" ++ (node then left then right) fashion replacing the successive ++ interior nodes as follows. Let l and r denote the left and @@ -556,22 +556,22 @@ BalancedBinaryTree(S: SetCategory): Exports == Implementation where -- balancedBinaryTree(x: S, u: List S) == -- n := #u -- n = 0 => empty() --- setleaves_!(balancedBinaryTree(n, x), u) - setleaves_!(t, u) == +-- setleaves!(balancedBinaryTree(n, x), u) + setleaves!(t, u) == n := #u n = 0 => empty? t => t error "the tree and list must have the same number of elements" n = 1 => - setvalue_!(t,first u) + setvalue!(t,first u) t m := n quo 2 acc := empty()$(List S) for i in 1..m repeat acc := [first u,:acc] u := rest u - setleaves_!(left t, reverse_! acc) - setleaves_!(right t, u) + setleaves!(left t, reverse! acc) + setleaves!(right t, u) t balancedBinaryTree(n: NonNegativeInteger, val: S) == n = 0 => empty() @@ -579,33 +579,33 @@ BalancedBinaryTree(S: SetCategory): Exports == Implementation where m := n quo 2 node(balancedBinaryTree(m, val), val, balancedBinaryTree((n - m) pretend NonNegativeInteger, val)) - mapUp_!(x,fn) == + mapUp!(x,fn) == empty? x => error "mapUp! called on a null tree" leaf? x => x.value - x.value := fn(mapUp_!(x.left,fn),mapUp_!(x.right,fn)) - mapUp_!(x,y,fn) == + x.value := fn(mapUp!(x.left,fn),mapUp!(x.right,fn)) + mapUp!(x,y,fn) == empty? x => error "mapUp! is called on a null tree" leaf? x => leaf? y => x error "balanced binary trees are incompatible" leaf? y => error "balanced binary trees are incompatible" - mapUp_!(x.left,y.left,fn) - mapUp_!(x.right,y.right,fn) + mapUp!(x.left,y.left,fn) + mapUp!(x.right,y.right,fn) x.value := fn(x.left.value,x.right.value,y.left.value,y.right.value) x - mapDown_!(x: %, p: S, fn: (S,S) -> S ) == + mapDown!(x: %, p: S, fn: (S,S) -> S ) == empty? x => x x.value := fn(p, x.value) - mapDown_!(x.left, x.value, fn) - mapDown_!(x.right, x.value, fn) + mapDown!(x.left, x.value, fn) + mapDown!(x.right, x.value, fn) x - mapDown_!(x: %, p: S, fn: (S,S,S) -> List S) == + mapDown!(x: %, p: S, fn: (S,S,S) -> List S) == empty? x => x x.value := p leaf? x => x u := fn(x.left.value, x.right.value, p) - mapDown_!(x.left, u.1, fn) - mapDown_!(x.right, u.2, fn) + mapDown!(x.left, u.1, fn) + mapDown!(x.right, u.2, fn) x @ |