Algebraic data types: Difference between revisions

Content added Content deleted

Inline

@@ Line 561: / Line 561: @@
 > rbtree:find(4,T8).
 {found,{4,-3}}
+</pre>
+=={{header|Go}}==
+{{trans|Kotlin}}
+<br>
+Go doesn't have algebraic data types as such though they can simulated (to a limited extent) by interfaces.
+However, pattern matching on interfaces (via the type switch statement and type assertions) is limited to matching the implementing type and so the balance() method is not very pleasant.
+<lang go>package main
+import "fmt"
+type Color string
+const (
+    R Color = "R"
+    B       = "B"
+)
+type Tree interface {
+    ins(x int) Tree
+}
+type E struct{}
+func (_ E) ins(x int) Tree {
+    return T{R, E{}, x, E{}}
+}
+func (_ E) String() string {
+    return "E"
+}
+type T struct {
+    cl Color
+    le Tree
+    aa int
+    ri Tree
+}
+func (t T) balance() Tree {
+    if t.cl != B {
+        return t
+    }
+    le, leIsT := t.le.(T)
+    ri, riIsT := t.ri.(T)
+    var lele, leri, rile, riri T
+    var leleIsT, leriIsT, rileIsT, ririIsT bool
+    if leIsT {
+        lele, leleIsT = le.le.(T)
+    }
+    if leIsT {
+        leri, leriIsT = le.ri.(T)
+    }
+    if riIsT {
+        rile, rileIsT = ri.le.(T)
+    }
+    if riIsT {
+        riri, ririIsT = ri.ri.(T)
+    }
+    switch {
+    case leIsT && leleIsT && le.cl == R && lele.cl == R:
+        _, t2, z, d := t.destruct()
+        _, t3, y, c := t2.(T).destruct()
+        _, a, x, b := t3.(T).destruct()
+        return T{R, T{B, a, x, b}, y, T{B, c, z, d}}
+    case leIsT && leriIsT && le.cl == R && leri.cl == R:
+        _, t2, z, d := t.destruct()
+        _, a, x, t3 := t2.(T).destruct()
+        _, b, y, c := t3.(T).destruct()
+        return T{R, T{B, a, x, b}, y, T{B, c, z, d}}
+    case riIsT && rileIsT && ri.cl == R && rile.cl == R:
+        _, a, x, t2 := t.destruct()
+        _, t3, z, d := t2.(T).destruct()
+        _, b, y, c := t3.(T).destruct()
+        return T{R, T{B, a, x, b}, y, T{B, c, z, d}}
+    case riIsT && ririIsT && ri.cl == R && riri.cl == R:
+        _, a, x, t2 := t.destruct()
+        _, b, y, t3 := t2.(T).destruct()
+        _, c, z, d := t3.(T).destruct()
+        return T{R, T{B, a, x, b}, y, T{B, c, z, d}}
+    default:
+        return t
+    }
+}
+func (t T) ins(x int) Tree {
+    switch {
+    case x < t.aa:
+        return T{t.cl, t.le.ins(x), t.aa, t.ri}.balance()
+    case x > t.aa:
+        return T{t.cl, t.le, t.aa, t.ri.ins(x)}.balance()
+    default:
+        return t
+    }
+}
+func (t T) destruct() (Color, Tree, int, Tree) {
+    return t.cl, t.le, t.aa, t.ri
+}
+func (t T) String() string {
+    return fmt.Sprintf("T(%s, %v, %d, %v)", t.cl, t.le, t.aa, t.ri)
+}
+func insert(tr Tree, x int) Tree {
+    t := tr.ins(x)
+    switch t.(type) {
+    case T:
+        tt := t.(T)
+        _, a, y, b := tt.destruct()
+        return T{B, a, y, b}
+    case E:
+        return E{}
+    default:
+        return nil
+    }
+}
+func main() {
+    var tr Tree = E{}
+    for i := 1; i <= 16; i++ {
+        tr = insert(tr, i)
+    }
+    fmt.Println(tr)
+}</lang>
+{{out}}
+<pre>
+T(B, T(B, T(B, T(B, E, 1, E), 2, T(B, E, 3, E)), 4, T(B, T(B, E, 5, E), 6, T(B, E, 7, E))), 8, T(B, T(B, T(B, E, 9, E), 10, T(B, E, 11, E)), 12, T(B, T(B, E, 13, E), 14, T(B, E, 15, T(R, E, 16, E)))))
 </pre>