Scalaでクラスを2つのリンクリストのメンバーにする方法はありますか？

Question

私はここで非常に明白な何かが欠けていると感じています。

私は、Javaで書かれたコンパイラジェネレータを学習の練習としてScalaに変換しています。これは、本当にJavaで書かれていない

、それはプログラムの一部ではC.

を音訳しているようだ、ノードがあります。各ノードは2つのリンクされたリストの一部であり、リンクされたリストのそれぞれの次の項目への参照であるフィールドがあります（これらを「横断」および「下」と呼びます）。これらのリストのいずれか、または両方をトラバースするさまざまな方法が、それぞれの訪問先ノードに何かを行います。

これらの明示的な参照の代わりにScalaのコレクションを使用したいと思います。定型的なコードが多数あり、これらのリストに要素を追加しています。これはどうすればいいですか？リストはかなり変更可能ですので、変更可能なリストを使用したいです

ノードのリンクされたリストを望んでいないと思います。各ノードは隣り合わせの（または下に）隣接ノードが何であるかを知る必要があるからです。このノードに到達したので、Nodeからどちらかのリストに移動する必要があります。

私はLinkedListから継承することができますが、私はそれを2回（横一回、下一回）行う必要があります。

私はLinkedListのインスタンスごとに2つの内部クラス（acrosslistとdownlist）を持つことができますが、LinkedList [Node]にすることはできますか？リストの次の参照はnode.acrosslist.next（say）である必要があり、LinkedListの場合はちょうど "次の"ものである必要があるため、これがどのように機能するかについて頭を浮かべることはできません。

このように、明らかに、または明らかではない場合、どうすればこの問題が発生するのかを教えてください。

Answer 1

あなたは自分自身をリンクし、各方向のイテレーターを作成してみませんか？

class Node(var left: Node, var down: Node) { 
    def iterateDown = new Iterator[Node] { 
    private[this] var current = this 
    def hasNext = down ne null 
    def next = { current = down; current } 
    } 
    def iterateLeft = new Iterator[Node] { 
    private[this] var current = this 
    def hasNext = left ne null 
    def next = { current = left; current } 
    } 
} 

Answer 2

私はRex Kerrのanswer上のビットを拡張してみましょう。 Scalaのコレクションには本当に3つの中心的なクラスがあり、それらのうち2つだけが実際にコレクションの一部です。それらはTraversable,IterableおよびIteratorです。

最も基本的なコレクションはTraversableです。 Traversableには、必要なものは1つだけです。メソッドforeachを実装する必要があります。したがって、コレクションの各要素に適用される関数を渡すことができる限り、Traversableにすることができます。たとえば：

class Three[A](a: A, b: A, c: A) extends Traversable[A] { 
    def foreach[U](f: (A) => U) {  
     f(a); f(b); f(c) 
    } 
} 

これは、このようなmapやfilterなどの方法がThreeを返さないでしょうが、あなたにTraversableすべてのメソッドを与えるが、Traversableます。あなたが定義したクラスを返すことははるかに難しく、多くの特殊なクラスではできません。たとえば、Threeは実行できません。Threeのfilterがいくつか削除されているためですか？

次に、Iteratorがあります。これは実際にはTraversableとほぼ同じですが、異なる方法です。 Iteratorは、nextとhasNextの2つのメソッドを定義する必要があります。たとえば：

class Three[A](a: A, b: A, c: A) extends Iterator[A] { 
    private var aReady, bIsRead, cIsRead = false 
    def hasNext = !(aIsRead && bIsRead && cIsRead) 
    def next = (aIsRead, bIsRead, cIsRead) match { 
     case (false, _, _) => aIsRead = true; a 
     case (_, false, _) => bIsRead = true; b 
     case (_, _, false) => cIsRead = true; c 
     case _ => Iterator.empty.next 
    } 
} 

これは主にTraversableのメソッドと同じように見えるIteratorのすべてのメソッドを、提供します。これらの方法の違いは、ほとんどの場合、Iteratorは1度しか使用できないという事実に関連しています。

最後に、Iterableがあります。 Iterableであるためには、あるクラスは1つのメソッド、iteratorを実装する必要があります。このメソッドは、そのクラスに対してIteratorを返します。例：

class Three[A](a: A, b: A, c: A) extends Iterable[A] { 
    // not necessary, but may offer a more efficient implementation 
    override def foreach[U](f: (A) => U) {  
     f(a); f(b); f(c) 
    } 

    def iterator = new Iterator[A] { 
     private var aReady, bIsRead, cIsRead = false 

     def hasNext = !(aIsRead && bIsRead && cIsRead) 
     def next = (aIsRead, bIsRead, cIsRead) match { 
      case (false, _, _) => aIsRead = true; a 
      case (_, false, _) => bIsRead = true; b 
      case (_, _, false) => cIsRead = true; c 
      case _ => Iterator.empty.next 
     } 
    } 
} 

質問に戻るには、期待される動作が何であり、どのようにしたいかを考慮する必要があります。特に、Scalaコレクションには「下」と「左」という概念はありません。つまり、NodeはScalaコレクションを返すメソッドを持つことができますが、はになります。Rex Kerrの解説を参照してください。

EDIT私はレックスカーのとは別の例を挙げましょう。ここではTraversableNodeを実行し、トラバーサルの順番を選択できます。

class Node[A] extends Traversable[A] { 
    var left: Node[A] = _ 
    var down: Node[A] = _ 
    var traverseLeft = true 
    var value: A = _ 

    def foreach[U](f: (A) => U) = if (traverseLeft) foreachLeft(f) else foreachDown(f) 

    def foreachLeft[U](f: (A) => U) { f(value); if (left != null) left.foreachLeft(f) } 
    def foreachDown[U](f: (A) => U) { f(value); if (down != null) down.foreachDown(f) } 
} 

だから、これNodeはTraversableで、（それはまだなど、mapからNodeを返さないでしょうが - これについて他の質問を見て）それはTraversableすべてのメソッドをサポートしています。フラグ（traverseLeft）で左または下を走査するかどうかを選択でき、すべての通常のTraversableメソッドは、メソッドが呼び出されたノードに設定されているものを使用します。

しかし、これは良いモデルではありません。私はむしろRex Kerrのイテレータを左下に返すか、Scalaコレクションを完全に残して、Kiamaで処理されたものと一緒に行くRex Kerrのソリューションに行きたいと思います。後者はまったく別のパラダイムですが、Scalaに変換されたコードに慣れ親しんでいるものではありません。