Как лучше смоделировать узел дерева?

Каковы плюсы и минусы каждого из следующих двух способов создания узла дерева?

type TreeNode = | TreeNode of int * (TreeNode option) * (TreeNode option) * (TreeNode option)



type Node = | Node of int * Node * Node

        | None

f# treenode
person user3703431    schedule 25.06.2014    source источник
comment
Этот вопрос, вероятно, лучше подходит для codereview.stackexchange.com.   -  person N_A    schedule 25.06.2014
comment
Ваш конструктор TreeNode имеет трех дочерних элементов вместо двух для Node.   -  person Lee    schedule 25.06.2014

Ответы (1)


arrow_upward
3
arrow_downward

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

Учитывая любой TreeNode(num, optLeft, optRight), вы всегда можете создать Node, содержащую ту же информацию (None типа опции будет сопоставлено с Node.None).

Интересно, что это не работает наоборот. Если кто-то даст вам Node.None, вы не сможете превратить его в TreeNode, потому что TreeNode нужно хотя бы одно целое число в корне.

Таким образом, они эквивалентны, за исключением того, что второй допускает пустые деревья. С практической точки зрения второй тип кажется более простым в использовании (потому что вам нужно обрабатывать пустое дерево только в одном месте).

person Tomas Petricek    schedule 25.06.2014