Idiomatic codice Haskell per semplificare la ricorsione

Question

Ho bisogno di calcolare foo n = maximumBy (comparing p) [1..n], dove p :: Int -> Int è lento. Ma so che p n < n per tutti n > 0 e voglio usare questo fatto per accelerare questo calcolo nel seguente modo: computo p x per a partire da n fino a 1, memorizzando il massimo corrente. Una volta raggiunto lo x minore o uguale al massimo corrente, so che questo massimo deve essere quello globale e che ho finito.

Quindi il mio tentativo assomiglia a questo:

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

Questo funziona, ma non sembra molto idiomatica. Quindi sto cercando una soluzione più elegante. Hai suggerimenti?

Answer 1

È possibile utilizzare il pattern matching per ridurre l'uso di if ... then ... else
Un altro trucco è quello di dare un numero alla variabile, permettono di ricordare il caso di iniziare Var0 e per la altra chiamata ricorsiva è possibile quindi utilizzare una più bella var
Ultima nota, si ha qualche se restituendo lo stesso valore dopo un predicato della stessa forma e condividendo lo stesso ambiente allora potrebbe essere possibile raggrupparli insieme.

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) 

---

Riscrittura tenendo conto commento,

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, quindi vediamo se ho avvolto il mio cervello intorno a questo correttamente ... Stai dicendo che p n < n per tutti gli interessanti n. E vuoi calcolare p x per x = n to 1, fino a x diventa inferiore al più grande p x visto finora?

Bene, sembra che si possa calcolare tutto lo p x come elenco pigro. Ora il problema si riduce alla scansione di questo elenco fino a trovare quello che stai cercando. Vorrei suggerire takeWhile, tranne che abbiamo anche bisogno di fold l'elenco per trovare il massimo corrente. Hmm, forse possiamo accoppiare ogni valore con il massimo corrente?

Qualcosa di simile

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 

o simili?