按给定条件快速排序Haskell

2024-05-21 • 问答

我有一个要求：

让我们考虑一下字符串之间的以下排序关系：s1小于s2 如果s1短于s2或它们具有相同的长度并且s1在字典上更小比s2。用两个参数x和y编写一个名为ltstr的函数，该函数实现此顺序关系。编写一个获得2个参数的函数qs：一个列表和一个排序标准，然后对使用快速排序算法，根据给定的标准给出列表。例如：

Main> qs ["Russia","Norway","Germany","Romania","France","Antigua and Barbuda","South Korea","Angola","Hungary"] ltstr
["Angola","Russia","Hungary","Antigua and Barbuda"]

我不确定如何在Haskell中准确地传递函数作为参数。这是代码框架

\begin{code}
 ltstr s1 s2 = if length(s1) < length(s2) then s1
               else if length(s1) == length (s2) && s1 < s2  then s1  
                     else s2

 qs (l:ls) crit = (qs smalls crit) ++ [l] ++ (qs biggs crit) 
                  where                    
                  smalls = [ s | s <- ls,(crit s l) == s]
                  biggs = [ b | b <- ls,(crit b l) == l]    

\end{code}

现在，此要求与排序算法无关。它只是乞求(def brackets ["()" "[]" "{}" "<>"]) (defn bracket [string brackettype] (for [b brackets] [(let [f (str (first b)) l (str (last b))] (if (or (= brackettype f) (= brackettype l)) (def fstringl (str f string l))))]) bstringb) (bracket "hello" "[") => #object[clojure.lang.Var$Unbound 0x6401b490 "Unbound: #'me.core/fstringl"]类型的Ordering实例。

只要您做对了，Data.List.sortBy :: (a -> a -> Ordering) -> [a] -> [a]就可以轻松完成。

Monoid

事情是sortByLengthThenLex :: (Foldable t,Ord (t a)) => [t a] -> [t a] sortByLengthThenLex = sortBy compareLengthThenLex where compareLengthThenLex :: (Foldable t,Ord (t a)) => t a -> t a -> Ordering compareLengthThenLex x y = (length x `compare` length y) <> (x `compare` y)类型的Monoid实例的定义如下

Ordering

如果比较的左手边相等，则优先级高。

相应地

instance Monoid Ordering where  
  mempty = EQ  
  LT `mappend` _ = LT  
  EQ `mappend` y = y  
  GT `mappend` _ = GT

注意：您可以将λ> sortByLengthAndLex ["Russia","Norway","Germany","Romania","France","Antigua and Barbuda","South Korea","Angola","Hungary","USA","UK"] ["UK","Russia","Antigua and Barbuda"]运算符视为<>的默认中缀版本。

按给定条件快速排序Haskell

pirate96 回答：按给定条件快速排序Haskell

大家都在问