Algebraic data types: Difference between revisions

=={{header|Bracmat}}==

 

= a x b y c zd

. !arg

 

Test:

, and can represent the algorithm directly

.

 

Output:

B

. ( B

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;

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>

 

Translation of several

{{works with|C sharp|8}}

 

class Tree

{{libheader|toadstool}}

 

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

color left val right)

 

=={{header|EchoLisp}}==

;; code adapted from Racket and Common Lisp

;; Illustrates matching on structures

</syntaxhighlight>

{{out}}

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

(when (!eq? 'empty n)

{{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 } }

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)))

 

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

-module(rbtree).

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

 

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

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

type colour= |Red |Black

 

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"

=={{header|Haskell}}==

 

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

 

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

 

'R';'';y;a:

:

Example use:

 

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

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

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.

For example:

 

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

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

 

'''pattern-matching.jq'''

 

def E: []; # the empty node

{{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

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.*

=={{header|Nim}}==

{{libheader|fusion/matching}}

{.experimental: "caseStmtMacros".}

 

 

=={{header|OCaml}}==

type color = R | B

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

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))

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;

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

=={{header|Picat}}==

{{trans|Prolog}}

T = e,

foreach (X in 1..10)

=={{header|PicoLisp}}==

{{trans|Prolog}}

(be color (B))

 

(ins @X @S (T @ @A @Y @B)) )</syntaxhighlight>

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))

-> NIL</syntaxhighlight>

Structural pattern matching was added to Python in version 3.10.

 

from enum import Enum

from typing import NamedTuple

{{trans|OCaml}}

 

#lang racket

 

{{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]] }

 

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

 

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

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)

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";

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. */

{{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::*;

of that object.

 

sealed abstract class Color

case object R extends Color

 

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

datatype color = R | B

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

=={{header|Swift}}==

{{works with|Swift|2+}}

enum Tree<A> {

case E

 

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 !

 

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

We can then code our solution similar to Haskell:

 

datatype define Tree = E | T color left val right

 

}

}</syntaxhighlight>

 

=={{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"

 

{{omit from|BBC BASIC}}

{{omit from|C}}

{{omit from|Pascal}}

{{omit from|Processing}}