在这个动态编程示例中，如何使fromList变得懒惰? [英] How to make fromList lazy in this dynamic programming example?

问题描述

module Main where
  import System.Random
  import Data.Foldable
  import Control.Monad
  import qualified Data.Map as M
  import qualified Data.Vector as V
  import Debug.Trace
  import Data.Maybe
  import Data.Ord

  -- Represents the maximal integer. maxBound is no good because it overflows.
  -- Ideally should be something like a billion.
  maxi = 1000

  candies :: V.Vector Int -> Int --M.Map (Int, Int) Int
  candies ar = ff [l (V.length ar - 1) x | x <- [0..maxi]]
    where
      go :: Int -> Int -> Int
      go _ 0 = maxi
      go 0 j = j
      go i j =
        case compare (ar V.! (i-1)) (ar V.! i) of
          LT -> ff [l (i-1) x + j | x <- [0..j-1]]
          GT -> ff [l (i-1) x + j | x <- [j+1..maxi]]
          EQ -> ff [l (i-1) x + j | x <- [0..maxi]]
      l :: Int -> Int -> Int
      l i j = fromMaybe maxi (M.lookup (i,j) cs)
      ff l = --minimum l
        case l of
          l:ls -> if l < maxi then l else ff ls
          [] -> maxi

      -- I need to make this lazy somehow.
      cs :: M.Map (Int, Int) Int
      cs = M.fromList [((i,j), go i j) | i <- [0..V.length ar - 1], j <- [0..maxi]]


  main :: IO ()
  main = do
    --ar <- fmap (V.fromList . map read . tail . words) getContents
    g <- fmap (V.fromList . take 5 . randomRs (1,50)) getStdGen
    print $ candies g

上面的代码适用于 HackerRank Candies 挑战.我认为代码本质上是正确的，即使它在提交时给了我运行时错误. HackerRank并没有说明这些错误是什么，但是很可能是因为我用完了分配的内存.

The above code is for the HackerRank Candies challenge. I think the code is correct in essence even though it gives me runtime errors on submission. HackerRank does not say what those errors are, but most likely it is because I ran out allotted memory.

要使上述工作正常进行，我需要重写上面的内容，以便fromList可以被懒惰地评估或达到某种效果.我喜欢上面的形式并重写函数，以便它们作为参数传递给地图，这是我非常想避免的事情.

To make the above work, I need to rewrite the above so the fromList gets lazily evaluated or something to that effect. I like the above form and rewriting the functions so they pass along the map as a parameter is something I would very much like to avoid.

我知道Haskell在Hackage上有各种记忆库，但是在线法官不允许使用它们.

I know Haskell has various memoization libraries on Hackage, but the online judge does not allow their use.

由于Haskell的纯洁，我可能已经将自己编码成一个洞.

I might have coded myself into a hole due to Haskell's purity.

我做了一些实验，以弄清楚这些褶皱和lambda的工作方式.我认为，这毕竟与延续性的传递肯定相关，因为延续性是在褶皱中逐渐形成的.为了说明我的意思，我将通过一个简单的程序对其进行演示.

I did some experimenting in order to figure out how those folds and lambda's work. I think this is definitely linked to continuation passing after all, as the continuations are being built up along the fold. To show what I mean, I'll demonstrate it with a simple program.

module Main where
  trans :: [Int] -> [Int]
  trans m =
    foldr go (\_ -> []) m 0 where
      go x f y = (x + y) : f x

  main = do
    s <- return $ trans [1,2,3]
    print s

令我惊讶的是，当我插入打印件时，它以相反的方式从左到右执行，这使我起初以为我误解了文件夹的工作方式.事实并非如此.

One thing that surprised me was that when I inserted a print, it got executed in a reverse manner, from left to right, which made me think at first that I misunderstood how foldr works. That turned out to not be the case.

上面的操作是打印出[1,3,5].

这是它如何执行的说明.尝试在上面打印出f x并不能提供足够的信息，只会使它遍及整个地方.

Here is the explanation how it executes. Trying to print out f x in the above will not be informative and will cause it to just all around the place.

它始于这样的东西.折叠显然执行了3个go函数.

It starts with something like this. The fold obviously executes 3 go functions.

go x f y = (x + y) : f x
go x f y = (x + y) : f x
go x f y = (x + y) : f x

以上内容并不完全正确.必须记住，所有f都是独立的.

The above is not quite true. One has to keep in mind that all fs are separate.

go x f'' y = (x + y) : f'' x
go x f' y = (x + y) : f' x
go x f y = (x + y) : f x

为了清楚起见，分离出lambda也应该是有益的.

Also for clarity one it should also be instructive to separate out the lambdas.

go x f'' = \y -> (x + y) : f'' x
go x f' = \y -> (x + y) : f' x
go x f = \y -> (x + y) : f x

现在，折痕从顶部开始.最上面的语句被评估为...

Now the fold starts from the top. The topmost statement gets evaluated as...

go 3 (\_ -> []) = \y -> (3 + y) : (\_ -> []) 3

这减少为:

go 3 (\_ -> []) = (\y -> (3 + y) : [])

结果是上面未完成的lambda.现在，首屏对第二条语句进行评估.

The result is the unfinished lambda above. Now the fold evaluates the second statement.

