Idiomatic Haskell Code zur Vereinfachung der Rekursion

Question

Ich muss foo n = maximumBy (comparing p) [1..n] berechnen, wobei p :: Int -> Int langsam ist. Aber ich weiß, dass p n < n für alle n > 0 und möchte diese Tatsache verwenden, um diese Berechnung auf folgende Weise zu beschleunigen: Ich berechne p x für x beginnend mit n bis 1, das aktuelle Maximum zu speichern. Sobald ich ein x erreiche weniger oder gleich dem aktuellen Maximum, weiß ich, dass dieses Maximum das globale sein muss und ich fertig bin.

So sieht mein Versuch wie folgt aus:

foo n = go (0, 0) n where 
    go (c, _) 1 = c 
    go (c, c') !x = if c' >= x then c else go (c2, c'2) (x-1) where 
     x' = p x 
     (c2, c'2) = if c' >= x' then (c, c') else (x, x') 

Dies funktioniert, aber sieht nicht sehr idiomatisch. Ich suche also eine elegantere Lösung. Hast du Vorschläge?

Answer 1

Sie können passend verwenden Muster die Verwendung, wenn zu reduzieren ... then ... else
Ein weiterer Trick ist eine Nummer zu Ihren Variablen zu geben, es können Sie den Start Fall var0 und für das erinnern, andere rekursive Aufruf können Sie dann ein schöneres var verwenden
Letzte Anmerkung, haben Sie einige wenn den gleichen Wert nach einem Prädikat der gleichen Form zurückkehrt und in der gleichen Umgebung dann können Sie gruppieren können sie zusammen.

foo n0 = go (0, 0) n0 
    where 
    go (x, y) n 
     | (n == 1) || (y >= n) = x 
     | y < (p n) = go (n, (p n)) (n-1) 
     | otherwise = go (x, y) (n-1) 

---

Rewriting Rechnung Kommentar Einnahme,

foo n0 = go 0 0 n0 
    where 
    go x y n 
     | (n == 1) || (y >= n) = x 
     | pn > y    = go n pn (n-1) 
     | otherwise    = go x y (n-1) 
      where 
      pn = p n 

Answer 2

OK, also lassen Sie mich sehen, ob ich mein Gehirn um diese richtig gewickelt ... Sie sagen, dass p n < n für alle interessanten n. Und Sie wollen p x für x = n to 1 berechnen, bis x wird weniger als die größte bisher gesehen p x?

Nun, es sieht so aus, als könnten Sie alle p x als eine faule Liste berechnen. Jetzt ist das Problem reduziert, diese Liste zu scannen, bis Sie finden, wonach Sie suchen. Ich würde vorschlagen takeWhile, außer wir müssen auch falten die Liste, um das aktuelle Maximum zu finden. Hmm, vielleicht können wir jeden Wert mit dem laufenden Maximum kombinieren?

So etwas wie

foo n = 
    let 
    ps = [ p x | x <- [n, n-1 .. 1] ] 
    qs = fold (\ px' (px, maxPX) -> (px', maxPX `max` px')) ps 
    in last . takeWhile (\ (px, maxPX) -> px >= maxPX) qs 

oder ähnliches?