时间戳

首页 > 解决方案 > 如何编写我自己的 Haskell sortOn 函数

function - 如何编写我自己的 Haskell sortOn 函数

问题描述

我想知道如何编写自己的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)

标签： functionsortinghaskellfunctional-programminghaskell-platform

解决方案

这里有一个提示。

如果你有一个列表[a]并且你只是sort它，该sort函数将隐式地使用该Ord实例a，特别是该函数：

compare :: a -> a -> Ordering

找出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.

推荐阅读