Runner in the High

技術のことをかくこころみ

ElmでPromise.all的なことをしたいときに便利なelm-task-parallel

github.com

背景

JavaScriptだと「起動時にサーバーへA, B, Cのデータの取得を問い合わせて全てデータがそろったら次の処理へ移る」というような実装をPromise.allで作ることがよくある。

これをElmで雑にやろうとすると以下のようなMaybeまみれのコードが生まれたりする。

-- Maybeでデータがロードされいているかいないかを表現している。
-- すべてJustになったら次の処理をする。

type alias Model =
    { user : Maybe User
    , posts : Maybe Posts
    , favorites : Maybe Favorites
    }

こうなるとupdate関数の中でデータを取り出すたびに毎度パターンマッチをしなければいけなくなり、とても冗長なコードになってしまう。また、毎回すべてのデータがJustかどうかをチェックしないといけなくなったりする。これは事故る可能性も高い。

可能であれば「全てのデータがそろっている/いない」を型で表現できるのが理想である。

elm-task-parallelを使う

ここでelm-task-parallelが使える。

まずはModelをこんな感じで設計する。この時点でひとつもMaybeが出てこない。

type Model
    = Failed
    | Loading (Task.Parallel.State3 User Posts Favorites)
    | Loaded User Posts Favorites

Loadingはデータをロード中であることを表現している。同時に取得したいデータの型の数に合わせて、使うStateN型を変更する。ここでは3つのデータを取得待ちするのでState3を使っている。

上のModelが用意できたので、取得の開始を行うinit関数を実装する。attemptNという関数が公開されているので、同時に実行したいTaskの数に応じて数字を変えて呼び出す。最大で5個のタスクまで扱うことができる。

init : () -> ( Model, Cmd Msg )
init _ =
    Task.Parallel.attempt3 
        LoadingUpdated 
        Api.fetchUser 
        Api.fetchPosts 
        Api.fetchFavorites 
        |> Tuple.mapFirst Loading

続いてMsg型を以下のように実装する。

type Msg
    = LoadingUpdated (Msg3 Http.Error User Posts Favorites)
    | LoadingFailed Http.Error
    | LoadingFinished User Posts Favorites

上記のMsg型を踏まえてupdate関数を以下のように作る。

update : Msg -> Model -> ( Model, Cmd Msg )
udpate msg model =
    case model of
        Loading loadingState ->
            case msg of
                LoadingUpdated loadingMsg ->
                    Task.parallel.update3 
                        loadingState 
                        loadingMsg 
                        LoadingFinished 
                        LoadingFailed
                        |> Tuple.mapFirst Loading

                LoaadingFailed _ ->
                    ( Failed, Cmd.none )

                LoadingFinished user posts favorites ->
                    ( Loaded user posts favorites )

         _ ->
             ( model, Cmd.none )

LoadingUpdatedバリアントは、最初に一気に実行されたTaskの結果を受け取るたびに呼び出され、Loadingバリアントが持つデータを逐次更新していく。パッケージを使う側である我々は、いまどのデータが揃っているのかを気にする必要はない。

最後にLoadedFinishedバリアントが飛んでくれば、ModelをLoadedに更新するために必要なデータが全部揃う、という流れである。これでもうMaybe型を登場させる必要はない。

内部の実装はどうなっているのか

読んでみると分かるがそんなに難しいことはしていない。

例えば、3つのデータを持つState3型はこんな感じの実装になっている。

type State3 a b c
    = FailedState3
    | State3 (Maybe a) (Maybe b) (Maybe c)

つまりパッケージの実装でMaybeを隠してくれているという感じである。

あとはupdateN関数の中で、失敗状態(FailedStateN)になっていない限り、ひとつづつMaybe型のデータが更新されていく、という流れになっている。

