Scala deconstruct, then restore Iterable

Question

I'm currently working on implementing my own Trie in Scala (for learning / hobbies), and I'm trying to keep it universal (so that it can store something Iterable, not just strings). My class signature looks like

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

I already have + = and - = implemented (it extends the mutable version of Set), but I am having problems with the iterator. My current approach made me scratch my head, looking for a graceful realization. I have a way to iterate over all TrieNodes and select only those marked as "real end". From there, I plan to keep track of the parent links to get the individual parts. (for example, "hello" in the tree will be stored as an "o" node, marked as ending, with the parent "l" → "l" → "e" → "h")

Now my problem. Since I am trying to preserve common things, I have no way to restore the “Item” from its “parts”. So my question for people from SO is the most elegant way to handle this? Should I add a reconstruction function to the constructor arguments? Does an Item need to be constrained in different ways to ensure the presence of a function? Or is it completely different?

Answer 1

The relationship between Item and Part is implied. At a minimum, you need to decompose the object into Part objects, and to restore you need to do the opposite.

Therefore, assuming "hello": String , you need to have f("hello") return ('h': Char, "ello": String) , and you need the inverse function g('h', "ello") return "hello" .

Thus, any two types with two such functions will be executed as long as some rules are followed. I think the rules are easy to understand. This is more or less how you decompose a list recursively with head and tail and rebuild it with ::

You can use the associated context to provide these functions for a regular type.

(edit)

Actually, I cannot use the context because there are two type parameters, but this is what I had in mind:

 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) ) } 

Then we provide some implicit objects:

 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𝄞