読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

Elmでループ(末尾再帰・末尾呼び出し最適化について)

Elmで、List.mapなどを使わずに自分でループ的な処理を書きたい場合についてです。

関数型言語の手法に慣れてない人向け結論

「末尾再帰」が使えるので調べてみてください。

慣れている人向け結論

0.17現在、末尾再帰は最適化されるようです。末尾呼び出し最適化は無いので相互末尾再帰はスタックオーバーフローします。

検証

elm-lang/coreの初期にはTrampolineがあったようですが、現在は無くなっています。Elmのコンパイラのコードにも、tail call云々という文字列が見られます。ということは末尾再帰・末尾呼び出しが最適化されるのか、と調べてみました。

次のコードをelm-reactorで試します。単純にフォームで指定した回数、末尾再帰でカウントダウンするだけです。

import Html exposing (..)
import Html.Attributes as Attr
import Html.App as App
import Html.Events exposing (onClick, onInput)
import String
import Debug


main =
  App.program
    { init = init
    , view = view
    , update = update
    , subscriptions = subscriptions
    }



-- MODEL

type alias Model =
    { count : Int }

initialLoopCount = 100000

init : (Model, Cmd Msg)
init = { count = initialLoopCount }
       ! []



-- VIEW


view model =
    div [ ]
      [ div [] [text (toString model.count) ]
      , input [ onInput ChangeLoopCount, Attr.value (toString model.count )] []
      , button [ onClick LoopStart ] [ text "start" ]
      ]



-- SUBSCRIPTION

subscriptions : Model -> Sub Msg
subscriptions model =
    Sub.none



-- UPDATE

type Msg = LoopStart
         | ChangeLoopCount String

update : Msg -> Model -> (Model, Cmd Msg)
update msg model =
  case msg of
      LoopStart ->
          (loopStart model) ! []

      ChangeLoopCount nStr ->
          (changeCount model nStr) ! []


changeCount model nStr =
    case (String.toInt nStr) of
        Ok n ->
            { model | count = n }

        Err _ ->
            model


loopStart model =
    let
        loop n =
            if n > 0 then
                loop (n - 1)
            else
                { model | count = n }
    in
        loop model.count

本体は最後のloopStartです。単純な末尾再帰のカウントダウンで、100,000,000回でも一瞬で終わります。

一方、JavaScriptだと末尾再帰最適化が無いはずなので、同じアルゴリズムだとスタックオーバーフローになるはずです。

loop = function (n) {
  if (n > 0) {
    return loop(n - 1);
  }
  return n;
}

結果、上記Elmコードと同じ環境で17,920回からスタックオーバーフローしました。

明らかに差異があるので、末尾再帰最適化されていると判断して良さそうです。

ちなみに、以下の末尾再帰ではない再帰のコードに変更して試したところ、15,723回からスタックオーバーフローしました。

loopStart model =
    let
        loop n =
            if n > 0 then
                1 * (loop (n - 1))
            else
                n
    in
        { model | count = loop model.count }

相互再帰

末尾再帰は最適化されているようですが、末尾呼び出しはどうでしょうか。以下の相互末尾再帰コードに書き換えて試してみます。

loopStart model =
    let
        loop1 n =
            if n > 0 then
                loop2 (n - 1)
            else
                { model | count = n }
        loop2 n =
            if n > 0 then
                loop1 (n - 1)
            else
                { model | count = n }
    in
        loop1 model.count

結果、17,968回からスタックオーバーフローしました。末尾呼び出しの最適化は行われてないと考えられます。

広告を非表示にする