Как написать свою собственную функцию Haskell sortOn

Question

Мне было интересно, как написать свою собственную функцию sortOn.

Я сделал функцию sortBy и функцию on, как показано ниже, но не могу понять, как их объединить и что дополнительный код для добавления. sortOn похоже на sortBy, но данная функция (здесь она называется comp) применяется только один раз для каждого элемента списка

sortBy :: (a -> a -> Ordering) -> [a] -> [a]
sortBy comp [] = []
sortBy comp [x] = [x]
sortBy comp (x:xs) = insert x (sortBy comp xs)
 where 
  insert x [] = [x]
  insert x (y:ys) 
   | (comp x y == LT) || (comp x y == EQ) = x:y:ys
   | otherwise = y:(insert x ys)

on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
on b f x y = b (f x) (f y)

Answer 1

Вот подсказка.

Если у вас есть список [a] и вы просто sort его, функция sort будет неявно использовать экземпляр Ord для a и, в частности, функция:

compare :: a -> a -> Ordering

для определения относительного порядка пар a элементов.

Теперь, если у вас есть список [a] и a Функция преобразования b, и вы хотите использовать sortOn для сортировки списка преобразованных значений, вам нужно выяснить относительный порядок пар элементов b. Как ты это сделаешь? Ну, вы неявно будете использовать экземпляр Ord для b и, в частности, функцию:

compare :: b -> b -> Ordering

Другими словами, когда вы попытаетесь определить:

sortOn :: (Ord b) => (a -> b) -> [a] -> [a]
sortOn f lst = ...

вас У вас будут аргументы типа:

f :: a -> b
lst :: [a]

и дополнительные объекты типа:

sortBy :: (a -> a -> Ordering) -> [a] -> [a]
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
compare :: b -> b -> Ordering

Теперь вы можете увидеть, как их собрать, чтобы определить sortOn?

СПОЙЛЕРЫ

Дополнительная подсказка: какой тип compare `on` f?

Дополнительная подсказка: это a -> a -> Ordering.