Функциональные типы данных в javascript

Question

Как создать функциональные и рекурсивные типы данных в javascript?

Я хотел бы быть в состоянии сделать что-то вроде ML:

datatype binary_node = Node of binary_node*binary_node 
        | Lead of int 

Некоторое время назад я взял курс в функциональном программировании - курс был по каким-то случайным причинам, на схеме, и мы построили datatypes, создавая канистры, начиная с названия типа данных и затем «полезной нагрузки», является ли это способом создания типов данных типа программирования в Javascript?

construct_node(n1,n2) -> 
    ("Node", n1, n2). 

construct_leaf(int_value) -> 
    ("Leaf", int_value). 

, а затем тип проверки:

is_node(n) -> 
    if (n[0] == "Node") -> 
     is_binary_tree(n[1]) and is_binary_tree(n[2]) 
    else 
     false 
is_leaf(l) -> 
    if(l[0] == "Leaf") -> 
     is_integer(n[1]) 
    else 
     false 
is_binary_tree(t) -> 
    is_node(t) or is_leaf(t) 

Что бы самый умный способ сделать это в JavaScript?

Answer 1

JavaScript обычно используется в моделях duck typed. Таким образом, вам не нужно определять какие-либо специальные типы данных. Любой объект, имеющий свойства node1 и node2, может считаться двоичным узлом дерева.

var n = { 
    node1: { 
     node1: 456, 
     node2: 789 
    }, 
    node2: 1002 
}; 

function isNode(x) { 
    return x && isBinaryTree(x.node1) && isBinaryTree(x.node2); 
} 

function isLeaf(x) { 
    return typeof x === 'number'; 
} 

function isBinaryTree(x) { 
    return isNode(x) || isLeaf(x); 
} 

Обратите внимание, что функции выше для рекурсивно проверки целостности всего дерева, а не для узла по-узел случае различия во обходе.

Answer 2

Одним из способов, которые я видел, является создание функции-конструктора для каждого случая алгебраического типа данных и использование экземпляров тестов для реализации ветвления. Например, это то, как Roy language реализует сопоставления шаблонов и помеченные союзы.

var Node = function(a, b){ 
    //protect against people forgetting to use "new" to call the constructor: 
    if(!(this instanceof Node)){ return new Node(a, b) } 

    //optionaly do extra type checking, if that is your thing: 
    if(!(a instanceof Leaf)){ /*...*/ } 
    if(!(b instanceof Leaf)){ /*...*/ } 

    //save properties 
    this.node1 = a; 
    this.node2 = b; 
}; 

var Leaf = function(value){ 
    /*...*/ 
    this.value = value; 
}; 

Таким образом, тег внутреннее «__proto__» свойство, а полезная нагрузка обычного экземпляра proeprties в объекте.

Причина, по которой мне нравится этот подход, заключается в том, что он очень «безопасен по типу». Свойство внутреннего прототипа не редактируется, и использование конструктора или объекта (вместо символа или строки) делает его менее подверженным конфликтам имен, либо с разными типами, либо со свойствами вашего объекта.

Другим хорошим моментом является то, что в отличие от зависимости от утиного ввода этот подход также легко работает с перечислениями и другими ситуациями, когда разные случаи имеют одинаковый набор свойств.

Плохая вещь в Javascript заключается в том, что, как и в случае с LISP, у нее нет встроенной поддержки деструктуризации, поэтому вы можете создать настраиваемую функцию соответствия, такую ​​как следующая.

var match_tree = function(x, cases){ 
    //just a helper function to make things pretty 
    if(x instanceof Node){ 
     return cases.node.call(this, x.node1, x.node2); 
    }else if(x instanceof Leaf){ 
     return cases.leaf.call(this, x.value); 
    }else{ 
     throw new TypeError("pattern match failed"); 
    } 
}; 

var sum_leaves = function(tree){ 
    return match_tree(tree, { 
     node: function(val){ return val }, 
     leaf: function(left, right){ 
      return sum_leaves(left) + sum_leaves(right); 
     } 
    }); 
}; 

Answer 3

Я являюсь создателем языка под названием Roy. Рой - это язык со статическими типами, алгебраическими типами данных и сопоставлением шаблонов. Он также компилируется в JavaScript.

Ваш пример будет выглядеть примерно так:

data Tree = Node Tree Tree | Leaf Number 

Номер является встроенный тип JavaScript.

Теперь мы можем шаблон матч на ADT:

let isNode n = match n 
    case (Node a b) = true 
    case (Leaf l) = false 

let isLeaf l = match l 
    case (Leaf l) = true 
    case (Node a b) = false 

Вот результат JavaScript:

var Node = function(Tree_0, Tree_1) { 
    if(!(this instanceof Node)) { 
     return new Node(Tree_0, Tree_1); 
    } 
    this._0 = Tree_0; 
    this._1 = Tree_1; 
}; 
var Leaf = function(Number_0) { 
    if(!(this instanceof Leaf)) { 
     return new Leaf(Number_0); 
    } 
    this._0 = Number_0; 
}; 
var isNode = function(n) { 
    return (function() { 
     if(n instanceof Node) { 
      var a = n._0; 
      var b = n._1; 
      return true; 
     } else if(n instanceof Leaf) { 
      var l = n._0; 
      return false; 
     } 
    })(); 
}; 
var isLeaf = function(l) { 
    return (function() { 
     if(l instanceof Leaf) { 
      var l = l._0; 
      return true; 
     } else if(l instanceof Node) { 
      var a = l._0; 
      var b = l._1; 
      return false; 
     } 
    })(); 
};