10.0.2 breaks a recursive "trie" query

Question

Bug introduced in 10.0.2 and fixed in 10.2

---

The 10.0.2 Dataset type system complication breaks a recursive trie constructor that worked in 0.1:

byPrefix = Query[ 
   GroupBy[First],
   If[First@# == {}, First@Keys@#, byPrefix[#]] &,
   Rest]; 

Test on FDA NDC product dataset ~4k sorted nonproprietary drug names:

drugNames = {"levetiracetam", "prednisone", "lamotrigine", 
    "alprazolam", "amlodipine besylate", "amoxicillin", 
    "diltiazem hydrochloride", "bupropion hydrochloride", 
    "topiramate", "quetiapine fumarate", "carvedilol"} // 
   AssociationMap[{"SOS"}~Join~ Characters[#]~Join ~ {"EOF"} & ] // 
  Dataset

Then,

drugNames[byPrefix]

warns:

Element with head Association is not of the form _String

but the normal form is OK:

drugNames[byPrefix] // Normal

It's not just a warning, it breaks lookup, even though note All Keys are String, not composite as implicated in this 10.0.2 bug:

drugNames[byPrefix]["SOS", Keys] or drugNames[byPrefix]["SOS", "p"] raise msg:

Cannot take part ... of expression of the form _String

while, again, with normal form workaround:

drugNames[byPrefix] // Normal // Dataset // Query["SOS", Keys]

{"l", "p", "a", "d", "b", "t", "q", "c"}

The normal form of an expression should be the same as the normalizing twice. That's violated here.

EDIT // Timing study

Although this question is not about performance, adding a basic benchmark to address comments, which also reveals another consequence of this bug for StringLength > 146:

randomTestWord[len_] :=  
  RandomChoice[
    CharacterRange["a", "z"], {len}] // <|StringJoin[#] -> #|> &;

Using

randomWordData[len_, n_] := 
  Table[randomTestWord[len], {n}] // Association // Dataset;

test along two axes: by array length fixing StringLength = 8

words8Test = 
  Range[100, 1000, 100] // AssociationMap[ randomWordData[8, #] &] // 
   Dataset;

and by StringLength = {2, 4, 8, 16, 32, 64, 128} fixing array length = 100:

words100Test = 
  2^Range[7] // AssociationMap[makeDataset[#, 100] &] // Dataset;

Both look linear in input:

words8Test[All, First @ AbsoluteTiming @ byPrefix[#]&]  
words100Test[All, First @ AbsoluteTiming @ byPrefix[#]&]  

BTW, another aspect of this bug:

randomTestWord[145] // Dataset // Query[byPrefix]  (* ok *)

But longer strings:

randomTestWord[146] // Dataset // Query[byPrefix] // Normal

(* ... <|"m" -> <|"c" -> <|"j" -> <|"b" -> <|"h" -> <|"j" -> <|"b" -> <|"s" \
-> <|"l" -> <|"r" -> <|"i" -> <|"x" -> <|"i" -> <|"k" -> <|"g" -> \
<|"z" -> <|"u" -> 
                    Dataset`Query`PackagePrivate`query[<|\
"elhhqbrjgenygqvgmlnnksmttunqfwbsgfifnhmxhirrybnrziyzodaboabnycxhawjsf\
ydvzrkfokuvekhoofakpatqijqvocuauicuvhgqoliqyhntxyyjuwitbhpdmcjbhjbslri\
xikgzue" -> {"e"}|>]|>|> ... *)

Answer 1

There appears to be a bug in the type inference mechanism here. If you evaluate

<<Dataset`
<<TypeSystem`

and then

res = drugNames[byPrefix];
res // GetType

(* Assoc[Atom[String], Atom[String], AnyLength] *)

which is bogus. Basically that says it thinks the result is an Association with keys and values that are both String. We can compare this to the correct type:

Dataset[Normal[res]] // GetType

(*Assoc[Atom[String], 
 Assoc[Atom[String], 
  Assoc[Atom[String], 
   Assoc[Atom[String], 
    Assoc[Atom[String], 
     Assoc[Atom[String], 
      Assoc[Atom[String], 
       Assoc[Atom[String], 
        Assoc[Atom[String], 
         Assoc[Atom[String], 
          Assoc[Atom[String], Assoc[Atom[String], AnyType, 1], 1], 1],
          1], 1], 1], 1], 1], AnyLength], AnyLength], 8], 1] *)

Perhaps the type inference code isn't quite sure what to do with recursive functions like byPrefix.