Algebraic data types: Difference between revisions

=={{header|Bracmat}}==

 

= a x b y c zd

. !arg

| insert$!arg

)

 

Test:

, and can represent the algorithm directly

.

& lst$tree

& done

 

Output:

B

. ( B

)

)

 

=={{header|C++}}==

C++ templates have a robust pattern matching facility, with some warts - for example, nested templates cannot be fully specialized, so we must use a dummy template parameter. This implementation uses C++17 deduced template parameters for genericity.

 

template<Color, class, auto, class> struct T;

struct E;

int main() {

print<insert_t<1, insert_t<2, insert_t<0, insert_t<4, E>>>>>();

 

===Run time===

Although C++ has structured bindings and pattern matching through function overloading, it is not yet possible to use them together so we must match the structure of the tree being rebalanced separately from decomposing it into its elements. A further issue is that function overloads are not ordered, so to avoid ambiguity we must explicitly reject any (ill-formed) trees that would match more than one case during rebalance.

 

#include <variant>

 

t = insert(std::string{argv[i]}, std::move(t));

print(t);

 

=={{header|C sharp}}==

Translation of several

{{works with|C sharp|8}}

 

class Tree

_ => this

};

{{out}}

<pre>

{{libheader|toadstool}}

 

(defstruct (red-black-tree (:constructor tree (color left val right)))

color left val right)

