递归 Haskell

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]

- Urah

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

- Satvik

---

@Urah 不需要。a 只是属于 Ord 类型类的任何类型。这只是为了使您的函数多态化，覆盖 Ord 类。但最好在编写函数定义之前编写类型。通过编写类型，您可以向编译器提供某些提示，以便它可以执行某种优化。 - Satvik

Answer 2

你需要从列表中删除第一个最小值，并将其连接到其余部分的前面。

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

- Robert

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)        

- Landei