再帰的データ型との統合

Question

suggestionのように、ツリーのようなネストされた構造体の再帰的なデータ型を使用するには、テストプログラムで再帰的なdatatyepを動作させようとしましたが、遭遇しました。

datatype 'a tree = 
    Leaf of { value : 'a } 
| Node of { value : 'a, left: 'a tree, right: 'a tree } 


fun recursivetreebuilder a n = 
    if n = 0 
    then 
     Leaf a 
    else 
     Node (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) 

ので、関数が再帰的にnまで減らさn秒で自身を呼び出すことにより、深さnのバイナリツリーを構築することになっている0

しかし、私は次のとおりです。

私のプログラムはこれですこのエラーを取得しています：再帰的なデータ型を使用して

Can't unify {left: 'a tree, right: 'a tree, value: 'a} with {value: 'b} * 
(Int32.int/int -> 'c) * (Int32.int/int -> 'c) (Field 1 missing) Found near if 
<(n, 0) then Leaf(a) else Node(a, recursivetreebuilder(...), ......) 

は別の統一ISSを解決することを意図していましたネストされたリストを使用するときはue。多分私は問題が他の質問に説明が与えられている場所を見ることができるはずですが、私はまだありません。

「フィールド1」はコンパイラが参照するもので、同じデータ型の異なる「サブタイプ」を統一できるようにするために再帰的なデータ型を意図したときになぜ統合できないのですか？

編集

が示唆構造のいくつかを試してみましたが、まだエラーを取得します。

datatype 'a tree = 
    Leaf of 'a 
    | Node of 'a tree * 'a tree 


fun recursivetreebuilder a n = 
    if n < 0 
    then 
     Leaf (a) 
    else 
     Node (recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) 

ため例えば私はここで二つの問題があります

val printList = fn : Int.int list -> unit 
Error- in 'recon_bintree.sml', line 12. 
Can't unify 'a with 'a * Int32.int/int (Type variable to be unified occurs in type) Found near if 
<(n, 0) then Leaf(a) else 
Node(recursivetreebuilder(a, ...), recursivetreebuilder(...)) 
Error- in 'recon_bintree.sml', line 12. 
Can't unify 'a with 'a * Int32.int/int (Type variable to be unified occurs in type) Found near if 
<(n, 0) then Leaf(a) else 
Node(recursivetreebuilder(a, ...), recursivetreebuilder(...)) 
Error- in 'recon_bintree.sml', line 12. 
Can't unify 'a tree with Int32.int/int -> 'b (Incompatible types) Found near if 
<(n, 0) then Leaf(a) else 
Node(recursivetreebuilder(a, ...), recursivetreebuilder(...)) 
Error- in 'recon_bintree.sml', line 12. 
Can't unify 'a tree with Int32.int/int -> 'b (Incompatible types) Found near if 
<(n, 0) then Leaf(a) else 
Node(recursivetreebuilder(a, ...), recursivetreebuilder(...)) 
Exception- Fail "Static errors (pass2)" raised 

Answer 1

を取得します。

最初の問題は(a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1))タプルではなくレコードであるのに対し、例えば— { value : 'a, left: 'a tree, right: 'a tree }ため—は、レコード型であることです。だから彼らは一致しません。 realを、intを期待する関数に渡すのと同じです。

（余談知識をひけらかす：技術的にタプル実際はレコードですが、非常に具体的なもの; (a, b, c)は{ 1 = a, 2 = b, 3 = c }のためのシンタックスシュガーで最も実用的な目的のために、あなただけの完全-別の類似が、-2としてタプルやレコードと考えることができます。しかし、今では、エラーメッセージが "Field 1"を参照した理由を知っています。

2番目の問題は、カリング（fun recursivetreebuilder a n = ...）を使用する関数を宣言していますが、それはタプル（recursivetreebuilder(a, n-1)）を持っています。

---

一つのアプローチは、これらの決定と一致するようにあなたのデータ型定義に固執し、カリー化を使用して機能を維持し、すべてを変更することです：レコードタイプを排除するために

datatype 'a tree = 
    Leaf of { value : 'a } 
| Node of { value : 'a, left: 'a tree, right: 'a tree } 

fun recursivetreebuilder a n = 
    if n = 0 
    then 
     Leaf { value = a} 
    else 
     Node { value = a, 
      left = recursivetreebuilder a (n-1), 
      right = recursivetreebuilder a (n-1) } 

をしたり、データ型の定義を変更し、カレーを除去する機能を変更してください：

datatype 'a tree = 
    Leaf of 'a 
| Node of 'a * 'a tree * 'a tree 

fun recursivetreebuilder (a, n) = 
    if n = 0 
    then 
     Leaf a 
    else 
     Node (a, recursivetreebuilder(a, n-1), recursivetreebuilder(a, n-1)) 

または上記を組み合わせてください。 （レコード対タプル問題の修正は、カリング対タプル問題の修正とは独立しています。）

---

ところで、私はそれがLeaf場合とNode場合の値の両方を含むことが間違いだと思います。現在の定義では、正確に0または正確に2つの要素を含むツリーを持つことは不可能です。

datatype 'a tree = 
    Leaf 
| Node of 'a * 'a tree * 'a tree 

または子供のノードを持つノードが、自分自身の無い値：

datatype 'a tree = 
    Leaf of 'a 
| Node of 'a tree * 'a tree 

または葉との区別をなくす代わりに

は、私はあなたが空の葉を持っていなければならないのどちらかだと思います子供をオプションにする：

datatype 'a tree = 
    Node of 'a * 'a tree option * 'a tree option