Haskell で楽しい Web スクレイピング

Haskell で Web スクレイピングしてみたらすごく楽しかったのでご紹介します.

# Scalpel

[Scalpel](https://hackage.haskell.org/package/scalpel) は Haskell のスクレイピングライブラリです.

著名なパーサコンビネータである [parsec](https://hackage.haskell.org/package/parsec) に影響を受けており, 宣言的・モナディックにスクレイピングスクリプトを書くことができます.

本記事では, Scalpel でのスクレイピングの実装例を紹介しながら, **モナディックな記述の裏側, `Alternative`, `MonadPlus` 型クラスを利用した解析器の仕組み** を説明したいと思います.

# スクレイピングしてみる (基本編)

弊社の Qiita AdventCalendar の投稿一覧をスクレイピングしてみましょう.

![Livesense_Advent_Calendar_2015_-_Qiita.png](https://qiita-image-store.s3.amazonaws.com/0/15173/d6383176-0211-2ad6-e806-8a6dcec6d36a.png)

http://qiita.com/advent-calendar/2015/livesense_1

#### スクレイピング結果例

こんな感じの結果を得ようと思います.

```
Just [
  masahixixi: 競馬における脆弱性を追求してみようと思った話~準備編~ (http://qiita.com/masahixixi/items/e6d5eaa3bd6efbf926aa),
  highwide:   Treasure DataとGoogleスプレッドシートで作るお手軽KPIダッシュボード (http://qiita.com/highwide/items/9a75428e8e8bda0325db),
  na-o-ys:    Haskell で Web スクレイピング,
  ...
]
```

## DOM 構造

カレンダーのアイテムは投稿済み/未投稿によって二通りの構造をしています.

#### 投稿済みアイテム

```html
<div class="adventCalendarItem">
  <div class="adventCalendarItem_author">
    {author}
  </div>
  <div class="adventCalendarItem_entry">
    <a href="{url}">
      {title}
    </a>
  </div>
</div>
```

#### 未投稿アイテム

```html
<div class="adventCalendarItem">
  <div class="adventCalendarItem_author">
    {author}
  </div>
  <div class="adventCalendarItem_comment">
    {comment}
  </div>
</div>
```

投稿済みアイテムからは **(author, url, title)** を, 未投稿アイテムからは **(author, comment)** を取得したいと思います.

## スクレイパーの実装

まずはカレンダーのアイテムを表す型 Item を定義します.

```hs
type Author  = String
type Title   = String
type URL     = String
type Comment = String

data Item
    = SubmittedItem   Author Title URL
    | UnsubmittedItem Author Comment
```

DOM 構造に準じて, Item を **(Author, Title, URL)** を持つ **SubmittedItem**, または **(Author, Comment)** を持つ **UnsubmittedItem** で定義します.

続いて, スクレイパー部分を実装します.

```hs
items :: Scraper String [Item]
items = chroots ("div" @: [hasClass "adventCalendarItem"]) item

item :: Scraper String Item
item = submittedItem <|> unsubmittedItem

submittedItem :: Scraper String Item
submittedItem = do
    author <- text        $ "div" @: [hasClass "adventCalendarItem_author"]
    title  <- text        $ "div" @: [hasClass "adventCalendarItem_entry"] // "a"
    url    <- attr "href" $ "div" @: [hasClass "adventCalendarItem_entry"] // "a"
    return $ SubmittedItem author title url

unsubmittedItem :: Scraper String Item
unsubmittedItem = do
    author  <- text $ "div" @: [hasClass "adventCalendarItem_author"]
    comment <- text $ "div" @: [hasClass "adventCalendarItem_comment"]
    return $ UnsubmittedItem author comment
```

使っている関数の簡単な説明です.

<dl>
  <dt>chroots</dt>
  <dd>選択したタグをルートとした DOM ツリーを子スクレイパーに渡す</dd>
  <dt>&lt;|&gt;</dt>
  <dd>2 つのスクレイパーを結合する</dd>
  <dt>texts, attr</dt>
  <dd>選択したタグのインナーテキスト / 属性を取り出す</dd>
</dl>

`items` は `chroots` 関数によって「"adventCalendarItem" クラスを持つ DIV タグ」を全て検索し, それをルートとした DOM ツリーを子スクレイパー `item` に渡します. 
型 `Scraper String [Item]` は 「String をスクレイピングして Item のリストを生成しますよ」 という意味です.

`item` では, 二つのスクレイパー `submittedItem` と `unsubmittedItem` を演算子 `<|>` で結合しています. 
演算子 `A <|> B` によって, **「まず A でスクレイピングし, 失敗したら B でスクレイピングする」** という機能を実現しています.

`submittedItem`, `unsubmittedItem` では, **タグのインナーテキストを取り出す `text` 関数** と, **タグの属性を取り出す `attr` 関数** を使って, ほしい情報を取り出しています.

`Scraper str` は `Monad` のインスタンスなので, 上記のように do 構文でつなぐことができます.

動くコードの全体像はこちらです.
https://gist.github.com/na-o-ys/b491ca3939acefb51a39#file-calendar-hs

# スクレイピングしてみる (発展編)

続いて, AtCoder の提出履歴をスクレイピングしてみましょう. 先ほどの例よりも複雑な処理が必要となります.

<img width="1013" alt="All_submissions_-_AtCoder_Beginner_Contest_031___AtCoder.png" src="https://qiita-image-store.s3.amazonaws.com/0/15173/5b28dc60-2746-7397-00ad-75dd56b23b63.png">

http://abc031.contest.atcoder.jp/submissions/all/1?user_screen_name=na_o_s

#### スクレイピング結果例

```
  AcSubmission {
    createdTime = "2015/11/25 15:38:16 +0000",
    title = "D - 語呂合わせ",
    user = "na_o_ys ",
    language = "C++14 (Clang++ 3.4)",
    score = "100",
    sourceLength = "1400 Byte",
    status = "AC",
    execTime = "35 ms",
    memoryUsage = "932 KB"
  },
  ...,
  FailedSubmission {
    createdTime = "2015/11/25 14:36:25 +0000",
    title = "C - 数列ゲーム",
    user = "na_o_ys ",
    language = "C++14 (Clang++ 3.4)",
    score = "0",
    sourceLength = "1019 Byte",
    status = "WA"
  },
  ...
```

## DOM 構造

カレンダーの例と同じく, Accepted / Failed で二種類の DOM 構造があります.

Accepted に存在する実行時間, メモリ使用量の TD タグが **Failed には存在しません**.

#### Accepted の場合

```html
<tr>
  <td> {投稿日時} </td>
  <td> {問題名} </td>
  <td> {ユーザ名} </td>
  ...
  <td> {状態} </td>
  <td> {実行時間} </td>
  <td> {メモリ使用量} </td>
</tr>
```

#### Failed の場合

```html
<tr>
  <td> {投稿日時} </td>
  <td> {問題名} </td>
  <td> {ユーザ名} </td>
  ...
  <td> {状態} </td>
```

## スクレイパーの実装

DOM 構造に準じて型 `Submission` を定義します. (簡単のために `AcSubmission` は user, execTime (実行時間) を, `FailedSubmission` は user のみを持つものとします.)

```hs
data Submission
    = AcSubmission {
          user     :: String,
          execTime :: String
      }
    | FailedSubmission {
          user     :: String
      }
```

続いて, スクレイパー `submissions`, `submission` を定義します.

```hs
submissions :: Scraper String [Submission]
submissions = chroots "tr" submission

submission :: Scraper String Submission
submission = acSubmission <|> failedSubmission
```

`acSubmission`, `failedSubmission` はどのように実装すれば良いでしょうか. DOM 構造を見ると分かる通り, Accepted/Failed には **TD タグの個数以外に違いがありません**.

Scalpel ライブラリでは attribute の有無について条件付けを行うことはできますが, **選択結果の個数やインナーテキストの内容で条件付けを行う機能は用意されていません**.

自作してみましょう!

先立って型クラス `Alternative`, `MonadPlus` を理解することで, スクレイピングの成功/失敗を自由に制御できるようになります.

## Alternative / MonadPlus

[データ型定義](https://hackage.haskell.org/package/scalpel-0.2.1.1/docs/Text-HTML-Scalpel.html#t:Scraper) にある通り, `Scraper` は型クラス `Alternative`, `MonadPlus` のインスタンスです. これらの型クラスが **スクレイピングの成功/失敗** や **`<|>` によるスクレイパーの結合** を表現する上で本質的な役割を担っています.

### Alternative

`Alternative` 型クラスでは関数 `empty`, `<|>` が提供されます.

```hs
class Applicative f => Alternative f where
  empty :: f a
  (<|>) :: f a -> f a -> f a
```

これらは以下の制約 (laws) を満たすことが要求されます.

```hs
empty <|> x = x
x <|> empty = x
```

このように, 演算子 `<|>` は引数のうち一方が empty であれば他方を返します.

型 Scraper においては, **empty をスクレイピングの失敗とみなす** ことで, 演算子 `A <|> B` によるスクレイパーの結合「まず A でスクレイピングし, 失敗したら B でスクレイピングする」を表現しています.

 参考: [9.4 Other monoidal classes: Alternative, MonadPlus, ArrowPlus | Typeclassopedia](https://wiki.haskell.org/Typeclassopedia#Other_monoidal_classes:_Alternative.2C_MonadPlus.2C_ArrowPlus)

### MonadPlus

"スクレイピングの失敗" の正体が型クラス `Alternative` で提供される `empty` であることが分かりました.

実は `empty` は, Scraper モナドの bind チェイン (という言い方が正しいのか分からないですが) 内で引き継がれるという性質を持っています.
`Scraper` が属するもう一方の型クラス, `MonadPlus` の定義を追うことでその理解が容易になります.

`MonadPlus` 型クラスでは関数 `mzero`, `mplus` が提供されます. 今重要なのは `mzero` です.

```hs
class Monad m => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a
```

`mzero` は次の制約を満たすことが要求されます.

```hs
mzero >>= f  =  mzero
v >> mzero   =  mzero
```

`<|>` の場合とは逆に, `bind` の左右どちらか一方でも `mzero` であれば, 結果は `mzero` になります.

型 Scraper のインスタンス宣言では, `mzero = empty` と[定義されています](https://hackage.haskell.org/package/scalpel-0.2.1.1/docs/src/Text-HTML-Scalpel-Internal-Scrape.html#instance%20MonadPlus%20(Scraper%20str)).
つまりスクレイパーの実装においては, do 構文中の **ある一箇所で `empty` が返っていれば, その他の演算内容に関わらず `empty` が返る** ということが分かります.

## 再び実装

リストの要素数をチェックして, 一致していなければ失敗させる関数 `nItems` を定義してみます.

要素数が合っていれば引数の Scraper をそのまま返し, 違っていれば `empty` を返します.

```hs
nItems :: Int -> Scraper s [a] -> Scraper s [a]
nItems n scraper = do
    items <- scraper
    if length items == n
      then return items
      else empty
```

[関数 `mfilter`](https://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Monad.html#v:mfilter) を使うと `nItems` をよりシンプルに定義できます.

```hs
nItems :: Int -> Scraper s [a] -> Scraper s [a]
nItems n = mfilter ((==n) . length)
```

この関数 `nItems` を使って, スクレイパー `acSubmission`, `failedSubmission` を次のように定義できます.

```hs
acSubmission :: Scraper String Submission
acSubmission = do
    cols <- nItems 10 . texts $ "td"
    return AcSubmission { user = cols !! 2, execTime = cols !! 7 }

failedSubmission :: Scraper String Submission
failedSubmission = do
    cols <- nItems 8 . texts $ "td"
    return FailedSubmission { user = cols !! 2 }
```

`acSubmission`, `failedSubmission` は TD タグがそれぞれぴったり 10 個 / 8 個でなければ `nItems` が `empty` を返すため, スクレイピングに失敗します.

解説したコードの全体像: https://gist.github.com/na-o-ys/b491ca3939acefb51a39#file-atcoder-hs

# まとめ

Haskell / Scalpel を使うことで, 宣言的でシンプル・モナディックなスクレイピングスクリプトを実装できることが分かったと思います.

僕は不勉強ですが, `Alternative` や `MonadPlus` を使って解析器の結合, 成功/失敗を表現するテクニックは, Haskell の代表的なパーサコンビネータである parsec でも駆使されているようです.

みなさんも Web スクレイピングに Haskell を取り入れてみては如何ですか？