Edited at

木構造と再帰の話

More than 1 year has passed since last update.

platform os version の3つの属性を持つ型Deviseの配列があります。

Device = Struct.new(:platform, :os, :version)

devices = [
Device.new(:pc, :windows, 7),
Device.new(:pc, :windows, 10),
Device.new(:pc, :macos, :el_capitan),
Device.new(:pc, :macos, :sierra),
Device.new(:pc, :ubuntu, 16.10),
Device.new(:smartphone, :ios, 8),
Device.new(:smartphone, :ios, 9),
Device.new(:smartphone, :android, 6.0),
Device.new(:smartphone, :android, 7.0),
Device.new(:smartphone, :android, 7.1), ]

この配列から、指定した属性の順序でグルーピングした木構造のHashを生成する関数def grouping(arr, *keys) を作りたい。

たとえば、 platform, os の順序でグルーピングすると、以下のような出力を期待します。

{

pc: {
windows: [
Device.new(:pc, :windows, 7),
Device.new(:pc, :windows, 10),
[,
macos: [
Device.new(:pc, :macos, :el_capitan),
Device.new(:pc, :macos, :sierra),
[,
ubuntu: [
Device.new(:pc, :ubuntu, 16.10),
],
}
smartphone: {
ios: [
Device.new(:smartphone, :ios, 8),
Device.new(:smartphone, :ios, 9),
],
android: [
Device.new(:smartphone, :android, 6.0),
Device.new(:smartphone, :android, 7.0),
Device.new(:smartphone, :android, 7.1),
]
}
}

これを、再帰を使ってこんなふうに書きました。

def grouping(arr, *keys)

return arr if keys.nil? || keys.empty?
return {} if arr.nil?

head, *tail = keys

arr.group_by(&head).transform_values{|xs|
grouping(xs, *tail)
}
end

グルーピング順の配列keysを先頭から取り出しながら再帰し、keysが空になった場合を停止条件としました。

木構造をやLinked Listを生成したりトラバースしたりするときに、再帰は大きな威力を発揮します。

Rubyだと、group_bytransform_values などの便利なメソッドが用意されているので、非常にあっさりと書けますね。

みなさんの得意な言語ならどんなふうに書きますか?