簡化遞歸的原地Haskell代碼

我需要計算foo n = maximumBy (comparing p) [1..n]，其中p :: Int -> Int很慢。但是我知道p n < n對於所有的n > 0並且想用這個事實來加速這個計算的方式如下：我計算p x爲x爲n降到1，記住當前的最大值。一旦我達到x小於或等於當前最大值，我知道這個最大值必須是全局值，而且我已經完成了。簡化遞歸的原地Haskell代碼

所以我嘗試看起來像這樣：

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

這工作，但看起來不是很習慣。所以我正在尋找更優雅的解決方案。你有什麼建議嗎？

來源

2013-03-26 ipsec

您可以使用模式匹配，以減少使用的，如果......那麼......否則
另一個技巧是給一個號碼給您的變量，它讓你記住起始情況var0，爲你可以使用更好的遞歸調用var
最後一點，你有一些如果返回同樣的形式和共享相同的環境後謂詞相同的值，那麼你可以將它們組合在一起。

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)

改寫考慮到評論，

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

來源

2013-03-26 12:26:12 zurgl

擺脫對，使它'去XYN ...'，我會pn'綁定'到一個名稱（唐甚至不給編譯器一個重新計算它的機會），否則這就是我所要做的。簡單，清晰，高效。 – 2013-03-26 14:18:27

謝謝，取而代之的是你建議它絕對更好。無論如何，我必須承認，我對於使用let ...在綁定時猶豫不決，因爲我真的不知道在我的第二個模式匹配中，（p n）是否會計算兩次。如果我必須證明我的代碼是正確的，那麼我會認爲Haskell本質上是懶惰的，這意味着它的評估策略是按需呼叫，並且定義爲「按需呼叫是名稱呼叫的備忘錄版本」，那麼它應該沒問題，不是。誠然，按照您的建議使用允許綁定不會讓任何疑問的地方，我已經在我的下面添加了您的建議。 – zurgl 2013-03-26 16:00:53

我會用'where'。 'go x y n | n == 1 || n <= y = x | pn> y = go n pn（n-1）|否則=去x y（n-1）其中pn = p n'。 – 2013-03-26 16:03:56

好吧，讓我看看我是否正確地把我的大腦包裹起來......你說的p n < n對於所有有趣的n。並且您想爲x = n to 1計算p x，直到x變得小於迄今爲止所見最大的p x？

好吧，那樣子你會計算所有的p x作爲一個懶惰的名單。現在，問題已經減少到掃描這個列表，直到你找到你要找的東西。我會建議takeWhile，除了我們還需要折的列表才能找到當前的最大值。嗯，也許我們可以將每個值與運行最大值進行配對？

喜歡的東西

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

或類似的？

來源

2013-03-26 11:55:03 MathematicalOrchid

簡化遞歸的原地Haskell代碼

回答

相關問題