Jump to content

Algebraic data types: Difference between revisions

Algebraic data types (view source)

Revision as of 16:57, 19 May 2013

452 bytes added ,  11 years ago
→‎{{header|Racket}}
No edit summary
Line 580:
{{trans|OCaml}}
 
<lang scheme>#lang racket>
#lang racket
 
;; Using short names to make the code line up nicely
(struct t-nodeN (color t-left value t-right) #:prefab)
 
(define (balance t)
(match t
[(t-nodeN 'blackB (t-nodeN 'redR (t-nodeN 'redR a x b) y c) z d) (N 'R (N 'B a x b) y (N 'B c z d))]
[(N 'B (N 'R a x (N 'R b y c)) z d) (t-nodeN 'redR (t-nodeN 'blackB a x b) y (t-nodeN 'blackB c z d))]
[(t-nodeN 'black (t-node 'redB a x (t-nodeN 'redR (N 'R b y c) z d)) (N 'R (N 'B a x b) y (N 'B c z d))]
[(N 'B a x (N 'R b y (N 'R c z d))) (t-nodeN 'redR (t-nodeN 'blackB a x b) y (t-nodeN 'blackB c z d))]
[(t-node 'black a x (t-node 'red (t-node 'red b y c) z d))
(t-node 'red (t-node 'black a x b) y (t-node 'black c z d))]
[(t-node 'black a x (t-node 'red b y (t-node 'red c z d)))
(t-node 'red (t-node 'black a x b) y (t-node 'black c z d))]
[else t]))
 
Line 599 ⟶ 597:
(define (ins t)
(match t
['empty (t-nodeN 'redR 'empty x 'empty)]
[(t-nodeN c al yv br) (cond [(< x v) (balance (N c (ins l) v r))]
(cond [(<> x yv) (balance (N c l v (ins r)))]
(balance (t-node c (ins a) y b) [else t])]))
(match (ins s) [(N _ l v r) (N 'B l [(> xv yr)]))
 
(balance (t-node c a y (ins b)))]
(define (visualize t0)
[else t])]))
(let loop ([t t0] [last? #t] [indent '()])
(match (ins s)
[(t-nodedefine _(I amid y blast) (cond [(eq? t-node 'blackt0) a""] y[last? b)mid] [else last]))</lang>
(for-each display (reverse indent))
(printf "~a~a[~a]\n" (I "\\-" "+-") (N-value t) (N-color t))
(define subs (filter N? (list (N-left t) (N-right t))))
(for ([s subs] [n (in-range (sub1 (length subs)) -1 -1)])
(loop s (zero? n) (cons (I " " "| ") indent)))))
 
(visualize (for/fold ([t 'empty]) ([i 16]) (insert i t)))
</lang>
 
<pre>
7[B]
+-3[B]
| +-1[B]
| | +-0[B]
| | \-2[B]
| \-5[B]
| +-4[B]
| \-6[B]
\-11[B]
+-9[B]
| +-8[B]
| \-10[B]
\-13[B]
+-12[B]
\-14[B]
\-15[R]
</pre>
 
=={{header|Rascal}}==
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/40910"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information