update3 : State3 a b c -> Msg3 x a b c -> (a -> b -> c -> msg) -> (x -> msg) -> ( State3 a b c, Cmd msg )
update3 prevData msg successMsg failureMsg =
    case prevData of
        FailedState3 ->
            ( prevData, Cmd.none )

        State3 a b c ->
            case msg of
                LoadedA3 data ->
                    nextCmd3 (Just data) b c successMsg

                LoadedB3 data ->
                    nextCmd3 a (Just data) c successMsg

                LoadedC3 data ->
                    nextCmd3 a b (Just data) successMsg

                FailedToLoad3 err ->
                    ( FailedState3, failureMsg err |> toCmd )

Scalaにおける無名クラスのメソッド呼び出しはリフレクションが使われる

こんなコードを書いた。

val App = new {
  def say = println("hello")
}

App.say

コレ自体実行はできるが、以下の警告がでる。

reflective access of structural type member method say should be enabled
by making the implicit value scala.language.reflectiveCalls visible.
----
This can be achieved by adding the import clause 'import scala.language.reflectiveCalls'
or by setting the compiler option -language:reflectiveCalls.
See the Scaladoc for value scala.language.reflectiveCalls for a discussion
why the feature should be explicitly enabled.

Scalaでは無名クラスにおけるメソッド呼び出しはランタイムリフレクションが使われるからである。

任意のトレイトを実装したクラスをワンショットで作りたい、などの用途では使われるケースが考えられるが、パフォーマンスや型安全性のことを考えると避けるほうが良いのかもしれない。

Scalaでは無名関数は型パラメータをとれない

こんなコードを書いた

object App {
  type Value[A] = Seq[(A, A)]
  
  sealed trait Status {
    def map[A](f: Value[A] => Value[A]) =
      this match {
        case Valid(value) => Valid(f(value))
        case Invalid() => Invalid()
      }
  }
  
  case class Valid[A](value: Value[A]) extends Status
  case class Invalid() extends Status
}

このコードをコンパイルすると、7行目の関数引数fを適用する部分で以下のエラーになる。

type mismatch;
 found   : Playground.App.Value[Any]
    (which expands to)  Seq[(Any, Any)]
 required: Playground.App.Value[A]
    (which expands to)  Seq[(A, A)]

これはパターンマッチにおけるValid型のAの型が決まらないからなので、mapメソッドが所属しているStatusトレイトそのものをStatus[A]みたいな形でジェネリックにすれば解決する。

一方で「なぜ無名関数をジェネリックにできないのか」は少しおもしろいトピックだと思う。これに関しては、このStackoverflowの回答でScalaの言語仕様と共に詳しく説明されていた。 stackoverflow.com

つまり、無名関数がジェネリックになれない(型パラメータをとれない)のは「メソッド」と「関数」の違いに由来するもの。

Scalaにおいてメソッドはジェネリックになれるが、関数は内部ではFunctionNとして表現されるため定義時点で型が決まりジェネリックにはなれない。したがって、無名関数もジェネリックになれないということのようだ。

「じゃあ他の言語はどうなんだ」というハナシになるが、例えばTypeScriptだと無名関数もこんな感じでジェネリックにできる。

const foo = <T>(x: T) => x;

人の作ったWebアプリケーションのコードを見るときに注目しているところ

普段見ているものをなんとなく書き出してみた。

インターフェイス

あえてやってないとか、レイヤ的にやる必要がないというケースもある。しかし、ある程度の規模のソフトウェアには大抵インターフェイスが現れる。インターフェイスがないコードはユニットテストもないことが多い。したがって、インターフェイスが現れないコードは責務分離が行われてない可能性を感じたりする。

言語機能上インターフェイスがない動的型付け言語の場合には、ダックタイピングを意識したコードが書かれているかをチェックする。ダックタイピングでなくとも、例えばRubyだったら抽象クラスと実装クラスの分離が行われているかを見たりする。

バリデーションロジック

すべてのバリデーションが、フレームワークの機能で実装されてたりしないかをチェックする。MVCとかクリーンアーキテクチャ的な実装であれば、それぞれのレイヤでどういうバリデーションをしているのかを覗いてみる。コントローラで全部のバリデーションが行われているときもある。

