Scala中的類型安全完美二叉樹

我想在Scala中實現類型安全perfect binary tree。換句話說以下應編譯：Scala中的類型安全完美二叉樹

Succ(Node(Leaf("a"), Leaf("b"))) 
Node(
    Succ(Node(Leaf("a"), Leaf("b"))), 
    Succ(Node(Leaf("c"), Leaf("d"))))

但以下不宜：

Node(
    Succ(Node(Leaf("a"), Leaf("b"))), 
    Leaf("c"))

我想出了下面滿足上述但一個可以欺騙編譯器的解決方案：

Node(
    Leaf("f"): PerfectBinaryTree, 
    Succ(Node(Leaf("a"), Leaf("b"))): PerfectBinaryTree)

有沒有辦法在Scala中避免這種情況？與Haskell（如果有的話）有什麼不同？

trait PerfectBinaryTree { 
    type N <: PerfectBinaryTree 
    } 

    case class Succ[P <: PerfectBinaryTree](p: P) extends PerfectBinaryTree { 
    type N = Succ[P] 
    } 

    class Leaf[T] private (t: T) extends PerfectBinaryTree { 
    type N = Leaf[T] 
    } 

    object Leaf { 
    def apply[T](t: T): Leaf[T] = new Leaf(t) 
    } 

    case class Node[A <: PerfectBinaryTree, B <: PerfectBinaryTree](l: A, r: B)(implicit evidence: A =:= B) extends PerfectBinaryTree { 
    type N = A 
    }

來源

2015-10-20 mjaskowski

您在問題中有兩個問題。我建議你在這個問題中刪除對Haskell的任何引用，並最終要求在Haskell中實現這個相關問題。 – Bakuriu

在Haskell中，這將是'data PerfectBinaryTree a = Zero a | Succ（PerfectBinaryTree（BinaryNode a））'和'數據BinaryNode a =節點a a'。你似乎已經搞亂了你的Scala代碼中的這個結構。「葉」應該是「零」嗎？爲什麼他們都是同一班的情況？ – Bergi

很可能@Bergi，我搞砸了。是啊'葉=零'。如何安排回去？ ;）我會考慮這個@Bakuriu – mjaskowski

訣竅（就像在Haskell）是傳遞Node類型變量（polymorphic recursion）的內部。

類的定義，然後變得非常簡單

case class Node[+A](left: A, right: A); 

sealed trait Tree[+A]; 
case class Succ[+A](subtree: Tree[Node[A]]) extends Tree[A]; 
case class Leaf[+A](value: A) extends Tree[A];

（當然你要新增功能摺疊/遍歷這種樹等）

然後，創造價值的時候，構造函數的數量決定需要多少個Node。請注意，總是隻有一片葉子，但它包含由給定數量的Node級別組成的二叉樹：

val sample: Tree[String] = 
Succ(
    Succ(
    Leaf(
     Node(
     Node("a", "b"), 
     Node("c", "d") 
    ) 
    ) 
) 
);

來源

2015-10-20 19:12:51

哇！那裏有沒有這種知識的很好的來源？ – mjaskowski

@mjaskowski有關該主題的研究論文。例如，請參閱如何實施[Java中的類型安全紅黑樹]（http://www.cs.kent.ac.uk/people/staff/smk/redblack/rbj.pdf）。您可能還想要搜索Ralf Hinze關於「構建紅黑樹」主題的前一篇論文。 – chi

@mjaskowski我也建議閱讀着名的岡崎的着作_Purely Functional Data Structures_（原始論文可在線獲取）。特別是有一章「結構分解」談到了這一點。一般來說，多態遞歸是一個很好的技巧，值得探索。另一個好的指針是研究自然數的表示和數據結構之間的對應關係，也在同一本書中。在這種情況下，我們將代表兩個冪。 –

Scala中的類型安全完美二叉樹

回答

相關問題