スカラはIterableを分解して再構築します

Question

私は現在Scalaで自分自身のTrieを実装しようとしています（学習/趣味目的のため）、一般的なままにしています（Iterableを格納できるように）。私のクラスの署名が

class Trie[Item <% Iterable[Part], Part](items: Item*) extends Set[Item] 

のように見える私はすでに+ =、含まれていると - =実装（それは設定の変更可能なバージョンを拡張するのです）が、私はイテレータを持ついくつかの問題を抱えています。私の現在のアプローチでは、優雅な実装を探して頭を悩ませています。私はすべてのTrieNodesを反復処理し、 "有効な終了"としてマークされているものだけを返す方法を持っています。そこから私は親リンクをたどって個々の部品を得る予定です。 （例えば、ツリー内の「hello」は、「l」→「l」→「e」→「h」の末尾に 'o'ノードとして保存されます）

私の問題。私は物事をジェネリックに保つために、私は "Parts"から "Item"を再構築する方法がない。ですから、SOの人々への私の質問は、これを処理する最も優雅な方法でしょうか？コンストラクタの引数に再構成関数を追加する必要がありますか？ Itemは、関数の存在を強制するために異なる方法でバインドする必要がありますか？それとも全く別のものなのでしょうか？

Answer 1

ItemとPartの間に暗黙の関係があります。最低でもItemをPartオブジェクトに分解し、その逆を行う必要があります。

だから"hello": Stringを取って、あなたはf("hello")リターン('h': Char, "ello": String)を持っている必要があり、あなたが逆関数にg('h', "ello")リターン"hello"を必要としています。

このように2つのタイプの関数は、いくつかのルールが適用される限り、そのように機能します。ルールは直感的に分かりやすいと思います。 headとtailを使って再帰的にリストを分解し、再構築する方法は、::

です。これらの関数を通常の型に提供するには、コンテキストバインドを使用できます。

（編集）

実際には2種類のパラメータがあるので、私は本当にバインドコンテキストを使用することはできませんが、これは私が考えていたものです：

trait R[Item, Part] { 
    def decompose(item: Item): (Part, Item) 
    def recompose(item: Item, part: Part): Item 
    def empty: Item 
} 

class NotATrie[Item, Part](item: Item)(implicit rel: R[Item, Part]) { 
    val brokenUp = { 
    def f(i: Item, acc: List[Part] = Nil): List[Part] = { 
     if (i == rel.empty) acc 
     else { 
     val (head, tail) = rel.decompose(i) 
     f(tail, head :: acc) 
     } 
    } 
    f(item) 
    } 

    def rebuilt = (rel.empty /: brokenUp)((acc, el) => rel.recompose(acc, el)) 
} 

その後、我々はいくつかの暗黙オブジェクトを提供：

implicit object string2R extends R[String, Char] { 
    def decompose(item: String): (Char, String) = (item.head, item.tail) 
    def recompose(item: String, part: Char): String = part + item 
    def empty: String = "" 
} 

implicit object string2RAlt extends R[String, Int] { 
    def decompose(item: String): (Int, String) = { 
    val cp = item.codePointAt(0) 
    val index = Character.charCount(cp) 
    (cp, item.substring(index)) 
    } 
    def recompose(item: String, part: Int): String = 
    new String(Character.toChars(part)) + item 
    def empty: String = "" 
} 

val nat1 = new NotATrie[String, Char]("hello") 
nat1.brokenUp // List(o, l, l, e, h) 
nat1.rebuilt // hello 

val nat2 = new NotATrie[String, Int]("hello\ud834\udd1e") 
nat2.brokenUp // List(119070, 111, 108, 108, 101, 104) 
nat2.rebuilt // hello