(defun insert (x s)

(toad-ecase1 (%insert x s)

 

=={{header|E}}==

 

=={{header|EchoLisp}}==

;; code adapted from Racket and Common Lisp

;; Illustrates matching on structures

(match (ins x s) [(N _ l v r) (N '⚫️ l v r)]))

{{out}}

(define (t-show n (depth 0))

(when (!eq? 'empty n)

(define T (for/fold [t 'empty] ([i 32]) (insert (random 100) t)))

(t-show T)

<small>

<pre>

{{trans|Erlang}}

But, it changed an API into the Elixir style.

def find(nil, _), do: :not_found

def find({ key, value, _, _, _ }, key), do: { :found, { key, value } }

|> RBtree.insert(6,-1) |> IO.inspect

|> RBtree.insert(7,0) |> IO.inspect

 

{{out}}

The <code>pcase</code> macro was added in Emacs 24.1. It's auto-loaded, so there's no need to add <code>(require 'pcase)</code> to your code.

 

(pcase tree

(`(B (R (R ,a ,x ,b) ,y ,c) ,z ,d) `(R (B ,a ,x ,b) ,y (B ,c ,z ,d)))

(dotimes (i 16)

(setq s (rbt-insert (1+ i) s)))

Output:

 

 

The code used here is extracted from [https://gist.github.com/mjn/2648040 Mark Northcott's GitHubGist].

-module(rbtree).

-export([insert/3, find/2]).

balance(T) ->

T.

 

Output:

 

=={{header|F_Sharp|F#}}==

// Pattern Matching. Nigel Galloway: January 15th., 2021

type colour= |Red |Black

|N(i,g,e,l) as node->if item>l then repair(i,g,insert e,l) elif item<l then repair(i,insert g,e,l) else node

match insert rbt with N(_,g,e,l)->N(Black,g,e,l) |_->Empty

=={{header|Go}}==

{{trans|Kotlin}}

 

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.

 

import "fmt"

}

fmt.Println(tr)

 

{{out}}

=={{header|Haskell}}==

 

data Tree a = E | T Color (Tree a) a (Tree a)

 

| x > y = balance col a y (ins b)

| otherwise = s

 

=={{header|J}}==

The following code represents a best effort translation of the current Haskell implementation of this task:

 

'R';'';y;a:

:

if. 'R'=wwC do. 'R';('B';e;K;<we);wK;<'B';wwe;wwK;<www return. end. end. end. end.

y

 

Example use:

 

┌─┬───────┬─┬───────┐

│R│┌─┬┬─┬┐│3│┌─┬┬─┬┐│

│ ││B││2│││ ││B││5│││

│ │└─┴┴─┴┘│ │└─┴┴─┴┘│

 

Note that by convention we treat the root node as black. This approach always labels it with 'R' which we ignore. However, if we wish to validate these trees, we must account for the discrepancy.

 

validate=: {{

if. 0=#y do. 1 return. end.

b=. check w

(*a)*(a=b)*b+'B'=C

 

Here, validate returns the effective "black depth" of the tree (treating the root node as black and treating empty nodes as black), or 0 if the tree is not balanced properly.

For example:

 

14 18 12 16 5 1 3 0 6 13 9 8 15 17 2 10 7 4 19 11

insert/?.~20

└─┴──────────────────────────────────────────────────────────────────────┴──┴────────────────────────────────────────────────────────────────────────┘

validate insert/?.~20

 

Finally a caution: red black trees exhibit poor cache coherency. In many (perhaps most or all) cases an amortized hierarchical linear sort mechanism will perform better than a red black tree implementation. (And that characteristic is especially true of this particular implementation.)

 

=={{header|jq}}==

 

'''bindings.jq'''

# assumption that . is free of JSON objects, and that any objects in

# $x will have distinct, singleton keys that are to be interpreted as

end

else null

 

'''pattern-matching.jq'''

 

def E: []; # the empty node

reduce range(0; $n) as $i (E; insert($i));

 

{{out}}

For brevity and perhaps visual appeal, the output from jq has been trimmed as per the following invocation:

<pre>

⚫

=={{header|Julia}}==

Julia's multiple dispatch model is based on the types of a function's arguments, but does not look deeper into the function's array arguments for the types of their contents. Therefore we do multi-dispatch on the balance function but then use an if statement within the multiply dispatched functions to further match based on argument vector contents.

 

abstract type AbstractColoredNode end

 

testRB()

<pre>

[B, [R, [B, [R, E, 1, E], 2, [R, E, 3, E]], 4, [B, E, 6, E]], 14, [B, E, 18, E]]]

Whilst Kotlin supports algebraic data types (via 'sealed classes') and destructuring of data classes, pattern matching on them (via the 'when' expression) is currently limited to matching the type. Consequently the balance() function is not very pretty!

 

import Color.*

}

println(tree)

 

{{out}}

=={{header|Nim}}==

{{libheader|fusion/matching}}

{.experimental: "caseStmtMacros".}

 

proc ins(t: var RBTree[T], x: T) = insImpl[T](t, x)

tt.ins(xx)

 

=={{header|OCaml}}==

type color = R | B

type 'a tree = E | T of color * 'a tree * 'a * 'a tree

in let T (_,a,y,b) = ins s

in T (B,a,y,b)

 

=={{header|Oz}}==

To match multiple variables at once, we create temporary tuples with "#".

 

case Col#A#X#B

of b#t(r t(r A X B) Y C )#Z#D then t(r t(b A X B) Y t(b C Z D))

in

t(b A Y B)

 

=={{header|Perl}}==

Each of the single letter variables declared right after $balanced, match an instance of $balanced, and if they succeed, store the result into the %+ hash.

 

use 5.010;

use strict;

}

print "Done\n";

{{out}}

<pre>Tree: <B,_,9,_>.

There is no formal support for this sort of thing in Phix, but that's not to say that whipping

something up is likely to be particularly difficult, so let's give it a whirl.

<span style="color: #000080;font-style:italic;">--

-- demo\rosetta\Pattern_matching.exw

<span style="color: #0000FF;">?</span><span style="color: #008000;">"done"</span>

<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>

{{out}}

<pre>

=={{header|Picat}}==

{{trans|Prolog}}

T = e,

foreach (X in 1..10)

printf("%*w[%w]\n",Indent,C,Y),

output(B,Indent+6).

{{out}}

<pre>

=={{header|PicoLisp}}==

{{trans|Prolog}}

(be color (B))

 

 

(be insert (@X @S (T B @A @Y @B))

Test:

@A=(T B E 2 E) @B=(T B (T R E 1 E) 2 E) @C=(T B (T R E 1 E) 2 (T R E 3 E))

 

=={{header|Prolog}}==

Structural pattern matching was added to Python in version 3.10.

 

from enum import Enum

from typing import NamedTuple

if __name__ == "__main__":

main()

 

{{out}}

{{trans|OCaml}}

 

#lang racket

 

 

(visualize (for/fold ([t 'empty]) ([i 16]) (insert i t)))

 

<pre>

{{works with|rakudo|2016.11}}

Raku doesn't have algebraic data types (yet), but it does have pretty good pattern matching in multi signatures.

 

multi balance(B,[R,[R,$a,$x,$b],$y,$c],$z,$d) { [R,[B,$a,$x,$b],$y,[B,$c,$z,$d]] }

$t = insert($_, $t) for (1..10).pick(*);

say $t.gist;

This code uses generic comparison operators <tt>before</tt> and <tt>after</tt>, so it should work on any ordered type.

{{out}}

 

An abstract pattern is recursively defined and may contain, among others, the following elements: Literal, VariableDeclaration, MultiVariable, Variable, List, Set, Tuple, Node, Descendant, Labelled, TypedLabelled, TypeConstrained. More explanation can be found in the [http://http://tutor.rascal-mpl.org/Courses/Rascal/Rascal.html#/Courses/Rascal/Patterns/Abstract/Abstract.html Documentation]. Some examples:

// Literal

rascal>123 := 123

Match black(leaf(3),leaf(4))

Match black(leaf(5),leaf(4))

 

===Concrete===

 

A concrete pattern is a quoted concrete syntax fragment that may contain variables. The syntax that is used to parse the concrete pattern may come from any module that has been imported in the module in which the concrete pattern occurs. Some examples of concrete patterns:

` Token1 Token2 ... Tokenn `

// A typed quoted pattern

<Type Var>

// A variable pattern

 

A full example of concrete patterns can be found in the [http://tutor.rascal-mpl.org/Courses/Recipes/Languages/Exp/Concrete/WithLayout/WithLayout.html Rascal Recipes].

There are two variants of the PatternsWitchAction. When the subject matches Pattern, the expression Exp is evaluated and the subject is replaced with the result. Secondly, when the subject matches Pattern, the (block of) Statement(s) is executed. See below for some ColoredTree examples:

 

data ColoredTree = leaf(int N)

| red(ColoredTree left, ColoredTree right)

case red(l, r) => green(l, r)

};

 

===Regular Expressions===

Regular expressions are noated between two slashes. Most normal regular expressions patterns are available, such as ., \n, \d, etc. Additionally, flags can be used to create case intensiveness.

 

bool: true

rascal>/a.c/ := "abc";

 

=={{header|REXX}}==

The nodes used for this example are taken from the Wikipedia example at: &nbsp;

[[https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#/media/File:Red-black_tree_example.svg red black tree, an example]]

parse arg nodes '/' insert /*obtain optional arguments from the CL*/

if nodes='' then nodes = 13.8.17 8.1.11 17.15.25 1.6 25.22.27 /*default nodes. */

if @.y\==. & @.y\=='' then call err "node is already defined: " y

end /*v*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

{{trans|Haskell}}

This would be a horribly inefficient way to implement a Red-Black Tree in Rust as nodes are being allocated and deallocated constantly, but it does show off Rust's pattern matching.

use self::Color::*;

use std::cmp::Ordering::*;

}

}

 

=={{header|Scala}}==

of that object.

 

sealed abstract class Color

case object R extends Color

}

}

 

Usage example:

 

=={{header|Standard ML}}==

datatype color = R | B

datatype 'a tree = E | T of color * 'a tree * 'a * 'a tree

T (B,a,y,b)

end

 

=={{header|Swift}}==

{{works with|Swift|2+}}

enum Tree<A> {

case E

return .E

}

 

=={{header|Tailspin}}==

 

Tailspin doesn't have type names, so here using a tag. Neither does it have destructuring (which seems to be posited in the problem statement). Arguably, pattern matching in Tailspin is more readable while still as concise.

processor RedBlackTree

data node <{VOID}|{colour: <='black'|='red'>, left: <node>, right: <node>, value: <> VOID}> local

end balance

templates ins&{into:}

when <..$into.value::raw> do { $into..., left: $ -> ins&{into: $into.left}} -> balance !

otherwise { $into..., right: $ -> ins&{into: $into.right}} -> balance !

1..5 -> \('$tree::toString;$#10;' -> !OUT::write $ -> !tree::insert \) -> !VOID

$tree::toString -> !OUT::write

{{out}}

<pre>

 

Tcl doesn't have algebraic types built-in, but they can be simulated using tagged lists, and a custom pattern matching control structure can be built:

package require Tcl 8.5

package provide datatype 0.1

proc default body { return -code return [list {} $body] }

}

We can then code our solution similar to Haskell:

 

datatype define Tree = E | T color left val right

 

}

}

 

=={{header|Wren}}==

{{trans|Go}}

Wren doesn't have either algebraic data types or pattern matching though, despite that, the ''T.balance()'' method looks better than I thought it would :)

var B = "B"

 

var tr = E.new()

for (i in 1..16) tr = tr.insert(i)

 

{{out}}

{{omit from|BBC BASIC}}

{{omit from|C}}

{{omit from|Pascal}}

{{omit from|Processing}}