また、バリデーションエラーをどうハンドリングしているかも確認する。DBエラーをそのままプレゼンター層に返していたり、ドメイン層に外部レイヤの言葉とかデータが出てくると「オッ」となったりする。

トランザクション

トランザクションをどの範囲で貼っているのかをチェックする。そもそもトランザクションが貼られていないときは、なんらかの理由があるかを調べてみる。トランザクションの実装がドメインからどれくらい分離できているかを見てみる。

トランザクションが貼られている部分に対するリクエストのトラフィックを見てみる。なぜそのトランザクションが結果整合じゃないのかを考えてみる。

Userクラス

大体、どんなアプリケーションでもUserみたいな名前のクラスが存在する。とりあえずおもむろにそれを覗いてみる。1000行とかあったりすることもあるので、そのときはまず深呼吸する。もしかしたら本当にそれだけ長くなる理由があるのかもしれない。

Userが薄い場合にはUserを継承してそうなクラスを探してみる。薄すぎるな〜と思ったときには、Userの実装をもとに値オブジェクト的なものを探してみる。あったら実装を読んでみる。どういうクラス設計になっているか覗いてみる。

POXO

これは極めて強引な意見だが、できのいいソフトウェアは大体POXO*1がちゃんと作られている。RubyならPOROだし、JavaならPOJOになる。特に、ドメインにあたるレイヤのコードがPOXOじゃないときは、その理由を探ってみる。

すべてのクラスが何かを継承していたり、なにかに依存している場合には「なんでだろう?」を考えてみたりする。

〇〇サービス

ディレクトリ構造を全部展開してHogeServiceみたいなのがないか探してみる。するとだいたい見つかるので、ゆっくりその中身を読んでみる。

ステートフルなのか、ステートレスなのか。ドメインサービスなのか、アプリケーションサービスなのか判断を試みる。どっちでもなさそうな場合には、なんらかのドメインに所属させれないか考えてみたりする。

〇〇リポジトリ

とりあえずDDDのリポジトリを期待して中身を覗いてみる。インターフェイスであることを期待しているところ、いきなりSQL文が現れたりすることもある。

インターフェイスになっている場合には、どこまで永続化装置を抽象化できているか見てみる。追加と削除のインターフェイスだけになっていたらかなり驚く。満足したらどこでDIしているのかを探してみる。フレームワークの機構を使っているのか、シンプルなコンストラクタDIなのかをチェックする。

レイヤごとの実装

MVCであればそれぞれにどういうコードが書かれているのかを見てみる。Mの中に永続化装置やプレゼンター実装の具体的な単語が出てくると「オッ」となる。クリーンアーキテクチャであればFlow of Controlをどう作っているか、アダプタ実装ごとのプラガビリティがインターフェイスでどれだけ抽象化できているか、をじっくり眺めてみる。

静的型付言語であれば、型を使ってドメインをどれくらい守れているかを見てみる。

*1:Plain-Old-Xxx-Objectの略。Xxxには任意のプログラミング言語の名前が入る。

ElmでBrowser.elementを使いつつルーティングを自前で作る

一般的にElmでルーティングを行うSPAを作る場合にはBrowser.applicationを使って、組み込みのルーティングの機構を使うことになる*1。しかし、一方でルーティングの仕組みを持たないBrower.elementBrowser.documentでも、ルーティングをJavaScriptサイドで自前実装する方法がある。

elementを使いつつルーティングを自作したいユースケースとして、ReactやVue.jsと統合してElmを使いたいケースが挙げられる。applicationやdocumentを使うと特定のDOMのみにElmアプリケーションをマウントすることができないため、他のフレームワークと共存させることができない。

なお、elm/browserリポジトリにも「Browser.elementでルーティングをするにはどうすればよいか」を説明した詳しいドキュメントがある。 github.com

実装してみる

