Elmで再帰的データ構造を扱う

アドカレ記事としてはフライングです。

- [[Elm] Decoder a からいろいろ理解ってしまおう](https://qiita.com/ymtszw/items/1cabbdbda4273b4c1978)

こちらの記事で、ElmのRecordで再帰的データ構造を扱うとき、単純に始めるとうまくいかないことを指摘しました。

# [魔物: 再帰的データ構造](https://qiita.com/ymtszw/items/1cabbdbda4273b4c1978#25-%E9%AD%94%E7%89%A9%E5%86%8D%E5%B8%B0%E7%9A%84%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)の補足

このような再帰的なデータ構造（増田クローンにおける`Post`)を考えています。`Post`には返信先`Post`が存在し、ある程度の階層までAPIで一気に取得できる想定です。

```
{
    "id": "postAbCd0001",
    "created_at": "2017-10-01T15:00:00Z",
    "user_id": "userAbCd0001",
    "subject": "Today I learned...",
    "body": "...utterly nothing.",
    "in_reply_to": {
        "id": "postaBcD0001",
        "created_at": "2017-10-01T14:00:00Z",
        "user_id": "userAbCd0002",
        "subject": "nya-n",
        "body": "nya-n",
        "in_reply_to": {
            "id": "postaaaa0001",
            "created_at": "2017-10-01T13:00:00Z",
            "user_id": "userAbCd0001",
            "subject": "nya-n",
            "body": "nya-n"
        }
    }
}
```

ElmでこのようなJSONを相手にしたいときはどうするか。Recordを定義しますが。。。

> ```elm
type alias Post =
    { id : String
    , created_at : String
    , user_id : String
    , subject : String
    , body : String
    , in_reply_to : Maybe Post -- << !!!
    }
```

