Algebraic data types: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,792: / Line 1,792: @@
 insert(X,S,t(b,A,Y,B)) :- ins(X,S,t(_,A,Y,B)).
+</pre>
+=={{header|Python}}==
+{{trans|C sharp}}
+Structural pattern matching was added to Python in version 3.10.
+<lang python>from __future__ import annotations
+from enum import Enum
+from typing import NamedTuple
+from typing import Optional
+class Color(Enum):
+    B = 0
+    R = 1
+class Tree(NamedTuple):
+    color: Color
+    left: Optional[Tree]
+    value: int
+    right: Optional[Tree]
+    def insert(self, val: int) -> Tree:
+        return self._insert(val).make_black()
+    def _insert(self, val: int) -> Tree:
+        match compare(val, self.value):
+            case _ if self == EMPTY:
+                return Tree(Color.R, EMPTY, val, EMPTY)
+            case -1:
+                assert self.left is not None
+                return Tree(
+                    self.color, self.left._insert(val), self.value, self.right
+                ).balance()
+            case 1:
+                assert self.right is not None
+                return Tree(
+                    self.color, self.left, self.value, self.right._insert(val)
+                ).balance()
+            case _:
+                return self
+    def balance(self) -> Tree:
+        match self:
+            case (Color.B, (Color.R, (Color.R, a, x, b), y, c), z, d):
+                return Tree(Color.R, Tree(Color.B, a, x, b), y, Tree(Color.B, c, z, d))
+            case (Color.B, (Color.R, a, x, (Color.R, b, y, c)), z, d):
+                return Tree(Color.R, Tree(Color.B, a, x, b), y, Tree(Color.B, c, z, d))
+            case (Color.B, a, x, (Color.R, (Color.R, b, y, c), z, d)):
+                return Tree(Color.R, Tree(Color.B, a, x, b), y, Tree(Color.B, c, z, d))
+            case (Color.B, a, x, (Color.R, b, y, (Color.R, c, z, d))):
+                return Tree(Color.R, Tree(Color.B, a, x, b), y, Tree(Color.B, c, z, d))
+            case _:
+                return self
+    def make_black(self) -> Tree:
+        return self._replace(color=Color.B)
+    def __str__(self) -> str:
+        if self == EMPTY:
+            return "[]"
+        return f"[{'R' if self.color == Color.R else 'B'}{self.value}]"
+    def print(self, indent: int = 0) -> None:
+        if self != EMPTY:
+            assert self.right is not None
+            self.right.print(indent + 1)
+        print(f"{' ' * indent * 4}{self}")
+        if self != EMPTY:
+            assert self.left is not None
+            self.left.print(indent + 1)
+EMPTY = Tree(Color.B, None, 0, None)
+def compare(x: int, y: int) -> int:
+    if x > y:
+        return 1
+    if x < y:
+        return -1
+    return 0
+def main():
+    tree = EMPTY
+    for i in range(1, 17):
+        tree = tree.insert(i)
+    tree.print()
+if __name__ == "__main__":
+    main()
+</lang>
+{{out}}
+<pre>
+                    []
+                [R16]
+                    []
+            [B15]
+                []
+        [B14]
+                []
+            [B13]
+                []
+    [B12]
+                []
+            [B11]
+                []
+        [B10]
+                []
+            [B9]
+                []
+[B8]
+                []
+            [B7]
+                []
+        [B6]
+                []
+            [B5]
+                []
+    [B4]
+                []
+            [B3]
+                []
+        [B2]
+                []
+            [B1]
+                []
 </pre>
@@ Line 2,540: / Line 2,674: @@
 {{omit from|Pascal}}
 {{omit from|Processing}}
-{{omit from|Python}}
 {{omit from|TI-83 BASIC}}
 {{omit from|TI-89 BASIC}}