如何使用Haskell中的快速排序通过其accountID对列表进行排序

Question

我是一名真正擅长函数式编程的学生.我正在处理已经定义为数据的银行应用程序,

type Accountno = Int 
data Accounttype = Saving | Current  | FixedDeposit deriving (Show,Read)
type Accountamount = Int
type Name = String 
type Account = (Accountno, Name, Accounttype, Accountamount) 


exampleBase :: [Account]
exampleBase = [ (1,"Jennifer",Saving,1000 ) , 
    (5,"Melissa",Current,3000) ,
    (2,"Alex",Saving,1500)]

我试图使用以下代码按其帐号对列表进行排序,

sortByID :: (Ord a) => [a] -> [a]
sortByID [] = []
sortByID (l :ls) =
  let
   smallerSorted = sortByID [x | x <- ls, x <= l]
   biggerSorted = sortByID [x | x <- ls, x > l]
  in
   smallerSorted ++ [l] ++ biggerSorted


viewSortedDetails :: IO()
viewSortedDetails = 
    do
     putStrLn "Account Details Sorted By Account ID"
     let records = sortByID exampleBase
     let viewRecord = map show records
     mapM_ putStrLn viewRecord

但我没有得到预期的结果.因为它给了我一个错误,通知"定义viewSortedDetails所需的Ord Accounttype实例".请帮助我克服这个问题非常感谢!

Answer 1

好吧,问题是你正在使用<=两个Account值进行排序比较,例如两个值,它们需要Account是一个实例Ord.现在,它Account是四元素元组的同义词,它被定义为Ord元组中所有类型的实例.Accountno,Name和,Accountamount都是具有Ord实例的类型的同义词,但Accounttype不是.

您可以Account通过创建Accounttype实例来直接对值进行排序Ord,只需将其添加到deriving子句中即可.

但是,如果你想具体排序仅受账户号码,而不是元组的其他元素,你需要以不同的方式做一些事情.一种选择是Account使用自定义Ord实例创建数据类型:

data Account = Account Accountno Name Accounttype Accountamount deriving (Eq, Show, Read)

instance Ord Account where
    (...)

然后您可以根据需要定义排序.

或者,你可以保持原样,而只是比较你想要的元素而不是整个Account值,使用这样的东西:

accountNo :: Account -> Accountno
accountNo (n,_,_,_) = n

......然后用类似的东西做比较smallerSorted = sortByID [x | x <- ls, accountNo x <= accountNo l].标准库还包含一个on用于此目的的函数,但在这种情况下使用它会很麻烦.

关于Haskell代码的一般主题的一些其他与您的问题不太相关的评论:

• Account可能使用记录语法定义为数据类型比使用类型同义词更好.大元组可能很难处理.

• Accountno并且Accountamount应该也可以是不同的类型,以避免将它们与其他Ints 混合:第一种因为对帐号进行算术没有意义,后者部分是因为(我猜)你隐含地使用定点算法,例如100实际上意味着1.00,一般只是为了避免混淆.

• 事实上,无论如何,Int这可能是一个糟糕的选择Accountamount:为什么不是来自Data.Fixed,Ratio Integer或者基于10安全的浮点类型(尽管标准库中没有一个,不幸的是).

• 标准库当然包括已经排序的功能 - 我假设重新实现是为了学习目的,但在实践中它可以全部被类似的东西取代sortBy (compare `on` accountNo).