Wie schreibe ich InsertionSort mit Foldr?

Question

Ich schrieb die folgenden Haskell Funktionen:

myInsert :: Ord a => a -> [a] -> [a] 
myInsert x [] = [x] 
myInsert x (y:ys) = if x < y then x:y:ys else y:myInsert x ys 

insertionSort :: Ord a => [a] -> [a] 
insertionSort [] = [] 
insertionSort [x] = [x] 
insertionSort (x:xs) = myInsert x (insertionSort xs) 

Wie Sie sehen können, "InsertionSort" abhängig von "myInsert", und sie funktionieren gut. Jetzt werde ich gebeten, "foldr" in "insertioSort" zu verwenden, aber ich konnte kein erfolgreiches Ergebnis erzielen.

Ich werde Ihr Feedback zu schätzen wissen.

Answer 1

Hier ist die definition of foldr used in GHC:

foldr k z = go 
      where 
      go []  = z 
      go (y:ys) = y `k` go ys 

Nur der Einfachheit halber wollen wir go, Inline- und ein bisschen weniger Phantasie Syntax:

foldr k z [] = z 
foldr k z (x:xs) = k x (foldr k z xs) 

Zum Vergleich hier ist Ihre Funktion:

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

Beachten Sie, wie ähnlich sie sind! Können Sie herausfinden, was k und z in den foldr Gleichungen sein müssen, um gleich Ihrer Implementierung von insertionSort zu sein?