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