関数型言語らしい書き方をElmのコードで知る

覚えたての関数型言語でコードを書いてみると何故か関数型っぽくないなーと感じることがしばしばあったので、どう考えて書いていけばよいのか調べてみました。ここでは書籍関数型プログラミング実践入門よりトップダウンに考える方法をElmで紹介しようと思います。

対象者

最近、Elmを始めたがいまいち関数型言語らしい書き方がわからない方

わかること

関数型言語を使った問題の解き方
トップダウン思考で問題を考える方法を感じ取れる

書籍で書かれているように詳しく過程は紹介しません。それでは始めましょう。

ランレングス圧縮

今回の問題は書籍で紹介されているランレングス圧縮を扱います。詳しい説明はWikipediaを見ていただくとして、ここでは具体例だけをお見せいたします。

AAABBCCCCAAA -> A3B2C4A3

この通り、ランレングス圧縮とはこのような符号化のことを言います。

命令形言語のエッセンスで解く

まずはこちらをご覧ください。

module RLE exposing (rle)


-- >>> rle ""
-- ""
-- >>> rle "A"
-- "A1"
-- >>> rle "AAABBCCCCAAA"
-- "A3B2C4A3"

rle : String -> String
rle rawString =
    case String.toList rawString of
        [] ->
            ""

        h :: t ->
            aux 1 h (String.fromList t) -- 最初の一文字を覚える


aux : Int -> Char -> String -> String
aux runLength prevChar tailString =
    case String.toList tailString of
        [] ->
            String.concat <| String.fromChar prevChar :: [ toString runLength ] -- 文字がなくなったらおしまい

        c :: s ->
            if c == prevChar then
                aux (runLength + 1) prevChar (String.fromList s) -- 同じ文字なら連長をカウントアップ
            else
                String.concat <|
                    String.fromChar prevChar
                        :: [ toString runLength, aux 1 c (String.fromList s) ] -- 違う文字なら新たに1からカウント

書籍で紹介されているものをElmで書いたものです。forループを再帰で解いた感じがします。しかし、これだけではどこが関数型言語らしくないのかわかりません。

関数型言語のエッセンスで解く

それでは次に関数型言語のエッセンスで解いてみます。コードからトップダウンに問題を考えるってこういうことかーと感じていただければと思います。文字列から文字列への変換の型を満たす関数を考える前に中間構造の型を考えてみましょう。

module RLE exposing (rle)


rle : String -> String
rle =
    fromCharAndRunLength << toCharAndRunLength
    
    
-- >>> fromCharAndRunLength [("A", 3), ("B", 4)]
-- "A3B4"
fromCharAndRunLength : List (Char, Int) -> String
fromCharAndRunLength =
    cat << rls2strs


-- >>> rls2strs [("A", 3), ("B", 4)]
-- ["A3", "B4"]
rls2strs : List (Char, Int) -> List String
rls2strs rls =
    ["P1"]


-- >>> cat ["A3", "B4"]
-- "A3B4"
cat : List String -> String
cat strs =
    "P1"


-- >>> toCharAndRunLength "AAABBBB"
-- [("A", 3), ("B", 4)]
toCharAndRunLength : String -> List (Char, Int)
toCharAndRunLength s =
    [('P', 1)]

Elm Search

Elm Searchを使うと型から関数を見つけることが出来ます。すると String.concat 関数が見つかるので cat を置き換えてみましょう。 hoogleではないものの、Elmにもこういうサービスが有ったんですね。

module RLE exposing (rle)

import List.Extra exposing (group)


rle : String -> String
rle =
    fromCharAndRunLength << toCharAndRunLength
    
    
-- >>> fromCharAndRunLength [("A", 3), ("B", 4)]
-- "A3B4"
fromCharAndRunLength : List (Char, Int) -> String
fromCharAndRunLength =
    String.concat << rls2strs


-- >>> rls2strs [("A", 3), ("B", 4)]
-- ["A3", "B4"]
rls2strs : List (Char, Int) -> List String
rls2strs =
    List.map rls2str
    
    
rls2str : (Char, Int) -> String
rls2str (c, n) =
    String.concat <| String.fromChar c :: [ toString n ]


-- >>> toCharAndRunLength "AAABBBB"
-- [("A", 3), ("B", 4)]
toCharAndRunLength : String -> List (Char, Int)
toCharAndRunLength =
    List.map toPair << group << String.toList


toPair : List Char -> (Char, Int)
toPair rls =
    case rls of
        h :: _ ->
            ( h, List.length rls )

        [] ->
            Debug.crash ""

String -> List String をElm Searchで検索しても見つかりませんが、 List a -> List (List a) で検索してみると List.Extra.group が見つかります。 HaskellではChar型のリストがString型と考えるみたいでして、Elmでも同様に考えてみます。

さて、続けて toPair を実装してみましたが、よく見てください Debug.crash が登場しています。ロジック上これが呼ばれることはないはずですが、ここではきっちりとプログラム実行中に停止しないようにしてみます。

module RLE exposing (rle)

import List.Extra exposing (group)


rle : String -> String
rle =
    String.concat << List.map (rls2str << toPair) << group << String.toList


rls2str : Maybe ( Char, Int ) -> String
rls2str rls =
    case rls of
        Just ( c, n ) ->
            String.concat <| String.fromChar c :: [ toString n ]

        Nothing ->
            ""


toPair : List Char -> Maybe ( Char, Int )
toPair str =
    case str of
        h :: _ ->
            Just ( h, List.length str )

        [] ->
            Nothing

fromCharAndRunLength と toCharAndRunLength はもう不要なので削除します。これで完成です。

どのあたりが関数型言語らしいコードなのか

トップダウンに問題を考えていき、機械的に型を解決していくことで解決まで出来ました。前者と見比べてみると高階関数と関数合成を多様していることがわかります。これはボトムアップな思考のまま逐次処理を行うコーディングをしていると見られない関数型言語らしい記述らしいです。高階関数はトップダウンに問題を考える上で非常に相性が良いとされていました。

やってみたものの果たしてElmでこの解き方が推奨されるのかはわかりませんが、こういう書き方もできるというご紹介でした。

繰り返しになりますが、本投稿は書籍関数型プログラミング実践入門に紹介されている考え方を踏襲してElmで実装しています。本書にはより詳しく考え方が載っているのでぜひご一読ください。

また、今回使用してコードは次のリポジトリで公開しております。

https://github.com/pastelInc/elm-run-length-encoding/blob/master/src/RLE.elm

パステル色な日々

気ままに綴るブログ