こんにちは、エンジニアの澤田です。
普段の業務で、XMLなどから値を取り出して扱う際、データを処理しやすいように一度DBに格納して、DB上でデータを処理することがあるのですが、
XMLなどは階層構造になっているため、取り出したデータも階層構造になることが多く、そのままではDBに格納することが難しくなっています。
(FORCIAでよく使っているPostgresでは配列や階層化された配列を格納できますが、階層化された配列の場合、同一階層の配列は長さが同じでなければならない等の制約があります)
今回は、最近少しずつ勉強しているHaskellを使って、階層化された配列をDBに格納しやすい形に変換してみようと思います！
ここでHaskellを使ってみようと思ったのは、階層化された配列は再帰的な構造をしているため、
再帰が書きやすいHaskellが適していそうだったからです。
※GHC はバージョン8.10.6を使用しています。
1次元リストのリストに展開する
DBに格納しやすい形として、1次元リストが1つのレコードに対応した、1次元リストのリストをイメージしてみました。
例えば、1次元リストの要素を半角カンマ(,) で結合して 1行ずつCSVファイルに出力すれば、DBのインポート機能を使ってそのまま取り込むことができます。
例えば、2階層の配列の展開した場合は以下のようなイメージです。
展開前:
[1, 2, 3, ["aaa", "bbb"]]
展開後:
[
[1, 2, 3, "aaa"],
[1, 2, 3, "bbb"]
]
3階層の場合は組合せのバリエーションが多くなり、以下のように展開されるイメージです。
展開前:
[1, 2, 3, ["aaa", "bbb"], [111, 222, ["foo", "bar", "hoge"]]]
展開後:
[
[1, 2, 3, "aaa", 111, "foo"],
[1, 2, 3, "aaa", 111, "bar"],
[1, 2, 3, "aaa", 111, "hoge"],
[1, 2, 3, "aaa", 222, "foo"],
[1, 2, 3, "aaa", 222, "bar"],
[1, 2, 3, "aaa", 222, "hoge"],
[1, 2, 3, "bbb", 111, "foo"],
[1, 2, 3, "bbb", 111, "bar"],
[1, 2, 3, "bbb", 111, "hoge"],
[1, 2, 3, "bbb", 222, "foo"],
[1, 2, 3, "bbb", 222, "bar"],
[1, 2, 3, "bbb", 222, "hoge"]
]
Haskellのリストで複数の型を要素に持てるようにする
Haskellのリストは同じ型しか要素に持てないため、複数の型の要素を持てるように、基本の型を包む形で独自のデータ型を定義します。
ここで Elm という型を定義し、「数値」「文字列」「空」の 3種類の型を持てるようにしてみました。
data Elm = IntElm Int | StringElm String | EmptyElm deriving (Show)
同様に、単一の要素とリストを同じ型で扱えるようにするための MixedElm という型を定義します。
data MixedElm = SingleElm Elm | NestedElm [MixedElm] deriving (Show)
1次元リストのリストに展開する関数のインターフェースを考える
階層化されたリストを1次元リストのリストに展開する関数とは一体どのようなものでしょうか…？
具体的な実装を考える前に、インターフェースを定義してイメージしやすくしてみます。
※"1次元リストのリスト" という表現は少々回りくどくなっていますが、
横縦の2次元に要素があるリストと区別するためにそのように表現しています
階層化された(ネストされた)リストを展開するというニュアンスで、Postgresでも使われている unnest という名前で関数を定義してみます。
unnest :: [MixedElm] -> [[Elm]]
また、階層化されたリストを受け取って展開するとなると、再帰的に処理する必要がありそうです。
そこで、再帰的な展開処理を行う expandMixedElm という関数を追加して、実際の展開処理をその関数にまかせることにします。
expandMixedElm 関数の第1引数は展開後のリスト、第2引数は展開前の未処理のリストを受け取るイメージです。
再帰的な処理の中で、第2引数のリストの要素を順番に処理して第1引数のリストに移し、全て移し終わったら第1引数の値をそのまま返すようにします。
unnest :: [MixedElm] -> [[Elm]]
unnest [] = [[]] -- 渡されたリストが空だった場合は単一の空リストのリストを返す
unnest xs = expandMixedElm [[]] xs -- expandMixedElm関数に展開処理をまかせる
expandMixedElm :: [[Elm]] -> [MixedElm] -> [[Elm]]
expandMixedElm xs [] = xs -- 全て移し終わったら第1引数の値をそのまま返す
1階層のリストを受け取る
まずは単純な1階層のリストを受け取る場合を考えてみます。
これまで記述した独自データ型の定義も含めると以下のようなコードになります。
data Elm = IntElm Int | StringElm String | EmptyElm deriving (Show)
data MixedElm = SingleElm Elm | NestedElm [MixedElm] deriving (Show)
unnest :: [MixedElm] -> [[Elm]]
unnest [] = [[]]
unnest xs = expandMixedElm [[]] xs
expandMixedElm :: [[Elm]] -> [MixedElm] -> [[Elm]]
expandMixedElm xs [] = xs
expandMixedElm [[]] (SingleElm y:ys) = expandMixedElm [[y]] ys
expandMixedElm xs (SingleElm y:ys) = expandMixedElm (map (\x -> x ++ [y]) xs) ys
上記のコードを unnest.hs というファイル名で保存します。
そして保存したディレクトリで GHCi を起動して、 :l unnest.hs と入力して読み込みます。
期待通りに動作するか見てみましょう！
*Main> unnest [SingleElm (IntElm 1), SingleElm (IntElm 2), SingleElm (IntElm 3)]
[[IntElm 1,IntElm 2,IntElm 3]]
よさそうですね！
階層化されたリストを受け取る
階層化されたリストの場合はちょっと複雑になります。
複雑な要因として、階層化されたリストは単一の要素の場合とリスト、さらにリストのリストが混在する場合があるからです。
そのため、単一の要素かリストかで処理を分けつつ、再帰的な処理を行う必要があります。
いろいろと試行錯誤した結果、第2引数のリストの先頭の要素( NestedElm ys ) のループを処理する中で case式を使って処理を分ける形で実装してみました。
data Elm = IntElm Int | StringElm String | EmptyElm deriving (Show)
data MixedElm = SingleElm Elm | NestedElm [MixedElm] deriving (Show)
unnest :: [MixedElm] -> [[Elm]]
unnest [] = [[]]
unnest xs = expandMixedElm [[]] xs
expandMixedElm :: [[Elm]] -> [MixedElm] -> [[Elm]]
expandMixedElm xs [] = xs
expandMixedElm [[]] (SingleElm y:ys) = expandMixedElm [[y]] ys
expandMixedElm xs (SingleElm y:ys) = expandMixedElm [x ++ [y] | x <- xs] ys
-- 階層化されたリストに対応する
expandMixedElm xs (NestedElm ys:zs) = expandMixedElm (foldl (\acc c -> acc ++ c) [] [foldl (\acc y -> case y of
SingleElm a -> acc ++ [x ++ [a]]
b -> case acc of
[] -> expandMixedElm [[]] [b]
otherwise -> expandMixedElm acc [b]
) [] ys | x <- xs]) zs
上の方で記載した、3階層の場合の例を試してみて、うまく動作するか見てみましょう…！
※実行結果は実際には1行で出力されますが、見やすくするために改行・インデントしています。
*Main> unnest [SingleElm (IntElm 1), SingleElm (IntElm 2), SingleElm (IntElm 3), NestedElm [SingleElm (StringElm "aaa"), SingleElm (StringElm "bbb")], NestedElm [SingleElm (IntElm 111), SingleElm (IntElm 222), NestedElm [SingleElm (StringElm "foo"), SingleElm (StringElm "bar"), SingleElm (StringElm "hoge")]]]
[
[IntElm 1,IntElm 2,IntElm 3,StringElm "aaa",IntElm 111,StringElm "foo"],
[IntElm 1,IntElm 2,IntElm 3,StringElm "aaa",IntElm 111,StringElm "bar"],
[IntElm 1,IntElm 2,IntElm 3,StringElm "aaa",IntElm 111,StringElm "hoge"],
[IntElm 1,IntElm 2,IntElm 3,StringElm "aaa",IntElm 222,StringElm "foo"],
[IntElm 1,IntElm 2,IntElm 3,StringElm "aaa",IntElm 222,StringElm "bar"],
[IntElm 1,IntElm 2,IntElm 3,StringElm "aaa",IntElm 222,StringElm "hoge"],
[IntElm 1,IntElm 2,IntElm 3,StringElm "bbb",IntElm 111,StringElm "foo"],
[IntElm 1,IntElm 2,IntElm 3,StringElm "bbb",IntElm 111,StringElm "bar"],
[IntElm 1,IntElm 2,IntElm 3,StringElm "bbb",IntElm 111,StringElm "hoge"],
[IntElm 1,IntElm 2,IntElm 3,StringElm "bbb",IntElm 222,StringElm "foo"],
[IntElm 1,IntElm 2,IntElm 3,StringElm "bbb",IntElm 222,StringElm "bar"],
[IntElm 1,IntElm 2,IntElm 3,StringElm "bbb",IntElm 222,StringElm "hoge"]
]
きちんと展開できていますね！
さいごに
今回は記事を書くにあたって、階層化されたリストを展開することに焦点をあてて色々と試してみましたが、
その元となる、XMLなどからデータを取り出して階層化されたリストを構成するところまでは辿り着けなかったので
機会があればチャレンジしてみたいと思います！
なお、以下のように Show のインスタンスを定義すると、独自のデータ型の包みの部分を外した形で出力することができます。
instance Show Elm where
show (IntElm x) = show x
show (StringElm x) = show x
show EmptyElm = ""
再度先ほどの関数を実行してみます。
*Main> unnest [SingleElm (IntElm 1), SingleElm (IntElm 2), SingleElm (IntElm 3), NestedElm [SingleElm (StringElm "aaa"), SingleElm (StringElm "bbb")], NestedElm [SingleElm (IntElm 111), SingleElm (IntElm 222), NestedElm [SingleElm (StringElm "foo"), SingleElm (StringElm "bar"), SingleElm (StringElm "hoge")]]]
[
[1,2,3,"aaa",111,"foo"],
[1,2,3,"aaa",111,"bar"],
[1,2,3,"aaa",111,"hoge"],
[1,2,3,"aaa",222,"foo"],
[1,2,3,"aaa",222,"bar"],
[1,2,3,"aaa",222,"hoge"],
[1,2,3,"bbb",111,"foo"],
[1,2,3,"bbb",111,"bar"],
[1,2,3,"bbb",111,"hoge"],
[1,2,3,"bbb",222,"foo"],
[1,2,3,"bbb",222,"bar"],
[1,2,3,"bbb",222,"hoge"]
]
シンプルな形になりましたね！
もう少し変換してファイルに出力すればCSVファイルにもできそうです :)
Discussion