按指定顺序在 Haskell 中插入排序

Question

我正尝试在 haskell 中为每周的大学作业实施插入排序。这是我的插入和排序功能：

  insert :: (Ord a) => a -> [a] -> [a]
  insert a [] = [a]
  insert a (a':as)
       | a <= a'   = a:a':as
       | otherwise = a':insert a as


  insertionSort :: (Ord a) => [a] -> [a]
  insertionSort   []      = []
  insertionSort (a:as) = insert a (insertionSort as)

这行得通，但我的导师指定了这样的签名：

insert :: (a -> a -> Bool) -> a -> [a] -> [a]
insertionSort :: (a -> a -> Bool) -> [a] -> [a]

我现在尝试的一切都失败了，编译器错误也没有多大帮助。希望你们能帮我解决这个问题！

编辑：

我导师给的例子是这样的：

Main> insert (<) 3 [1,2,5,7,9]
[1,2,3,5,7,9]
Main> insSort (>) [7,9,1,2,5]
[9,7,5,2,1]

Answer 1

你需要做的就是使用布尔函数参数的结果而不是固定的比较，就像这样：

insert :: (Ord a) => (a -> a -> Bool) -> a -> [a] -> [a]
insert _ a [] = [a]
insert f a (a':as)
     | f a a'   = a:a':as
     | otherwise = a':insert f a as

其他功能类似。

insertionSort :: (Ord a) => (a -> a -> Bool) -> [a] -> [a]
insertionSort _  []      = []
insertionSort f (a:as) = insert f a (insertionSort f as)

Demo

按指定顺序在 Haskell 中插入排序

Insertionsort in Haskell with specified order

haskell

insertion-sort