遞歸哈斯克爾

Question

我想實現這樣的事情：

mymin (x:[]) = x 
mymin (x:y:xs) = mymin ((if x < y then x else y):xs) 

mysort [] = [] 
mysort (x) = mymin x (mysort othervalues) 

我知道這個代碼是錯誤的，但它只是想法。我怎麼可以連接其餘的值與返回遞歸的最小值。 輸入會像

mysort [7,9,3,7,1,2]

[1,**7,9,3,7,2**] 
[1,2,**7,9,3,7**] 
[1,2,3,**7,9,7**] 
[1,2,3,7,**7,9**] 
[1,2,3,7,7,**9**] 
[1,2,3,7,7,9] 

Answer 1

我想你想實現選擇排序。

mymin最好返回最小元素以及列表中的其餘元素。

mymin :: Ord a => [a] -> (a,[a]) 
mymin [x] = (x,[]) 
mymin (x:xs) = let (min,rest) = mymin xs 
    in if x < min then (x,min:rest) else (min,x:rest) 

mysort :: Ord a => [a] -> [a] 
mysort [] = [] 
mysort xs = let (min,rest) = mymin xs 
    in min:mysort rest 

Answer 2

您需要從列表中刪除最小的第一次出現，它Concat的到前面的休息

mymin :: (Ord a) => [a] -> a 
mymin [x] = x 
mymin (x:y:xs) | x < y  = mymin (x:xs) 
       | otherwise = mymin (y:xs) 

myremove :: (Eq a) => a -> [a] -> [a] 
myremove x [] = [] 
myremove x (y:ys) | x == y = ys 
        | otherwise = y: myremove x ys 

mysort :: (Ord a) => [a] -> [a] 
mysort [] = [] 
mysort [x] = [x] 
mysort xs = x : mysort (myremove x xs) where x = mymin xs 

Answer 3

大廈Satvik的回答，您可以通過編寫mymin爲避免明確遞歸

mymin :: Ord a => [a] -> (a, [a]) 
mymin (x : xs) = foldr f (x, []) xs where 
    f z (y, ys) = if y < z then (y, z : ys) else (z, y : ys)