さて、ではどんな感じでルーティング部分を自作するか。この記事では楽をするべくルーティングの実装にnanorouterhistoryを使う。

nanorouterはURLのマッチング機構だけをもつ小さなルーティングモジュールである。これを使えばURLのパスやパラメタのパーサをわざわざ正規表現で作る必要がなくなる。また、イベントエミッタ的なインタフェースをしているのでElmのPortがもつPub/Sub的な雰囲気との相性がよい。

historyは言わずとしれたHistory APIの抽象化ライブラリ。これを使っておけばブラウザ間の差異だとかそういうのを気にしなくていい。

ここから紹介する実際のコードは以下のギッハブリポジトリに置いてある。 github.com

index.js

基本的にパスの変更が起きた場合に、JSサイドでは変更をPort経由でElmアプリケーションへ送信したり、Elmアプリケーションから受け取ったパスを用いてhistoryで遷移を実行したりするだけである。

import { Elm } from "./App.elm"
import { createBrowserHistory } from 'history'

const history = createBrowserHistory()
const app = Elm.App.init({ 
  flags: history.location.pathname,
  node: document.querySelector('main'),
})

history.listen((location, _) => {
  app.ports.onUrlChanged.send(location.pathname)
})

app.ports.replaceInternal.subscribe(path => {
  history.push(path)
})

Route.elm

ルーティングに関連するロジックを凝集したのが、このRouteモジュールになる。

port module Route exposing
    ( Route(..)
    , decode
    , link
    , replace
    )

import Html exposing (Html, a, text)
import Html.Attributes exposing (href)
import Html.Events as Events
import Json.Decode as Decode


type Route
    = Top
    | PageA
    | PageB


decode : Decode.Value -> Route
decode value =
    value
        |> Decode.decodeValue decoder
        |> Result.withDefault Top


link : msg -> String -> Html msg
link msg label =
    a [ href "#", onClick msg ] [ text label ]


replace : Route -> Cmd msg
replace route =
    replaceInternal (routeToString route)

内部関数であるonClicklink関数の中で使っている。これはaタグで画面遷移の発火をブロックするためのカスタムのonClickイベントである。これがないとブラウザのロードが走ってしまう。

stringToRouterouteToStringはRoute型と文字列のパスを突合するためのマッピング関数である。JavaScript側とPortを介して文字列でパス情報がやりとりされるため、このようなマッピングを行う関数が必要になる。

replaceInternalを公開関数にしていないのは、直接文字列を受け取れてしまうのを避けるためである。あえてreplace関数でラップして、引数にRoute型を受け取るようにすることで、ルーティングの組み合わせが型から判別できる。文字列だとなんでも指定できる分、使う側からすると前提がなくて難しい。パスにスラッシュがつくのかどうか、なども気にしてなくてはいけなくなる。

-- Internals


onClick : msg -> Html.Attribute msg
onClick msg =
    Events.custom "click"
        (Decode.succeed
            { message = msg
            , stopPropagation = True
            , preventDefault = True
            }
        )


stringToRoute : String -> Decode.Decoder Route
stringToRoute value =
    case value of
        "/pageA" ->
            Decode.succeed PageA

        "/pageB" ->
            Decode.succeed PageB

        _ ->
            Decode.succeed Top


routeToString : Route -> String
routeToString route =
    case route of
        Top ->
            "/"

        PageA ->
            "/pageA"

        PageB ->
            "/pageB"


decoder : Decode.Decoder Route
decoder =
    Decode.string |> Decode.andThen stringToRoute


port replaceInternal : String -> Cmd msg

App.elm

initialModel関数ではFlagの値をValue型で受け取り、初期のRoute型のデータを計算する。計算されたRoute型のデータをchangeRouteTo関数に食わせることで、最初のModelが生成される。

基本的には画面遷移は、このModel計算の流れを繰り返すことになる。

port module App exposing (main)

import Browser
import Html exposing (Html, div, text)
import Json.Decode as Decode
import Pages.A as PageA
import Pages.B as PageB
import Route



