How to do a Hierarchical GroupBy?

Proceed in two steps: first, recursive GroupBy with pruning at the leaves (DeleteCases[{}]) and generating lists-of-rules instead of associations (Normal):

hgb[A_] := Normal@GroupBy[A, First -> Rest, hgb@*DeleteCases[{}]]

Then, at the end apply the function F to the leaves, being careful to delay the application (:>) just in case F needs it:

HierarchicalGroupBy[A_, F_] := hgb[A] /. (x_ -> {}) :> F[x]

Try it out:

expr = {{a}, {a, b}, {a, c}, {a, b, c, d}, {a, b, c, f}, {b, c}, {b, d}};
HierarchicalGroupBy[expr, func]

(*    {a -> {b -> {c -> {func[d], func[f]}}, func[c]},
       b -> {func[c], func[d]}}                           *)

To do the updated example, we can still use the above GroupBy recursion and redefine

HierarchicalGroupBy[A_, F_] := hgb[A] //. {(x_ -> {y_}) -> (x -> y),
                                           (x_ -> {}) :> F[x]}

so that

expr2 = {{a}, {a, b}, {a, b, c, d}, {a, b, c, f}, {a, b, d, e},
         {a, b, e, d, c, f}, {a, c}, {b, c}, {b, d}, {c}};
HierarchicalGroupBy[expr2, func]

(*    {a -> {b -> {c -> {func[d], func[f]}, d -> func[e], 
       e -> d -> c -> func[f]}, func[c]}, b -> {func[c], func[d]},
       func[c]}                                                       *)

A variation on Roman's idea:

ClearAll[hG]
hG = Normal @ GroupBy[# /. {} -> Nothing , First -> Rest,  Function[x, hG[x, #2]]] /. 
     {Rule[a_, {b_}] :> Rule[a, b], Rule[a_, {}] :> #2[a]} &;

hG[expr, func]

{a -> {b -> c -> {func[d], func[f]}, func[c]}, b -> {func[c], func[d]}}

hG[expr2, func]

{a -> {b -> {c -> {func[d], func[f]}, d -> func[e], e -> d -> c -> func[f]}, func[c]}, b -> {func[c], func[d]}, func[c]}

Tags:

Gathering