Explizite Rekursion in Haskell

Question

Die Aufgabe: Ich versuche, eine Funktion mit Typ Signatur minimum_recursive :: (a -> a -> Bool) -> [a] -> a zu schreiben. Für seinen ersten Parameter akzeptiert er eine Funktion, die ich less aufrufen werde, die zwei Parameter akzeptiert, und gibt True zurück, wenn der erste Parameter kleiner als der zweite ist, ansonsten False. minimum_recursive akzeptiert auch eine Liste als zweiten Parameter. Mit expliziter Rekursion sollte minimum_recursive den kleinsten Wert in seiner Eingabeliste [a] ermitteln.

Mein Denken: Ich dachte, um die tatsächliche Rekursion in eine Hilfsfunktion, die auch einen Akku akzeptiert. Ich würde die Helferfunktion mit dem ersten Gegenstand als Akkumulator bezeichnen.

Was ich bisher haben: Bisher habe ich folgendes:

-- function as first parameter to min' 
-- accepts two params, returns True if 
-- first must come before second in sorted 
-- order 
less :: Ord a => a -> a -> Bool 
less a b = a < b 

-- Subpart B 
minimum_recursive :: (a -> a -> Bool) -> [a] -> a 
minimum_recursive func list = minimum_recursive_h func list [] 

Ich habe Probleme mit herauszufinden, wie auch minimum_recursive_h zu schreiben beginnen.

Hinweis: Ich weiß, es gibt wahrscheinlich einen einfacheren Weg, um diese Aufgabe zu erfüllen, aber ich bin verpflichtet, darüber zu gehen, wie oben angegeben.

Answer 1

Man könnte es wie folgt tun:

minimum_recursive _ [] = error "no minimum of empty list" 
minimum_recursive _ [x] = x 
minimum_recursive f (x:xs) = let m = minimum_recursive f xs 
          in if f x m then x else m 

Oder mit einem Akkumulator:

minimum_recursive _ [] = error "no minimum of empty list" 
minimum_recursive f (x:xs) = helper f x xs 
    where 
     helper _ m [] = m 
     helper f m (x:xs) 
      | f m x = helper f m xs 
      | otherwise = helper f x xs 

Answer 2

Wenn Sie das kleinste Element in der Liste möchten, suggest du, dass Sie die kleinste Ellement hinzufügen, die Sie derzeit als Parameter für die Funktion haben.

minimum_recursive :: (a -> a -> Bool) -> a -> [a] -> a 
minimum_recursive f min [] = min 
minimum_recursive f min (x:xs) | f min x = minimum_recursive f min xs 
           | otherwise = minimum_recursive f x xs 

Sie sollten auch die Art in der Funktion, die diesen Aufruf a-Maybe a ändern, da es kein kleinster ellement in einer leeren Liste ist. Here some help about Maybe

Wenn Sie es ohne einen zusätzlichen Parameter tun möchten, könnten Sie das kleinste Ellement am Anfang der Liste gut speichern. In diesem Fall ist es wichtig zu verwenden Vielleicht

minimum_recursive :: (a -> a -> Bool) -> [a] ->Maybe a 
minimum_recursive f [] = Nothing 
minimum_recursive f (x:[]) = Just x 
minimum_recursive f (y:(x:xs)) | f y x  = minimum_recursive f (y:xs) 
           | otherwise = minimum_recursive f (x:xs) 

Dies ist, wie das Minumum ehit Falte gefunden werden kann. Betrachten Sie die Schönheit der Funktionsprogrammierung. Aber das wird nicht funktionieren für die leere Liste

simplefold :: [a] -> a 
simplefold (x:xs) = foldl min x xs 

Aber wir können diese Funktion in einem einbetten, die überprüft, ob die Liste leer ist und das Rück Nichts in diesem Fall.

betterfold :: [a] -> Maybe a 
betterfold [] = Nothing 
beterfold l = Just (simplefold l) 

Answer 3

Der klassische Weg, um Probleme zu lösen rekursiv ist folgende:

1. Angenommen, Sie haben das Problem bis auf die letzten s fast gelöst tep.
2. Schreiben Sie den Code, der die Lösung für alle, mit Ausnahme des letzten Schritts, berechnet.
3. Schreiben Sie das Basisgehäuse.

Im Fall von Listen bedeuten dies dieses Muster:

1. Fall: was sollte für [] die Lösung sein? (wenn überhaupt, im Falle Ihrer minimum_recursive Funktion wäre dies ein Fehler).
2. Für eine nicht leere Liste x:xs, nehmen Sie an, Sie haben bereits almostTheResult = minimum_recursive f xs. Wie berechnet man minimum_recursive (x:xs) angesichts dieser?

Ich gebe Ihnen einen großen Hinweis: Ihre minimum_recursive können in Bezug auf foldr und diese Funktion implementiert werden:

minBy :: (a -> a -> Bool) -> a -> a -> a 
minBy pred x y = if pred x y then x else y 

Die foldr Funktion tut genau das, was ich beschreibe oben. Das erste Argument zu foldr ist die Funktion, die die endgültige Lösung berechnet, die den Listenkopf und die Teillösung für den Schwanz angibt, und das zweite Argument ist der Ergebnisbasisfall.