Kod haskel Idiomatic upraszczający rekursję

Question

Muszę obliczyć foo n = maximumBy (comparing p) [1..n], gdzie p :: Int -> Int jest powolny. Ale wiem, że p n < n dla wszystkich n > 0 i chcesz użyć tego faktu, aby przyspieszyć to obliczenie w następujący sposób: Obliczyć p x dla x począwszy od n do 1, zapamiętywanie bieżącego maksimum. Po osiągnięciu x mniejszej lub równej bieżącemu maksimum wiem, że to maksimum musi być globalne i gotowe.

Więc moja próba wygląda następująco:

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') 

To działa, ale nie wygląda bardzo idiomatyczne. Dlatego szukam bardziej eleganckiego rozwiązania. Czy masz sugestie?

Answer 1

Można użyć wzorca dopasowania do zmniejszenia zużycia if ... then ... else
Inną sztuczką jest dać numer do zmiennej, to pozwoli Ci zapamiętać wielkość Zaczynając var0 i dla inne wywołanie rekurencyjne można użyć ładniejszy var
ostatnia uwaga, masz jakiś jeśli powrót tą samą wartość po orzecznika o tej samej formie i dzielenie tego samego środowiska to może być ich można grupować razem.

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) 

---

Przepisywanie uwzględnieniem uwag,

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, więc pozwól mi zobaczyć, czy ja owinięty wokół mojego mózgu to poprawnie ... Mówisz, że p n < n dla wszystkich ciekawym n. A chcesz obliczyć p x dla x = n to 1, aż x stanie się mniejszy niż jak dotąd największy oglądany p x?

Wygląda na to, że można obliczyć całą liczbę p x jako leniwą listę. Teraz problem polega na skanowaniu tej listy, dopóki nie znajdziesz tego, czego szukasz. Sugerowałbym takeWhile, z wyjątkiem tego, że musimy również krotnie listę, aby znaleźć aktualne maksimum. Hmm, może możemy sparować każdą wartość z maksymalnym biegiem?

Coś

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 

lub podobnym?