comb sort

combsort.hs

import Data.List
import Test.QuickCheck

combSort :: Ord a => [a] -> [a]
combSort xs = comb (gap (length xs)) xs 

comb :: Ord a => Int -> [a] -> [a]
comb h xs
    | h <= 0 = xs
    | h == 1 = let sorted = comb' in
                if xs == sorted
                then sorted
                else comb h sorted                   
    | otherwise = comb (gap h) comb' 
  where
    comb' = foldl (foldfunc h) xs [0..end xs h] 
    foldfunc g ys i
        | ys !! i > ys !! (i + g) = swap i (i + g) ys
        | otherwise               = ys
    end ys g = (length ys - 1) - g 

gap :: Int -> Int
gap x = truncate $ fromIntegral x * 10 / 13

swap :: Int -> Int -> [a] -> [a]
swap i j xs = zipWith swap' [0..] xs
  where
    swap' n val
        | n == i    = xs !! j
        | n == j    = xs !! i
        | otherwise = val

prop_combSort :: [Int] -> Bool
prop_combSort xs = combSort xs == sort xs