-- model


type Model
    = Top
    | PageA PageA.Model
    | PageB PageB.Model


initialModel : Decode.Value -> ( Model, Cmd Msg )
initialModel flag =
    ( changeRouteTo (Route.decode flag), Cmd.none )


changeRouteTo : Route.Route -> Model
changeRouteTo route =
    case route of
        Route.Top ->
            Top

        Route.PageA ->
            PageA PageA.init

        Route.PageB ->
            PageB PageB.init

Msg型のバリアントふたつはほとんどBrowser.applicationで使うものと近い。

-- update


type Msg
    = URLChanged Decode.Value
    | ChangeURL Route.Route


update : Msg -> Model -> ( Model, Cmd Msg )
update msg model =
    case msg of
        URLChanged nextRoute ->
            ( changeRouteTo (Route.decode nextRoute), Cmd.none )

        ChangeURL route ->
            ( model, Route.replace route )

上で定義されているURLChangedはインバウンドなPortの受けメッセージになる。ここはFlagと同じでValue型で受け取る。

受け取ったValue型のデータをデコードしてそこからModel型をつくる流れはinitialModel関数とほぼ同じであることがわかる。

-- port


subscriptions : Model -> Sub Msg
subscriptions _ =
    onUrlChanged URLChanged


port onUrlChanged : (Decode.Value -> msg) -> Sub msg

画面遷移のリンクはRouteモジュールで定義したlink関数で作ることができる。

-- view


view : Model -> Html Msg
view model =
    case model of
        Top ->
            div []
                [ text "This is Top"
                , div [] [ Route.link (ChangeURL Route.PageA) "PageA" ]
                , div [] [ Route.link (ChangeURL Route.PageB) "PageB" ]
                ]

        PageA pageModel ->
            PageA.view pageModel

        PageB pageModel ->
            PageB.view pageModel

あえてBrowser.elementを使って自分でElmアプリケーションのルーティングを作ってみると「SPAにおけるルーティングとはなんぞや」というものがすごくクリアに見えてくる。これはReactだろうがVue.jsだろうが同じである。

ルーティングはアプリケーションに対するブラウザからの入力であり、アプリケーションからブラウザに対する出力という副作用である。Elmアプリケーションは、外部から受け取ったデータをもとにModelを都度計算するというひとつの関数のように振る舞う。こういう分かりが生じてくるのが、関数型プログラミングのおもしろさだ。

*1:Browserモジュールが提供している初期化関数の種類に関してはJinjorさんのQiitaの記事が詳しい https://qiita.com/jinjor/items/245959d2da710eda18fa

Elmアプリケーションにおける多言語対応パターン

特段テクい話ではないが最近話す機会があったのでこちらでもメモ。

まず、以下のように対応している言語のパターンを表現した型を全画面共通で使える型として用意しておく。

type Lang 
    = Ja 
    | En

あとは各ページごとに画面で表示するラベルのインターフェイスとなるレコード型を用意しておき、言語別に出し分ける関数を作る。 これをview関数の中で呼び出せばよい。 非常にシンプル。

type alias Phrases = 
    { title : String
    , cancel : String
    , submit : String
    } 


toPhrases : Lang -> Phrases
toPhrases lang =
    case lang of
        Ja ->
            { title = "タイトル"
            , cancel = "キャンセル"
            , submit = "提出"
            }

        En ->
            { title = "Title"
            , cancel = "Cancel"
            , submit = "Submit"
            }

最後に言っておくと、Languageモジュールみたいな日英の多言語情報をまとめたぶっこみモジュールを作るのは強くオススメしない。 共通で使う文言ならまだしも、ある画面でしか使っていない文言を全部ひとつにまとめたくなった場合には、本当にまとめる意味があるのか考えるべきだ。

というわけで、画面モジュールごとに上で言うところのPhrasestoPhrasesをペアで用意するのがよい。

