P07 Flatten a nested list structure.
自信がついてきたので自分で考えてみたが難しい…。
でも、以下のアルゴリズムでできると思ったので組んでみる。
- 結果格納用のリストを変数で用意し、以下のメソッドをメソッド内で定義する。
- 先頭から1要素取り出す。
- その要素がListならそのListに対して再帰呼び出しする。その後1.の残りのListに対しても再帰呼び出しする。
- その要素がList以外の何かなら、結果格納用リストの末尾にくっつける。その後、1.のListの残りの要素に対して再帰呼び出し。
- その要素がNilならListの終わりなので何もしない。(終了条件)
def myAnswer[A] (ls: List[A]): List[A] = {
var result: List[A] = Nil
def flatten[A] (ls: List[A]): Unit = ls match {
case ls::tail if ls== classOf[List] => {
myAnswer(ls[A])
myAnswer(tail)
}
case h::tail => {
result:+h
myAnswer(tail)
}
case Nil =>
case _ => throw new NoSuchElementException
}
flatten(ls)
result
}
これに対して
scala:scala
myAnswer(List(List(1,1),2,List(3,List(5,8))))
を実行するがエラーになる。
Error:(11, 37) type List takes type parameters
case ls::tail if ls== classOf[List] => {
^
Error:(12, 20) value ls of type A does not take type parameters.
myAnswer(ls[A])
^
「Listは型パラメータを取るよ」…?あっ。
case ls::tail if ls == classOf[List[A]] => {
myAnswer(ls[A])
myAnswer(tail)
}
これで一つ目のエラーは消えた。でも次のやつが全然分からない。
多分そもそも型パラメータが分かってない。
それでもう悩んでもダメだと判断して回答例を見ると
def flatten(ls: List[Any]): List[Any] = ls flatMap {
case ms: List[_] => flatten(ms)
case e => List(e)
}
この問題はそもそも再帰ではなく、flatMapの使い方を練習する問題でした。
flatMapを知らなかったので flatMapをマスターする を参考にしながらお勉強。
ちょっとよく分からないので、エントリを分けます…。
でも今回は、自分が再帰をわかっていないこととflatMapとの出会いがあったので収穫はあったと思い込むことにします。デバッグもできず模範回答も分からずのエントリ。ぐぬぬ…。
次回エントリは「Scalaの再帰が分かった話」とかにしたいですわ…。