bubbleソートを作ってみる

最初に書いたもの

bubblesort :: Ord a => [a] -> [a]
bubblesort [] = []
bubblesort xs = (bubblesort $ init xs') ++ [last xs']
  where
    exchangeNeighbors ys = case ys of
      (a:b:zs) -> (min a b):(exchangeNeighbors $ (max a b):zs)
      (a:_)    -> [a]
    xs' = exchangeNeighbors xs

ソート順の指定などが出来なかったり、型指定がベタ書きだったりする所がイケてない。

ソートで共通の型とメソッドを作ってみたもの

data Order = Asc | Desc

type Sort a = Order -> [a] -> [a]

left :: Ord a => Order -> a -> a -> a
left Asc  = min
left Desc = max

right :: Ord a => Order -> a -> a -> a
right Asc  = max
right Desc = min

bubblesort :: Ord a => Sort a
bubblesort _ []     = []
bubblesort order xs = (bubblesort order $ init xs') ++ [last xs']
  where
    exchangeNeighbors ys = case ys of
      (a:b:ys') -> (left order a b):(exchangeNeighbors $ (right order a b):ys')
      (a:_)     -> [a]
    xs' = exchangeNeighbors xs

Order, Sort, left, rightは任意のソートメソッドで共通的に使える想定。

結果

*Main> bubblesort Desc [1..10]
[10,9,8,7,6,5,4,3,2,1]
*Main> bubblesort Asc $ reverse [1..10]
[1,2,3,4,5,6,7,8,9,10]

ハマったところ

type Sort = Ord a => Order -> a -> a -> aといった書き方は出来ない。

少なくともGHCでは受理されない。
http://stackoverflow.com/q/22945348

NumがShowやEqの小クラスじゃない

ソートの動作検証を行うのに、こんな感じのメソッドを作ってみた:

test :: Num a => Sort a -> IO ()
test sort = do
  print $ sort Asc [1]
  print $ sort Asc [2,1]
  print $ sort Asc [3,2,1]

結果

p2.hs:24:3:
    Could not deduce (Show a) arising from a use of ‘print’
    from the context (Num a)
      bound by the type signature for test :: Num a => Sort a -> IO ()
      at p2.hs:22:9-32
    Possible fix:
      add (Show a) to the context of
        the type signature for test :: Num a => Sort a -> IO ()

しかし手元にあるプログラミングHaskellを見ると、

class (Eq a, Show a) => Num a where ...

とある。

しばらくググってみた結果、どうやらGHC 7.4でNumからEqとShowが分離されたということが判明。
http://stackoverflow.com/a/11194912

とりあえず、以下のように複数指定してやればOKであった。

test :: (Num a, Show a) => Sort a -> IO ()

一方で、型推論では以下のような型が導出された。

test :: (Show s, Num t) => (Order -> [t] -> s) -> IO ()

また、今回のbubblesortメソッド自体は、任意のOrdな値に適用できる。つまり、

bubblesort Asc ['d','c','b','a']

は全く問題なく動作する。

そこで、以下のようにtestメソッドにCharのパターンも加えてみたのだが、

test sort = do
  print $ sort Asc [1]
  print $ sort Asc [2,1]
  print $ sort Asc [3,2,1]
  print $ sort Asc ['d','c','b','a']

結果

p2.hs:24:21:
    Could not deduce (Num Char) arising from the literal ‘1’
    from the context (Show s)
      bound by the inferred type of
               test :: Show s => (Order -> [Char] -> s) -> IO ()
      at p2.hs:(23,1)-(27,36)
    In the expression: 1
    In the second argument of ‘sort’, namely ‘[1]’
    In the second argument of ‘($)’, namely ‘sort Asc [1]’

bubblesortに渡すリストの各要素の値が、NumでもありCharでもあるので、型推論できないと言われる。

こちらについてはどうすれば解決できるか今のところ不明。