SCIMなどの外部連携インターフェイスがアプリケーションの仕様を侵食する件

今回はちょっとエンタープライズなハナシ。

そもそもSCIMってなに

このQiitaの記事が詳しい。
要はマスターデータを連携するためのWebAPIのインターフェイスの規格的なもの。 qiita.com

SCIMインターフェイスはつらい

B2Bのプロダクトだとマスターデータの連携を行う目的でSCIMインターフェイスの口を提供するケースがあるが、SCIMはビジネスルールを侵食する

まずSCIMにはスキーマとして次の仕様があるが、SCIMインターフェイスを実装するアプリケーションは基本的にスキーマごとの仕様を実装することがほぼ必須になる。

  • Groupスキーマの仕様
    • Groupの階層化(あるGroupが子となるGroupを複数持つことができる)
    • Userの所属(Groupに複数のUserが所属できる)
  • Userスキーマの仕様
    • 物理/論理削除

「必須になる」と書いているのは、アプリケーションはスキーマ単位で取捨選択はできるが、スキーマにおける仕様を取捨選択することはできないからである。たとえばGroupスキーマをサポートしながら、Userの所属のみを採用し、Groupの階層化をサポートしない、というのはほぼ不可能*1になる。

実際のAzureADでのケースを挙げると、AzureDAサイドでグループの階層化が行われている場合には、SCIMのグループ更新のリクエストに階層化されたグループの情報が乗ってくる。アプリケーション側は階層情報をどこかで必ず保持しなければいけない。リクエストを読み捨ててしまうと、続いて不定期でやってくるAzureADからの永続化チェックのレスポンスを作れないからである。AzureAD側が満足するレスポンスを返せないと、永遠にリクエストが飛んでくることになるし、永続化に失敗しているとみなされればAzureADの場合には「検疫モード」に移行し、連携処理がしばらく止められてしまい顧客に迷惑をかける。

これは、SCIMインターフェイスがアプリケーションから「〇〇の機能は提供していない」みたいなリクエストを受け取る選択肢を提供していないためだ。したがって、SCIMを使うからには常にSCIMのルールに乗らなければいけない。これが「プロダクトのドメインSCIMの仕様に侵食される」と述べた理由である。

たとえばグループ削除のポリシーについて

もっと踏み込んだ話をする。 たとえば、SCIMではグループの削除がインターフェイスとして存在しているため、SCIMをカバーする場合には我々サイドのアプリケーションもグループの削除をサポートせねばならない。

また、SCIMのグループは階層化もサポートしているため、階層化されているグループの削除のポリシーも考えることになる。 簡単に考えても、階層化されているグループを削除する場合には次の4パターンがある。

  1. 親グループが消えたら子グループも消える
  2. 親グループが消えても子は残るがもとの親の親に紐づく(この仕様は子が親をひとつしか持たない場合のみ有効)
  3. 親グループが消えた場合には子は親を持たないグループになる
  4. 子グループを持つ親は削除できないようにする

さて、この4つの選択肢を出したとしてもSCIMでAzureADをサポートする場合にはc以外の選択肢を持つことができない。なぜならAzureADがcだからである! 我々が違う選択をしてくても、SCIMを使っている限りはSCIMに寄り添う以外不可能。そういうことなのである。

もちろんAzureADに対応しないという選択もできるが、シェアを考えると現実的ではない。

どうすればいいのか

自前のWebAPIのみを提供するという選択肢がある。これであれば自分たちで仕様を決められるのでSCIMに引きずられることはない。

しかし自前のWebAPIとなると、今度は顧客側に対応の工数を求めることになり、B2Bサービスなどは受注や導入開始などのリードタイムを長くする可能性がある。 B2Bアプリケーションにおいて「導入の容易さ」は大きな武器であり、ここを犠牲にするのは確実におすすめできない。

SCIMの利点はマスタデータを提供する多くのサービス(Okta, GSuite, AzureAD, etc)が大抵の場合すでにインターフェイスを実装しているため、使う側からすると導入コストがゼロに等しくなるというアドバンテージがある。 ビジネスの観点からするとここには勝てない。

