MonadPlusとFoldableによって一般化されたソートです＞ω＜　リスト以外にもSeqなどのデータ型に適用できます＞ω＜

GSort.hs

module GSort (bubbleSort) where

import Prelude hiding (head, tail, foldr, foldr1)
import Control.Monad
import Data.Foldable

bubbleSort' :: (Ord a, MonadPlus m, Foldable m, Eq (m a)) => m a -> m a
bubbleSort' xs
  |xs  == mzero = xs
  |xs' == mzero = return x
  |x > y       = y <: x <: ys'
  |otherwise    = x <: y <: ys'
  where
    x   = head xs
    xs' = tail xs
    y   = head ys
    ys  = bubbleSort' $ tail xs
    ys' = tail ys

bubbleSort :: (Ord a, MonadPlus m, Foldable m, Eq (m a)) => m a -> m a
bubbleSort xs = foldr ((.) bubbleSort' . flip const) xs xs

head :: Foldable m => m a -> a
head = foldr1 const
tail :: (Foldable m, MonadPlus m) => m a -> m a
tail xs = snd $ foldr (\x (y, ys)-> (return x, y `mplus` ys)) (mzero, mzero) xs

infixr 9 <:
(<:) :: MonadPlus m => a -> m a -> m a
x <: xs = return x `mplus` xs

infixはモジュールの先頭に書かないといけないゾ

module GSort
....
infixr 9 <:
....
bubbleSort' ...