再帰とループについて
the interviews のサービスが終わると言うことで、投稿内容をスクレープするスクリプトをscalaで書きました。
そこで、再帰とループについて考えてみました。
関数型言語ではループは再帰で表現した方がよいと言うことになっているのですが、ループインデックスへの再代入を避けるための苦し紛れとしか思えません。
そこで、スクリプトの関数型バージョンと手続き型バージョンを見比べて見たいと思います。
関数型バージョン
val name = "tamanoir" val url_base = "http://theinterviews.jp/" + name + "/page/" type TheList = List[net.htmlparser.jericho.Element]; @tailrec def ScrapeRecur(count: Int, ls: TheList): TheList = { Thread.sleep(1000) val url = if (count == 1) url_base else url_base + count.toString val str = scala.io.Source.fromURL(url).mkString val s = new net.htmlparser.jericho.Source(str) val body = s.getAllElements(HTMLElementName.BODY) if (body.isEmpty()) ls else { val res = body.get(0).getAllElements(HTMLElementName.DIV).filter { e => { val attr = e.getAttributeValue("class") attr != null && (attr == "title" || attr == "note") } } if (res.isEmpty()) ls else ScrapeRecur(count + 1, ls ::: (res.toList)) } } val results = ScrapeRecur(1, List()) val html_txt = "<html xmlns=\"http://www.w3.org/1999/xhtml\" lang=\"ja\" xml:lang=\"ja\">" + "<head><title>" + name + "</title>" + "<meta http-equiv=\"Content-Type\" content=\"text/html;" + " charset=UTF-8\" /></head><body>" + results.mkString + "</body></html>"
手続き型バージョン
val name = "tamanoir" val url_base = "http://theinterviews.jp/" + name + "/page/" val results = ListBuffer[net.htmlparser.jericho.Element](); // ミュータブルリスト var cont = true // ミュータブル var count = 1 // ミュータブル while (cont) { Thread.sleep(1000) cont = false val url = if (count == 1) url_base else url_base + count.toString val str = scala.io.Source.fromURL(url).mkString val s = new net.htmlparser.jericho.Source(str) val body = s.getAllElements(HTMLElementName.BODY) if (!body.isEmpty()) { body.get(0).getAllElements(HTMLElementName.DIV).filter { e => { val attr = e.getAttributeValue("class") attr != null && (attr == "title" || attr == "note") } }.foreach(e2 => { results += e2; cont = true }) } count += 1 } val html_txt = "<html xmlns=\"http://www.w3.org/1999/xhtml\" lang=\"ja\" xml:lang=\"ja\">" + "<head><title>" + name + "</title>" + "<meta http-equiv=\"Content-Type\" content=\"text/html;" + " charset=UTF-8\" /></head><body>" + results.mkString + "</body></html>"
これは小説家の佐藤亜紀 http://theinterviews.jp/tamanoir の投稿内容を収拾するスクリプトです。
このサイトはよくあるようにPaginateされています。
そこで、ページごとにcollectする必要があり、それぞれのページに複数のエントリがあります。わりと終了条件のわかりづらい二重ループです。
ここで、内ループの一つのページに含まれるエントリを収拾するのは簡単で、いずれの例でも1行の関数型アプローチ(body.get(0).getAllElements(HTMLElementName.DIV).filter 〜〜)で済ませています。
問題は外ループの終了条件です。内ループが空振りに終わったら、外ループも終了するようになっています。関数型アプローチでは再帰を抜けるようにして、手続き型アプローチではwhileを止めます。
また、収拾したエントリの扱いも異なります。
関数型アプローチでは、関数型の作法に従ってイミュータブルリストを連結して新しいイミュータブルリストを作成しています。
手続き型アプローチではミュータブルリストにpush_backするおなじみの方法を採っています。
意外と両バージョンの行数はほとんど同じです。
これ、どっちの方が書きやすくて可読性が良いかといえば、手続き型バージョンだと思うんですよね。
ページをめくって読んでいく流れがそのままコードに落としてあるからです。
そして、内ループの流れも関数型っぽく書いてはいますが、foreach内でpush_backしているので、手続き脳の人にも理解しやすいと思います。
それに引き替え、関数型バージョンは内ループで作成されるリストを検証するステップを追加する必要があり煩雑です。末尾再帰最適化が働くようにするようにするにも一手間かかりました。
Scalaの場合は、再帰関数をdefするときにリストの型( List[net.htmlparser.jericho.Element] )を明示しないといけないのもイライラ感があります。
Scalaの型推論が不十分だと言う不平不満も理解できます。
どっかの教科書に「再帰によるループの表現はほとんどの場合は自分で書く必要が無いから安心して良い」とか書いてあったように思いますが、逆に、foreach、map、foldなどのお仕着せのループ関数が使えない場合は、手続的に書いた方が良いように思えます。
パフォーマンスもこちらの方が期待できますしね。
というわけで、Haskellのような純粋な言語よりは、関数型のおいしいところだけをつまみ食いできるScalaの方が私の好みに合います。
マルチパラダイム万歳と言うことで。