haskell - How to make fromList lazy in this dynamic programming example? -

module main   import system.random   import data.foldable   import control.monad   import qualified data.map m   import qualified data.vector v   import debug.trace   import data.maybe   import data.ord    -- represents maximal integer. maxbound no because overflows.   -- ideally should 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]]           go :: int -> int -> int       go _ 0 = maxi       go 0 j = j       go 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 j = frommaybe maxi (m.lookup (i,j) cs)       ff l = --minimum l         case l of           l:ls -> if l < maxi l else ff ls           [] -> maxi        -- need make lazy somehow.       cs :: m.map (int, int) int       cs = m.fromlist [((i,j), go j) | <- [0..v.length ar - 1], j <- [0..maxi]]     main :: io ()   main =     --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 hackerrank candies challenge. think code correct in essence though gives me runtime errors on submission. hackerrank not errors are, because ran out allotted memory.

to make above work, need rewrite above fromlist gets lazily evaluated or effect. above form , rewriting functions pass along map parameter avoid.

i know haskell has various memoization libraries on hackage, online judge not allow use.

i might have coded myself hole due haskell's purity.

edit:

i did experimenting in order figure out how folds , lambda's work. think linked continuation passing after all, continuations being built along fold. show mean, i'll demonstrate simple program.

module main   trans :: [int] -> [int]   trans m =     foldr go (\_ -> []) m 0       go x f y = (x + y) : f x    main =     s <- return $ trans [1,2,3]     print s 

one thing surprised me when inserted print, got executed in reverse manner, left right, made me think @ first misunderstood how foldr works. turned out not case.

what above print out [1,3,5].

here explanation how executes. trying print out f x in above not informative , cause around place.

it starts this. fold 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 

the above not quite true. 1 has keep in mind fs 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 

also clarity 1 should instructive separate out 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 fold starts top. topmost statement gets evaluated as...

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

this reduces to:

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

the result unfinished lambda above. fold evaluates second statement.

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

this reduces to:

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

the fold goes last statement.

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

this reduces to:

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

the 0 outside fold gets applied , final lambda gets reduced to

1 : 3 : 5 : [] 

this start of it. case gets more interesting when f x replaced f y.

here similar program previous.

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

let me once again go top bottom.

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) 

the top statement.

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

the middle statement:

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

the 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 expressions build because ys cannot applied. after 0 gets inserted can whole expression 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 buildup due order of evaluation.

edit: so...

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

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

first foldr has travel of list before can begin. candi' depends on s , c variables cannot applied necessitates building continuations in last example.

then when 2 0 0 fed @ end of fold, whole thing gets evaluated.

it bit hard reason about.

the problem have linked has clean haskell solution using right folds. in other words, can skip worrying lazy fromlist, memoization , using more functional style.

the idea maintain list of (candy, score) pairs candy 0 (repeat 0 in bellow code). go once left right , bump candy values if item score exceeds 1 before:

-- s score , c candy of guy before -- if s < score guy should @ least c + 1 candies candy' = max candy $ if s < score c + 1 else 1 

and same thing again going in other direction:

import control.monad (replicatem) import control.applicative ((<$>))  solve :: [int] -> int solve = sum . map fst . loop . reverse . loop . zip  (repeat 0)         loop cs = foldr go (\_ _ -> []) cs 0 0     go (candy, score) f c s = (candy', score): f candy' score         candy' = max candy $ if s < score c + 1 else 1  main =     n <- read <$> getline     solve . fmap read <$> replicatem n getline >>= print 

this performs linearly, , passes tests on hackerrank.