哈斯克爾名單和功能

Question

這是在過去幾天瘋狂的家庭作業。

我得到一個列表，我正在應用一個函數 - 如果它旁邊的元素小於前一個，則將每個元素向右推。

我的功能，越過列表一次，列表的頭排序：

sortEm lis@(x:y:xs) = if x > y then y: sortEm (x:xs) else lis 
sortEm [x] = [x] 
sortEm [] = [] 

myList (x:y:xs) = if x > y then sortEm lis else x:myList(y:xs) 
myList [] = [] 
myList [x] = [x] 

但我的問題是，一旦sortem已經完成了它返回一個空列表或包含一個元素的列表，我將如何設計這個功能的方式？

我正在考慮foldl和一些haskell的魔法，但目前我卡住了。

在此先感謝

Answer 1

myList []  = [] 
myList (x : xs) = sortEm (x : myList xs) 

（未經測試）

或者在摺疊方面：

myList = foldr cons [] 
    where cons x xs = sortEm (x : xs) 

（還未經測試）

Answer 2

，你sortEm函數名稱的第一個是誤導，它不排序它的參數列表，但我將其頭部元件插入尾部。碰巧，有一個insert功能已經在Data.List module是插入第一個參數爲2，所以有一個等價

sortEm (x:xs) === Data.List.insert x xs 

現在，插入一個項目將只會讓你排序列表回來，如果你要插入它變成已經排序的列表。由於空列表排序，這就是你在dave4420的答案中得到的函數。這是一個"insertion" sort，逐步將列表元素插入輔助列表中，最初爲空。這就是第二個功能是什麼，你在dave4420答案了：

insertionSort xs = foldr Data.List.insert [] xs 

這不「適用sortem」即插入，「每個元素」只有一次。有關列表[a,b,c,...,z]這相當於

insert a (insert b (insert c (... (insert z []) ...))) 

你可能是指在您的評論是什麼，即比較（以及可能的交換）「只有一次」兩個相鄰的元素，被稱爲bubble sort。當然，在列表僅做一個傳球不會得到它排序，在一般情況下：

bubbleOnce xs = foldr g [] xs where 
    g x [] = [x] 
    g x xs@(y:ys) | x>y  = y:x:ys -- swap x and y in the output 
       | otherwise = x:xs -- keep x before y in the output 

現在，bubbleOnce [4,2,6,1,8] ==> [1,4,2,6,8]。您預期的值[2,4,1,6,8]將從摺疊函數g以相反的方向從左到右應用而產生。 但是，這自然要少得多哈斯克爾這裏做列出：

bubbleOnce' [] = [] 
bubbleOnce' (x:xs) = let (z,h)=foldl g (x,id) xs in (h [z]) where 
    g (x,f) y | x>y  = (x, f.(y:)) -- swap x and y in the output 
      | otherwise = (y, f.(x:)) -- keep x before y in the output 

（編輯:)看到jimmyt's answer爲等價的，但使用簡單的遞歸簡單又好的版本。它也比這裏的fodlr和foldl版本更加懶惰（不太嚴格）。

Answer 3

-- if..then..else version 
sortEM  :: Ord a => [a] -> [a] 

sortEM (x:y:xs)  = if x < y 
         then x : sortEM (y:xs) 
         else y : sortEM (x:xs) 
sortEM b   = b 


-- guard version 
sortEM_G :: Ord a => [a] -> [a] 

sortEM_G (x:y:xs) 
    | x < y  = x : sortEM_G (y:xs) 
    | otherwise = y : sortEM_G (x:xs) 
sortEM_G b   = b