Schwartz変換 on Haskell

リストのリストを受け取って、リストの長さでソートするsortByLengthを書いてみる。

まずは素直に書いてみる。

import List;

sortByLength :: [[a]] -> [[a]]
sortByLength xs = sortBy cmp xs

cmp :: [a] -> [a] -> Ordering
cmp x y | length x < length y = LT
        | length x == length y = EQ
        | otherwise = GT

sortByを使うためにListをimportしている。SortByの型は(a -> a -> Ordering) -> [a] -> [a]。つまり、第一引き数に(a -> a -> Ordering)な型の関数、第二引き数に[a]をとり、[a]を返す関数。ここでは第一引き数に関数cmp,第二引き数にxsを渡している。

cmpは、[a],[a]を取りOrdering型を返す関数。ここでは二つの引き数(List)の長さを比べている。

問題点

cmpのパターンマッチングの中で何度もlengthを呼び出している。cmpはソート中に二値を比較するたびに適応されるので、ここで何度もlengthを呼び出すのはCPU効率が悪い(逆にShwartz変換はメモリ空間を犠牲にしているので、適材適所で使うべきだろうけど)。というわけで、Shwartz変換を使ってみます。

Shwartz変換バージョン

import List;

sortByLength xs = map untupplize $ sortBy cmp $ map tupplize xs

tupplize :: [a] -> ([a],Int)
tupplize xs = (xs, length xs)

untupplize :: ([a],Int) -> [a]
untupplize (xs,_) = xs;

cmp :: ([a], Int) -> ([a], Int) -> Ordering
cmp (_,x) (_,y) | x < y = LT
                | x == y = EQ
                | otherwise = GT

まず、tupplizeはリストを与えると(リスト,リストの長さ)という形のタプルを返す関数。これをmapに適応して、[リスト,リスト,リスト..]というリストを[(リスト,長さ),(リスト,長さ)..]というリストに変換する。

そのリストに対してcmpを適応する。cmpではパターンマッチで(リスト,長さ)から長さの部分をx,yという変数に束縛して、cmpではx,yの長さをチェックするだけ。毎回lengthを呼ばなくなったので効率が良くなった。

あとは、tupplizeされた状態の各要素をuntupplizeしてもとにもどしてあげれば良い。これはtupplizeの逆をやってるだけのなので割愛。

スコープを短く

tupplizeもuntupplizeもcmpも、ソートのためにしか使わないのだから、その中だけのスコープに限定したい

import List
sortByLength xs = map untupplize $ sortBy cmp $ map tupplize xs
    where
      tupplize xs = (xs, length xs)
      cmp (_,x) (_,y) | x < y = LT
                      | x == y = EQ
                      | otherwise = GT
      untupplize (xs,_) = xs

名前つけるまでもないものにはλ使う

tupplizeとuntupplize程度の処理、わざわざ名前付き関数にする必要もなし

import List
sortByLength xs = map (\(xs,_) -> xs)
                  $ sortBy cmp
                        $ map (\x -> (xs, length xs)) xs
    where
      cmp (_,x) (_,y) | x < y = LT
                      | x == y = EQ
                      | otherwise = GT

lambdaにしたら素直に後ろから読んでいくだけでわかりやすいコードになった。やったねたえちゃん！

関数合成してみる

sortByLengthの引き数がそのままmapの引き数になっててださいので、ポイントフリースタイルで書き直してみる

import List;

sortByLength :: [[a]] -> [[a]]
sortByLength  = map (\(xs,_) -> xs) . sortBy cmp . map (\xs -> (xs, length xs))
    where
      cmp (_,x) (_,y) | x < y = LT
                      | x == y = EQ
                      | otherwise = GT

Haskellでは . で関数を繋ぐことで関数合成ができる。g(f(x))が、g . fで表すことができる、という感じ。

このあたりは結構新しい概念なのでていねいに追う。

まずは、

map (\(xs,_) -> xs) . sortBy cmp . map (\xs -> (xs, length xs))

を詳細に観ていく。評価される優先順位がわかりやすい感じに書きかえる

(map (\(xs,_) -> xs)) . (sortBy cmp) . (map (\xs -> (xs, length xs)))

つまり、(map (\(xs,_) -> xs))で生まれる関数と(sortBy cmp)で生まれる関数と(map (\xs -> (xs, length xs)))で生まれる関数を合成している。

まずは一番最初 (map (\(xs,_) -> xs)) を見る。mapの型は (a -> b) -> [a] -> [b]で、ここでは引き数にラムダ式をひとつ与えている。これによって、mapがカリー化されるので、(map (\(xs,_) -> xs))が返すのは、型が[a] -> [b]な関数となる。

つぎに(sortBy comp)を見る。先ほどの例のおなじように考えて、sortBy の型が (a -> a -> Bool) -> [a] -> [a]なので、(sortBy cmp)は [a] -> [a]な型の関数となる。

最後のmapも同様。

これらのみっつの関数を合成したものを、sortByLengthに束縛している。

今日はここまで。