> さあ、こいつは成立しているでしょうか？[Ellieで試してみます。](https://ellie-app.com/kTmNYjRSta1/0)

> ALIAS PROBLEM
Line 5, Column 1
This type alias is recursive, forming an infinite type!
When I expand a recursive type alias, it just keeps getting bigger and bigger. So dealiasing results in an infinitely large type! Try this instead:

> ```elm
type Post
    = Post
        { id : String
        , created_at : String
        , user_id : String
        , subject : String
        , body : String
        , in_reply_to : Maybe Post
        }
```
This is kind of a subtle distinction. I suggested the naive fix, but you can often do something a bit nicer. So I would recommend reading more at: https://github.com/elm-lang/elm-compiler/blob/0.18.0/hints/recursive-alias.md

メイン記事の方でも書きましたが、`type alias`は展開されていくわけなので、**どこかにたどり着かないと**こまってしまいます。無限に展開できてしまう型はコンパイルできません。ここでいう「どこか」とは、

```elm
type Something = ...
```

のかたちで定義された何か型です。つまり`type alias`ではだめなのです。終着点になれません。

エラーメッセージには、

```elm
type Post
    = Post
        { id : String
        , created_at : String
        , user_id : String
        , subject : String
        , body : String
        , in_reply_to : Maybe Post
        }
```

という提案がなされています。`Post`というただ一通りの型コンストラクタを持つ`Post`型です。しかしながらこの方式はナイーブすぎて少々微妙です。元々ElmのRecordの機能で`Post`は自動的に

```elm
Post : String -> String -> String -> String -> String -> Post
```

という関数になっていたのが、型コンストラクタになったことで、

```elm
Post : { id : String
       , created_at : String
       , user_id : String
       , subject : String
       , body : String
       , in_reply_to : Maybe Post
       }
     -> Post
```

こういう関数になってしまいました。`Decoder`を組み合わせるワークフローとなじまなくなってしまいます。ApplicativeなDeocder生成もできなくって悔しい。

recursive aliasについてのドキュメントを読むと、こういう提案もされています。

```elm
type alias Post =
    { id : String
    , created_at : String
    , user_id : String
    , subject : String
    , body : String
    , in_reply_to : Maybe InReplyTo -- !!!
    }

type InReplyTo = InReplyTo Post
```

こうするとコンパイルはまず通りますし、難しい部分は"in_reply_to"のdecode部分だけに局所化できて、ベターです。

# 再帰的`Decoder`

ではこれをdecodeしてみましょう。

```elm
import Json.Decode exposing (Decoder, map, map6, field, string, maybe)

postDecoder : Decoder Post
postDecoder =
    map6 Post
        (field "id" string)
        (field "created_at" string)
        (field "user_id" string)
        (field "subject" string)
        (field "body" string)
        (maybe (field "in_reply_to" (map InReplyTo postDecoder)))
```

何しろ`Decoder`はいくらでも組み合わせが効くわけですから、`InReplyTo`型に当てはめる部分だけ`map`で実現してあげれば、あとは`postDecoder`を再帰的に使えば良さそうですよね。

意気揚々コンパイルすると、、、

> BAD RECURSION
Line 19, Column 1
postDecoder is defined directly in terms of itself, causing an infinite loop.

> Maybe you are trying to mutate a variable? Elm does not have mutation, so when I see postDecoder defined in terms of postDecoder, I treat it as a recursive definition. Try giving the new value a new name!

> Maybe you DO want a recursive value? To define postDecoder we need to know what postDecoder is, so let's expand it. Wait, but now we need to know what postDecoder is, so let's expand it... This will keep going infinitely!

> To really learn what is going on and how to fix it, check out: https://github.com/elm-lang/elm-compiler/blob/0.18.0/hints/bad-recursion.md

また怒られた。**Bad Recursion**です。

関数定義に際して、定義内で自分自身に引数を与えて呼び出して使うのは一般的な再帰関数で、当然Elmでも可能です。なのですが、時々うまくいかないケースが有り、再帰データ構造に対する`Decoder`定義はその有名な例です。[Docにもtricky recursionとして説明されています][tricky]。

[tricky]: https://github.com/elm-lang/elm-compiler/blob/0.18.0/hints/bad-recursion.md#tricky-recursion

この問題を解決するために[`lazy`][lazy]という関数が用意されています。Elmコンパイラはこのようなtricky recursionでも、**再帰の中でlambda関数に到達できればコンパイルできるようになっています**。[試してみましょう。][ok]

[lazy]: http://package.elm-lang.org/packages/elm-lang/core/5.1.1/Json-Decode#lazy
[ok]: https://ellie-app.com/qxB8f5hZXa1/0

```elm
import Json.Decode exposing (Decoder, map6, field, string, maybe, lazy)

postDecoder : Decoder Post
postDecoder =
    map6 Post
        (field "id" string)
        (field "created_at" string)
        (field "user_id" string)
        (field "subject" string)
        (field "body" string)
        (maybe (field "in_reply_to" inReplyToDecoder))

inReplyToDecoder : Decoder InReplyTo
inReplyToDecoder =
    map InReplyTo (lazy (\_ -> postDecoder))
```

めでたし。

ついでにいうと、これも[`Parser`の場合][lazyParser]と全く同等です。Elmのバージョンアップによって、このワークアラウンドは不要になるそうです。

[lazyParser]: https://qiita.com/jinjor/items/d0d4b83b530251df913e#%E5%86%8D%E5%B8%B0%E7%9A%84%E3%81%AA%E3%83%91%E3%83%BC%E3%82%B5%E3%83%BC

# おまけ：`maybe`の順序

```elm
maybe (field "in_reply_to" inReplyToDecoder)
```

となっていますが、

```elm
field "in_reply_to" (maybe inReplyToDecoder)
```

ではだめなのでしょうか？

これは、

- "in_reply_to"は常に存在するが、値がdecodeできない(`null`だとかの)ことがある、のか、
- "in_reply_to"自体がないことがある、のか、

という違いを反映しています。

全体に対して`maybe`を適用しているということは、"in_reply_to"の存在自体が"Maybe"であることを示しているわけです。もし"in_reply_to"は常にあるのであれば、`maybe`を適用するのは`inReplyToDecoder`だけでいいでしょう。

微妙な違いですが、APIの仕様をきちんと反映できています。例として書いた増田クローンでは、

```
{
    "id": "postAbCd0001",
    "created_at": "2017-10-01T15:00:00Z",
    "user_id": "userAbCd0001",
    "subject": "Today I learned...",
    "body": "...utterly nothing.",
    "in_reply_to": {
        "id": "postaBcD0001",
        "created_at": "2017-10-01T14:00:00Z",
        "user_id": "userAbCd0002",
        "subject": "nya-n",
        "body": "nya-n",
        "in_reply_to": {
            "id": "postaaaa0001",
            "created_at": "2017-10-01T13:00:00Z",
            "user_id": "userAbCd0001",
            "subject": "nya-n",
            "body": "nya-n"
        }
    }
}
```

3階層目は"in_reply_to"を持っていません。したがって、`maybe`は`field`に適用する必要があったのでした。このようなロジックもまた、`Decoder`という抽象化レベルによって容易に達成できるようになっているのが素晴らしいのです。