Haskell实现指定签名冒泡排序：无Ord约束是否可实现

核心疑问解答 #

你的教授没有漏写Ord a类型约束，该需求完全可以实现。

签名中的第一个参数(a -> a -> Bool)就是自定义比较规则的入参，所有元素的大小判定逻辑都由这个函数提供，不需要依赖Ord类的默认比较方法。这种设计的灵活度更高，支持自定义任意排序规则，不需要要求a类型实现Ord实例。

实现思路 #

• 先实现单轮冒泡的辅助函数：遍历列表，相邻元素用传入的比较函数判断，如果满足交换条件就交换位置，遍历完成后当前轮次的极值元素会被移动到列表末尾
• 主函数递归执行冒泡逻辑：每次拿到单轮冒泡后的列表，取出末尾已经排好的极值，对剩余的前半部分递归执行冒泡排序，最后拼接结果即可

示例实现代码 #

bsort :: (a -> a -> Bool) -> [a] -> [a]
bsort cmp [] = []
bsort cmp xs = 
  let bubbled = bubble cmp xs
  in bsort cmp (init bubbled) ++ [last bubbled]
  where
    bubble cmp [x] = [x]
    bubble cmp (x:y:xs)
      -- 满足比较函数返回True时交换两个元素位置
      | cmp x y = y : bubble cmp (x:xs)
      | otherwise = x : bubble cmp (y:xs)

使用示例 #

1. 数字升序排序，传入(>)作为比较函数（规则：前一个元素大于后一个时需要交换）

-- 执行结果为 [1,2,3,4]
bsort (>) [3,1,4,2]

2. 按字符串长度降序排序，传入自定义长度比较函数

-- 执行结果为 ["haskell","python","java","c"]
bsort (\a b -> length a < length b) ["haskell", "java", "c", "python"]

内容的提问来源于stack exchange，提问作者Zhijie Xia