在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中记录多参数函数中的单个参数

回答

相关问题