Ich möchte einen Algorithmus in Haskell entwerfen mit Endrekursion und erster Ordnung Programmierung für InsertionsortInsertion Art mit Endrekursion & Funktion erster Ordnung
Ich habe mit dieser Lösung kam
Aber ich bin mir nicht sicher, ob es erste Reihenfolge und Tail-Rekursion verwendet.
Kann jemand kommen mit einer alternativen Lösung
Dank Verwendung
Dies ist die einfache Version, nicht Endrekursion mit noch 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
Sie können einen Speicher hinzufügen, die uns die Art mit Endrekursion umschreiben können:
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 ist ziemlich gut die Art und Weise definiert ist; aber nur für den Zweck von Funktionen höherer Ordnung, können wir definieren es mögen:
insert' :: Ord a => a -> [a] -> [a]
insert' x xs = menores ++ x:mayores
where (menores,mayores) = span (<x) xs
, wo der Abschnitt (<x) eine Funktion vom Typ Ord a => a -> Bool-span geben.
Dies verwendet keine Tail-Rekursion. Die 'sonst '-Klausel von' insert' ist 'y: insert_s' (deutlicher geschrieben als' (:) y (insert ys) ') erscheint der Aufruf von' insert' als Argument für '(:)', nicht in Heckposition –
Können Sie erklären, was Sie unter "Programmierung erster Ordnung" verstehen? Ist das einfach irgendetwas, das keine Funktion als Argument hat? – Lazersmoke
@Lazersmoke ja, genau. –