go 2 (\y -> (3 + y) : []) = \y -> (2 + y) : (\y -> (3 + y) : []) 2

这减少为:

go 2 (\y -> (3 + y) : []) = (\y -> (2 + y) : 5 : [])

弃牌进入最后一个陈述.

The the fold goes to the last statement.

go 1 (\y -> (2 + y) : 5 : []) = \y -> (1 + y) : (\y -> (2 + y) : 5 : []) 1

这减少为:

go 1 (\y -> (2 + y) : 5 : []) = \y -> (1 + y) : 3 : 5 : []

首屏外的0被应用，最后的lambda被减少为

The the 0 outside the fold gets applied and the final lambda gets reduced to

1 : 3 : 5 : []

这仅仅是开始.当f x替换为f y时，情况变得更加有趣.

This is just the start of it. The case gets more interesting when f x is replaced with f y.

这是与以前类似的程序.

Here is a similar program to the previous.

module Main where
  trans :: [Int] -> [Int]
  trans m =
    foldr go (\_ -> []) m 1 where
      go x f y = (x + y) : f (2*y+1)

  main = do
    s <- return $ trans [1,2,3]
    print s

让我再次从上到下

go x f'' = \y -> (x + y) : f'' (2*y+1)
go x f' = \y -> (x + y) : f' (2*y+1)
go x f = \y -> (x + y) : f (2*y+1)

最重要的声明.

go 3 (\_ -> []) = \y -> (3 + y) : (\_ -> []) (2*y+1)

中间语句:

go 2 (\y -> (3 + y) : (\_ -> []) (2*y+1)) = \y -> (2 + y) : (\y -> (3 + y) : (\_ -> []) (2*y+1)) (2*y+1)

最后一条语句:

go 1 (\y -> (2 + y) : (\y -> (3 + y) : (\_ -> []) (2*y+1)) (2*y+1)) = \y -> (1 + y) : (\y -> (2 + y) : (\y -> (3 + y) : (\_ -> []) (2*y+1)) (2*y+1)) 2*y+1

请注意表达式的构建方式，因为无法应用y.只有插入0后，才能对整个表达式求值.

Notice how the expressions build up because ys cannot be applied. Only after the 0 gets inserted can the whole expression be evaluated.

(\y -> (1 + y) : (\y -> (2 + y) : (\y -> (3 + y) : (\_ -> []) (2*y+1)) (2*y+1)) 2*y+1) 1

2 : (\y -> (2 + y) : (\y -> (3 + y) : (\_ -> []) (2*y+1)) (2*y+1)) 3

2 : 5 : (\y -> (3 + y) : (\_ -> []) (2*y+1)) 7

2 : 5 : 10 : (\_ -> []) 15

2 : 5 : 10 : []

由于评估的顺序，有一些积累.

There is a buildup due to the order of evaluation.

所以...

go (candy, score) f c s = (candy', score): f candy' score
    where candy' = max candy $ if s < score then c + 1 else 1

实际上，上面的每次迭代在列表中进行了3次传递.

The above in fact does 3 passes across the list in each iteration.

第一个文件夹必须先移动到列表的后面，然后才能开始.然后，由于candi'依赖于无法立即应用的s和c变量，因此有必要像上一个示例中那样建立延续.

First foldr has to travel to back of the list before it can begin. Then as candi' depends on s and c variables which cannot be applied immediately this necessitates building up the continuations as in that last example.

然后，在折叠结束时将两个0 0送入时，整个东西才被评估.

Then when the two 0 0 are fed into at the end of the fold, the whole thing only then gets evaluated.

这很难推理.

推荐答案

您链接到的问题具有使用正确折叠的干净的Haskell解决方案.换句话说，您只需使用更具功能性的样式，就无需担心懒惰的fromList，备忘录和所有这些内容.

The problem you have linked to has a clean Haskell solution using right folds. In other words, you can skip worrying about lazy fromList, memoization and all that by just using a more functional style.

这个想法是，您维护一个(candy, score)对的列表，其中所有初始candy为零(以下代码中的repeat 0).然后，如果该项目得分超过之前的得分，则从左向右移动一次并增大candy值:

The idea is that you maintain a list of (candy, score) pairs where candy is zero initially for all (repeat 0 in bellow code). Then you go once from left to right and bump up candy values if this item score exceeds the one before:

-- s is the score and c is the candy of the guy before
-- if s < score then this guy should get at least c + 1 candies
candy' = max candy $ if s < score then c + 1 else 1

并再次朝另一方向做同样的事情:

and do the same thing again going in the other direction:

import Control.Monad (replicateM)
import Control.Applicative ((<$>))

solve :: [Int] -> Int
solve = sum . map fst . loop . reverse . loop . zip  (repeat 0)
    where
    loop cs = foldr go (\_ _ -> []) cs 0 0
    go (candy, score) f c s = (candy', score): f candy' score
        where candy' = max candy $ if s < score then c + 1 else 1

main = do
    n <- read <$> getLine
    solve . fmap read <$> replicateM n getLine >>= print

这会线性执行，并通过HackerRank上的所有测试.

This performs linearly, and passes all tests on HackerRank.

这篇关于在这个动态编程示例中，如何使fromList变得懒惰?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！