顧客との力関係やその他もろもろの都合が合うのであれば「SCIMなどの外部連携インターフェイスを使わない」という選択肢も検討できるだろうが、本当にそれができるかはまた別問題である。

余談

AzureADとのSCIM対応は仕様を知ったり実装をする点でも実は結構大変... なのだが、それはまた別記事で書こうと思う。

*1:もちろん、バックエンド側でSCIMとの連携情報保持でしか使わないテーブルを用意するだけに留めるというのは可能。しかし、逆に言うと最低限それは絶対にやらなければならない。なにもしないは不可。

Elmでコンシステント・ハッシュ法を扱うパッケージを作って得たモジュール設計の学び

数ヶ月前にElmでコンシステント・ハッシュ法を扱うためのelm-consistent-hashingというモジュールを公開した。

github.com

こんな感じで使える。詳しくはテストを見るといいと思う。

let
    ch =
        ConsistentHashing.new Replica.default (Node.new "node1")
            |> ConsistentHashing.add (Node.new "node2")
            |> ConsistentHashing.add (Node.new "node3")
            |> ConsistentHashing.add (Node.new "node4")

    nextNode =
        ConsistentHashing.getNode (Key.new value) ch
in
-- ...

コンシステント・ハッシュ法についてはWikipedia以外にもこのQiitaの記事も詳しい。

qiita.com

コンシステント・ハッシュ法というと分散システムで使われるイメージが強いので、作った自分もフロントエンドで使い所があるのかは謎だが、いずれElmがサーバーサイドをやれるようになったらきっと広く使われるようになるだろう。

このモジュールは初めての公開モジュールだったが、作るにあたっていくつか工夫した部分がある。

パフォーマンスを考えたコレクション型の選択

Elmはデフォルトのコレクション([]とかで作られるやつ)がList型になっているが、Listは内部では線形リストになっている。

elm-consistent-hashingでも最初はなにも考えずに内部の仮想ノードのコレクションをList型でよしとしてしたが、コンシステント・ハッシング法では次に割り当てるノードを計算する際にソート済みの仮想ノードから検索を行うため、検索は二分探索のほうが効率が良くなる。

仮想ノードは基本的に数が多いので、ここの検索効率はいい感じにしておきたい。 したがってランダムアクセスに優れるArrayに置き換え、内部の実装は以下のようにした。ギリギリ末尾再帰になっていないのがちょっと悲しい。

{-| Looks up the nearest key by recursive Binary Search.
This is way better in performance using linear search with List in case of many keys.
-}
findInternal : Int -> Int -> Maybe Node.Node -> Key.Key -> Keys -> Maybe Node.Node
findInternal beginIndex endIndex currentNode key (Keys keys) =
    if beginIndex > endIndex then
        currentNode

    else
        let
            median =
                beginIndex + (endIndex - beginIndex) // 2
        in
        keys
            |> Array.get median
            |> Maybe.andThen
                (\( medianNode, medianKey ) ->
                    if Key.toString medianKey < Key.toString key then
                        findInternal (median + 1) endIndex (Just medianNode) key (Keys keys)

                    else
                        findInternal beginIndex (median - 1) (Just medianNode) key (Keys keys)
                )

なお、ElmにおけるListとArrayの違いはこのQiitaの記事が詳しい。 qiita.com

Elmの素晴らしいところはListモジュールがそもそも添字アクセスの関数を標準では提供していないところだ。 そもそもListは線形リストだから添字アクセスするものではない、だから添字アクセスしたければArrayを使え、という思想が標準モジュールの設計から伝わってくる。

とはいえ、デフォルトのコレクションがList型なのでArray型を使うには必ずデータを総なめするコストがかかる。 場合によってはこの計算量は無視できないので、敢えてListで添字アクセスをするという選択肢のほうがよい場合もある。 正直、このあたりはアプリケーションやらモジュールの性質によるので一概に答えを出すのは難しい。

