Haskellの再帰的なソート機能

Question

私はこの2つの機能ではHaskellでのソート機能を実装したいと思います：

smallest :: (Ord a) => [a] -> a 
smallest [] = error "empty list" 
smallest [x] = x 
smallest (x:xs) 
    | x < smallest xs = x 
    | otherwise = smallest xs 

insert :: Int -> [Int] -> [Int] 
insert x [] = [x] 
insert x (y:ys) 
    | x <= y = x:y:ys 
    | otherwise = y:insert x ys 

私の考えでは、再帰と右の位置ではなく、私はに新しいですと最小値を挿入することですハスケル私はそれを実装する方法にいくつかの問題があります。

Answer 1

smallest (x:xs) 
    | x < smallest xs = x 
    | otherwise = smallest xs 

は、リストの各ポイントでsmallestクエリの数を重複して指数関数的に吹き飛ばします。代わりに：

smallest (x:xs) = min x (smallest xs) 

、あるいは単にsmallest = minimum。

insertionSort [] = [] 
insertionSort (x:xs) = insert x (insertionSort xs) 

だけでなく、残りのリストをお返しするsmallestが必要になります。この1：

selectSmallest :: [Int] -> (Int, [Int]) 
selectSmallest (x:xs) = let (y, ys) = smallest xs in if x < y 
    then (x, xs) 
    else (y, x:ys) 

selectionSorta [] = [] 
selectionSorta xs = let (y, ys) = smallest xs in 
    y : selectionSorta ys 

ここで私はあなたの機能または類似のものと見ることができるいくつかの種類があります