How to make fromList lazy in this dynamic programming example?

Question

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 ij = 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 lij = 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 ij) | 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 

The above code is for HackerRank Candies . I think the code is essentially correct, although it gives me runtime errors on presentation. HackerRank does not say what these errors are, but most likely it is because I have run out of allocated memory.

In order to do the above work, I need to rewrite the above so that fromList gets a lazy rating or something like that. I like the above form and rewriting the functions so that they go around the map, as a parameter is something that I really would like to avoid.

I know that Haskell has various memoization libraries for Hackage, but an online judge does not allow them to be used.

I could encode myself into a hole due to the purity of Haskell.

Edit:

I experimented to figure out how these folds and lambda work. I think this is definitely related to the continuation, which runs in the end, since the continuations are built along the crease. To show what I mean, I will demonstrate this with a simple program.

 module Main where trans :: [Int] -> [Int] trans m = foldr go (\_ -> []) m 0 where go xfy = (x + y) : fx main = do s <- return $ trans [1,2,3] print s 

One thing that surprised me was that when I inserted the seal, it was done in the reverse order, from left to right, which made me think that I misunderstood how folding works. This turned out to be wrong.

What this means is a printout [1,3,5] .

Here is an explanation of how it is performed. Trying to print fx in the above example will not be informative and will result in it just everywhere.

It starts with something like that. The grid obviously performs the functions of 3 go .

 go xfy = (x + y) : fx go xfy = (x + y) : fx go xfy = (x + y) : fx 

The above is not entirely true. It must be borne in mind that all f are distinct.

 go x f'' y = (x + y) : f'' x go xf' y = (x + y) : f' x go xfy = (x + y) : fx 

Also for clarity, it is also instructive to separate lambdas.

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

Now dropping begins from above. The topmost operator is rated as ...

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

It comes down to:

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

The result is an incomplete lambda above. Now the convolution evaluates the second statement.

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

It comes down to:

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

The summary goes to the last statement.

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

It comes down to:

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

0 is applied outside the crease, and the final lambda is reduced to

 1 : 3 : 5 : [] 

This is just the beginning. The case becomes more interesting when fx is replaced by fy .

Here is a similar program for the previous one.

 module Main where trans :: [Int] -> [Int] trans m = foldr go (\_ -> []) m 1 where go xfy = (x + y) : f (2*y+1) main = do s <- return $ trans [1,2,3] print s 

Let me go from top to bottom again.

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

Top operator.

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

Middle operator:

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

Last statement:

 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 

Notice how the expressions are expressed, since y cannot be applied. Only after 0 is 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 : [] 

In order of evaluation, there is an increase.

Edit: So ...

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

The above 3 actually goes through the list at each iteration.

The first foldr should go to the beginning of the list before it begins. While candi' depends on the variables s and c , which cannot be applied immediately, this requires the creation of continuations, as in this last example.

Then, when two 0 0 are fed to the end of the fold, all this is only then evaluated.

It’s a little difficult to reason.

Answer 1

The problem you are having has a clean Haskell solution using the correct folds. In other words, you don’t have to worry about lazy fromList, memoization and all this, just using a more functional style.

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

 -- 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 repeat the same 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) fcs = (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 

This runs linearly and passes all tests on HackerRank.

Answer 2

As for my own question at the top, probably the way to make this lazy is to just use a list (list of lists or list vector). The reason why the above cannot be made lazy because the type of card is lazy in values ​​and builds keys.

More importantly, my analysis of the fact that the fold does essentially two passes was completely correct. The way executable continuations execute in the reverse order completely confused me, but I adapted the @ behzad.nouri code to work with only one loop.

 module Main where import Control.Monad (replicateM) import Control.Applicative ((<$>)) import Debug.Trace solve :: [Int] -> Int solve = sum . loop where loop :: [Int] -> [Int] loop = (\(_,_,x) -> x 0 0) . foldr go (0, 0, \_ _ -> []) go :: Int -> (Int, Int, Int -> Int -> [Int]) -> (Int, Int, Int -> Int -> [Int]) go score (candyP,scoreP,f) = let candyP' = if scoreP < score then candyP + 1 else 1 in (candyP', score, \candyN scoreN -> let candy' = max candyP' $ if scoreN < score then candyN + 1 else 1 in candy' : f candy' score) -- This part could be replaced with a sum main = do n <- read <$> getLine solve . fmap read <$> replicateM n getLine >>= print 

The above tests are all without problems, and this convincingly proves the correctness of the above analysis.