在Haskell中記錄多參數函數中的單個參數

我正在解決this programming problem，而我現在的解決方案超出了時間限制。我相信我的問題的解決方案是記憶。但是，我不明白備忘錄解決方案here。在Haskell中記錄多參數函數中的單個參數

這是我目前解決方案的主要功能。

maxCuts :: Int -> Int -> Int -> Int -> Int 
maxCuts n a b c 
    | n == 0 = 0 
    | n < 0  = -10000 
    | otherwise = max (max amax bmax) cmax 
    where 
     amax = 1 + maxCuts (n - a) a b c 
     bmax = 1 + maxCuts (n - b) a b c 
     cmax = 1 + maxCuts (n - c) a b c

如果b和c相對於n較小，則此函數運行時間過長。我只是複製他們用於階乘函數的解決方案，但該函數只需要一個參數。我有四個參數，但我只想在第一個參數n上鍵入記憶。請注意，ab和c在遞歸調用中不會更改。

來源

2016-09-08 Gaston Gilbert

做的僅僅是uncurry功能所以最簡單的事情，實際上，只有一個參數：'maxCuts ::（Int，Int，Int，Int） - > Int' – user2297560

重寫你的函數定義是這樣的：

maxCuts :: Int -> Int -> Int -> Int -> Int 
maxCuts n a b c = maxCuts' n where 
    maxCuts' n 
      | n == 0 = 0 
      | n < 0  = -10000 
      | otherwise = max (max amax bmax) cmax 
      where 
       amax = 1 + maxCuts' (n - a) 
       bmax = 1 + maxCuts' (n - b) 
       cmax = 1 + maxCuts' (n - c)

現在你有一個參數的功能，您可以memoize的。

來源

2016-09-08 16:10:48

另外：是不是你的算法只是計算像div n (minimum [a,b,c])？

正如您所指出的，參數a，b和c不會改變，所以首先重寫函數以將參數n放在最後。

如果你決定使用一個列表來memoize的函數值它需要一點點的關心，以確保GHC將保存映射表：

import Debug.Trace 

maxCuts' :: Int -> Int -> Int -> Int -> Int 
maxCuts' a b c n = memoized_go n 
    where 
    memoized_go n 
     | n < 0 = -10000 
     | otherwise = mapped_list !! n 

    mapped_list = map go [0..] 

    go n | trace msg False = undefined 
     where msg = "go called for " ++ show n 
    go 0 = 0 
    go n = maximum [amax, bmax, cmax] 
     where 
     amax = 1 + memoized_go (n-a) 
     bmax = 1 + memoized_go (n-b) 
     cmax = 1 + memoized_go (n-c) 

test1 = print $ maxCuts' 1 2 3 10

註定義的循環依賴：memoized_go取決於mapped_list這取決於go這取決於memozied_go。

由於列表只允許非負數索引，因此n < 0必須是以獨立的警戒模式處理。

trace調用顯示go僅在每個值爲n時調用一次。例如，考慮嘗試這樣做沒有定義mapped_list：

maxCuts2 :: Int -> Int -> Int -> Int -> Int 
maxCuts2 a b c n = memoized_go n 
    where 
    memoized_go n 
     | n < 0 = -10000 
     | otherwise = (map go [0..]) !! n 
    -- mapped_list = map go [0..] 
    go n | trace msg False = undefined 
     where msg = "go called for " ++ show n 
    go 0 = 0 
    go n = maximum [amax, bmax, cmax] 
     where 
     amax = 1 + memoized_go (n-a) 
     bmax = 1 + memoized_go (n-b) 
     cmax = 1 + memoized_go (n-c) 

test2 = print $ maxCuts2 1 2 3 11

運行test2顯示go被調用的n相同的值多次。

更新

爲了避免產生大的未計算的thunk，我會用BangPatterns 爲amax，bmax和cmax：

{-# LANGUAGE BangPatterns #-} 

maxCuts' ... = 
    ... 
    where 
    !amax = 1 + ... 
    !bmax = 1 + ... 
    !cmax = 1 + ...

來源

2016-09-08 16:17:38 ErikR

在Haskell中記錄多參數函數中的單個參數

回答

相關問題