时间戳

首页 > 解决方案 > Haskell - 我有一个问题分为 3 个部分 - 使用前 2 个函数创建一个函数，对第一个元素的元组列表进行排序

haskell - Haskell - 我有一个问题分为 3 个部分 - 使用前 2 个函数创建一个函数，对第一个元素的元组列表进行排序

问题描述

哈斯克尔新手。所以我创建的第一个函数sort_by使用快速排序对 a 类型的列表进行排序 - 工作正常。

下一个函数 compare by 接受一个比较器类型（定义如下）和一个函数并返回一个比较器 - soGT等EQ。这两个函数我都必须只使用函数定义。现在的问题 - 我应该使用这两个函数来定义一个基于使用currying的标题的函数，但我不知道我的compare_By函数应该如何帮助创建这样的函数？

非常感谢任何帮助。谢谢。

import GHC.Show (Show)
type Comparator a   = a -> a -> Ordering
type Tokeniser a    = String -> [a]
type Translator a b = a -> Maybe b

data English = E String deriving (Show)
data French  = F String deriving (Show)
data German  = G String deriving (Show)


sort_by :: Comparator a -> [a] -> [a]
sort_by o as = qs as []
    where qs [] as' = as'
          qs (a:as) as' = qs les $ a : qs gts as'
            where les = [a' | a' <- as, a  `o` a' == GT] 
                  gts = [a' | a' <- as, a `o` a' /= GT]

compare_by :: (b -> a) -> Comparator a -> Comparator b
compare_by f o a b = o (f a) (f b)

sort_by_fst :: Comparator a -> [(a,b)] ->[(a,b)]
sort_by_fst f [(a,b)] = ??

标签： haskellfunctional-programming

解决方案

面对这些问题时，查看类型并从那里开始工作会很有帮助。

您需要使用sort_by和compare_by创建sort_by_fst. 显然，我们需要sort_by对列表进行排序，所以让我们看看它的类型：

sort_by :: Comparator a -> [a] -> [a]

太好了，让我们用它来对列表进行排序：

sort_by_fst f xs = sort_by _comparator xs

再次查看的类型sort_by，我们可以看到我们需要Comparator (a, b)对xs :: [(a, b)]. 但是我们只有一个f :: Comparator a，所以用compare_by得到一个Comparator (a, b)。

compare_by :: (b -> a) -> Comparator a -> Comparator b
-- Specialising to the types we need (substituting b = (a, b)):
compare_by :: ((a, b) -> a) -> Comparator a -> Comparator (a, b)

除了 a 之外Comparator a，我们还需要一个(a, b) -> a: 一个获取元组第一个元素的函数。fst正是这样做的：

sort_by_fst f xs = sort_by (compare_by fst f) xs

这也可以写得更简洁

sort_by_fst = sort_by . compare_by fst

顺便说一句，_name(eg _comparator) 语法是GHC 的类型化孔功能。如果你编译有漏洞的代码，GHC 会告诉你需要什么类型的表达式，并建议可能的绑定（例如函数和参数）来填补漏洞。

附带说明一下，该compare_by函数是onfrom的专用和翻转版本Data.Function：

on :: (b -> b -> c) -> (a -> b) -> a -> a -> c

sort_by_fst因此可以这样实现：

import Data.List (sortBy)
import Data.Function (on)

sort_by_fst :: Comparator a -> [(a, b)] -> [(a, b)]
sort_by_fst f = sortBy (f `on` fst)

推荐阅读