Elm でマージソート

tl;dr

アルゴリズム図鑑という書籍を参考に Elm で merge sort をやったら盛大にコケたので､Functional Programming in Elmという連載のMerge Sort を読みながら､勉強してみたらなんとか解くことができた｡

コード

import Html

-- まずは merge を作ります
merge : List comparable -> List comparable -> List comparable
merge left right =
    case (left, right) of
        ([], [])
            -> []
        (_::_, [])
            -> left
        ([], _::_)
            -> right
        (l::ls, r::rs)
            -> if l < r then
                   l :: merge ls right
               else
                   r :: merge left rs

-- つぎに半分にする分離装置を作ります
split : List comparable -> (List comparable, List comparable)
split list =
    let
        splitCore list_ flipFlop halfOne halfTwo =
            case list_ of
                [] -> (halfOne, halfTwo)
                x::xs -> if flipFlop then
                             splitCore xs (not flipFlop) (x::halfOne) halfTwo
                         else
                             splitCore xs (not flipFlop) halfOne (x::halfTwo)
    in
        splitCore list True [] []

-- そしてソートする部品をつくります
sort : List comparable -> List comparable
sort list =
    case list of
        [] -> list
        [_] -> list
        _ -> -- Elm の Case文って型を自由に取れるのか､知らなんだ
            let
                (halfOne, halfTwo) = split list
            in
                merge (sort halfOne) (sort halfTwo) -- 分割統治法のキモは再帰

-- 最後に確認します
main
    =  [3,1,4,5,9,2,6,0,8,7]
    |> sort
    |> Debug.toString
    |> Html.text -- [0,1,2,3,4,5,6,7,8,9]

参考にした文献

=> Merge Sort

結語

QuickSort の方が実装はラク｡