sorte d'insertion en utilisant la récursivité queue et première fonction pour

Question

Je voudrais concevoir un algorithme Haskell utilisant récursion queue et première programmation de commande pour tri par insertion

Je suis venu avec cette solution

isort :: Ord a => [a] -> [a] 
isort [] = [] 
isort [x] = [x] 
isort (x:xs) = insert (isort xs) 
    where insert [] = [x] 
      insert (y:ys) 
      | x < y = x : y : ys 
      | otherwise = y : insert ys 

Mais je ne suis pas sûr si elle utilise le premier ordre et la récursivité de la queue.

Quelqu'un peut-il trouver une solution de rechange à l'aide

• queue récursion
• première programmation pour

Merci,

Answer 1

Ceci est la version simple, sans utiliser ni récursion queue HOF

sort :: Ord a => [a] -> [a] 
sort [] = [] 
sort [x] = [x] 
sort (x:xs) = insert x (sort xs) 

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

Vous pouvez ajouter un accumulateur, qui nous permet de réécrire le genre en utilisant la récursivité queue:

sort' :: Ord a => [a] -> [a] 
sort' xs = sortAcc xs [] 

sortAcc :: Ord a => [a] -> [a] -> [a] 
sortAcc [] acc = acc 
sortAcc (x:xs) acc = sortAcc xs (insert x acc) 

insert est assez bien défini la façon dont il est; mais juste dans le but d'utiliser des fonctions d'ordre supérieur, on peut le définir comme:

insert' :: Ord a => a -> [a] -> [a] 
insert' x xs = menores ++ x:mayores 
    where (menores,mayores) = span (<x) xs 

où la section (<x) est une fonction de type Ord a => a -> Bool passé à span.