たとえばelm-consistent-hashingにおいては、ノードを追加するappend関数内部でノード追加後のソートを実行するためにArray型になっているものを一旦List型に変換し直している。 しかし、モジュールデザインとして「ノードの追加というのはそう頻繁に行われないだろう」と想定して、敢えてノード追加時の計算コストを許容してArrayを採用している。

{-| Internal data structure of Keys is Array, but as an interface, List might be more generic, handy to use.
Plus, `append` is less likely to be called by users, so here probably won't be any performance issue.
-}
append : List ( Node.Node, Key.Key ) -> Keys -> Keys
append keys (Keys currentKeys) =
    keys
        |> (++) (Array.toList currentKeys)
        |> List.sortBy (Key.toString << Tuple.second)
        |> Array.fromList
        |> Keys

non-emptyなインターフェイス

new関数はもともとは初期化時に追加するノードをListで受け取るようなインターフェイスになっていた。

let
    ch =
        ConsistentHashing.new 
            Replica.default 
            [ Node.new "node1"
            , Node.new "node2"
            , Node.new "node3"
            , Node.new "node4"
            ]
in
-- ...

しかし、このインターフェイスでは空のノード配列を初期化時に渡せてしまう。

ノードが存在しない状態をこのようにして作れることは嬉しくない。 なぜなら常にノードが空である場合を常に考慮しないといけなくなるため、必然的にほとんどの操作関数の戻り値をMaybe型にせざるを得なくなってしまう。

したがって、初期化時のnew関数が必ずひとつのノードを取るようにした。

{-| Creates a new ConsistentHashing data
`new` function only takes one initial node at first. This interface is like non-empty list which aims to ensure one node always available at least for distribution.
If you want, you can add some more nodes one by one using `add` function.
-}
new : Replica.Replica -> Node.Node -> ConsistentHashing
new replica initialNode =
    -- ...

こうすることでノードが空でない状態というのが約束できるため、ConsistentHashing型のデータが存在する場合にはノードも必ずひとつは存在することが決まりMaybe型の登場回数を抑えられる。

このような「空でない状態」を表現するには、別の方法として幽霊型をつかう手もある。実際に幽霊型を使って「空でないリスト」を表現する方法は以下のQiitaの記事が詳しい。

qiita.com

一方でノードの削除時にはMaybeを返すようにしている。

{-| Removes a node
This function returns Nothing if all nodes were removed.
`remove` function internally run linear removing of all replicated virtual nodes so that it possibly results in huge computation cost in case you give a big number of Replica.
-}
remove : Node.Node -> ConsistentHashing -> Maybe ConsistentHashing
remove node (ConsistentHashing { replica, nodes, keys, head }) =
    -- ...

最後の一つを残してすべてのノードを削除することができないようなインターフェイスにしてもよかったが、new関数における「常にひとつは生きたノードが存在している」に対して、remove関数でノードを削除する際に「常にひとつのノードが生きている」というのは、なにかしらの大規模な障害が起きるケースではありえないこともあるだろうと考えてMaybeを選んだ。

大事故が起きたときにはすべてのノードがダウンしている可能性もあるし、その場合にはすべてのノードが削除され、割り当てることはできない状態なのでNothingとなる。

モジュール設計の勘所

自分が今回elm-consistent-hashingのインターフェイス設計をする上で意識したのは、ひとりのユーザーとして自分がこのモジュールを使う際にどうなっていたら嬉しいのか、どういうインターフェイスだったらバグを生みにくくできるか、のふたつ。

これは公開モジュールのみならず普段のプロダクト開発においてチームのメンバだけで使うモジュールの設計だとしても同じだし、もはやElmに限った話でもない。 計算量とインターフェイスというふたつの軸がメインだったが、個人的にはいつもこれをかなり意識してモジュールを設計している。

純粋関数型データ構造

純粋関数型データ構造