{-# GHC_OPTIONS -O2 #-} {-# LANGUAGE BangPatterns #-} -- import Data.List (foldl') main = do a <- getLine ; b <- getLine ; print $ test2 (read a) (read b) {- using main = do [a,b]<- fmap read getLine ; print $ test a b SHOOTS time and memory consumption UP by full 10% - 15% for some reason but that's besides the point ----- I'm trying to encode simple nested loop: ----- test m n = let d = m+n-3 ; c = 0 ; pairs = [] in -- calculate some value and also for i in [0..m] -- selectively collect few results for j in [0..n] -- into a short buffer c += (j%3)==0 ? 2 : 1 -- increment counter if (i+j == d) append (i,j) AtEndOf pairs -- grow buffer at end, conditionally, return (c,pairs) -- by some rarily-succeeding test ----- thus only the final value of c is defined ----- but buffer may be consumed lazily, one-by-one, while being built -- so we have here two values calculated in one go, in parallel - -- where one is built from the top down (buffer), -- and the other from the bottom up (counter) -} test m n = let d = m + n - 3 in -- build a VERY short test buffer cross (sum,concat) $ unzip [ (c, [(i,j) | (i+j) == d ]) -- sample "rare" test | i<- [0..m], j<-[0..n], let c = if (rem j 3) == 0 then 2 else 1 ] cross (f,g) (x,y) = (f x,g y) {- > test 1000 1000 => (1336335,[(997,1000),(998,999),(999,998),(1000,997)]) => time: 0.56s memory: *** 45,728 kB *** > test 2000 2000 => (5338668,[(1997,2000),(1998,1999),(1999,1998),(2000,1997)]) => time: 2.51s memory: *** 222,848 kB *** ;; nested loop in CLISP as control case ;; takes constant space, as it should: -- http://i...content-available-to-author-only...e.com/ziw12 -- (test 1000 1000) => Run time: 0.336949 sec. Space: 5832 Bytes (test 2000 2000) => Run time: 1.37579 sec. Space: 5832 Bytes so clearly much interim storage is used unnecessarily in Haskell using FOLD or fused auxiliary functions does not help (not even FOLDL' works, which can only build whole buffer at once, in reversed order anyway) unless we use BANG_PATTERNS which are not even a part of the base language (!!!?!) -} -- here's unzip definition fused into it: test1 m n = cross (sum,id) $ foldr f ([0],[]) -- foldr f (0,[]) [ (c, [(i,j) | (i+j) == d ]) | i<- [0..m], j<-[0..n], let c = if (rem j 3) == 0 then 2 else 1 ] where d = m + n - 3 f (c1,h1) ~(c,h) = case h1 of []-> (c1:c,h) ; (x:_)->(c1:c,x:h) -- 0.32s-21.2MB / 1.24s-53.9MB -- f (c1,h1) ~(c,h) = (c1:c, case h1 of []-> h ; (x:_)-> x:h) -- 0.62s-63.1MB / 2.52s-245.4MB -- f (c1,h1) ~(c,h) = case h1 of []-> (c1+c,h) ; (x:_)->(c1+c,x:h) -- **0.77s-42.7MB STACK_OVER** -- f (c1,h1) ~(c,h) = case h1 of []-> (c+c1,h) ; (x:_)->(c+c1,x:h) -- **0.90s-48.8MB STACK_OVER** -- f (c1,h1) ~(c,h) = (c+c1, case h1 of []-> h ; (x:_)-> x:h) -- **0.94s-61.1MB STACK_OVER** -- so here clearly the buffer is recognized as being built lazily, -- and the space is wasted in the interim list to be reduced by 'sum', -- but when we try to fuse the definition of sum into it (as evident above) -- STACK OVERFLOW follows (!?!??) -- there shouldn't be any unnecessary interim storage used, -- explicit lists nor implicit stack frames; -- still memory leak's there in the best case, even whe we fuse -- the foldr definition itself, unless we use BANG PATTERNS: test2 m n = f 0 0 0 where d = m + n - 3 f i j !c -- !accumulate the counter | j > n && i >= m = (c,[]) | j > n = f (i+1) 0 c | True = let (c',h') = f i (j+1) (c + if (rem j 3) == 0 then 2 else 1) in if (i+j) == d then (c', (i,j):h') else (c',h') -- (without bang pattern it's a stack overflow!) -- NB with (c', if (i+j) == d then (i,j):h' else h') there's still a leak there {- test2: now constant, near-zero space 1000,1000 => (1336335,[(997,1000),(998,999),(999,998),(1000,997)]) time: 0.19s memory: 4764 kB 2000,2000 => (5338668,[(1997,2000),(1998,1999),(1999,1998),(2000,1997)]) time: 0.76s memory: 4764 kB -} test3 m n = f 0 0 0 [] -- accum_build the list, where d = m + n - 3 -- but in reversed order, and unnecessarily strictly f i j !c !h | j > n && i >= m = (c,h) | j > n = f (i+1) 0 c h | True = f i (j+1) (c + if (rem j 3) == 0 then 2 else 1) (if (i+j) == d then (i,j):h else h) -- for 1000,1000/2000,2000: time: 0.09s/0.37s memory: 3740 kB -- twice faster, 7/9 the memory footprint -- here's foldl reformulation of test3 test4 m n = foldl f (0,[]) [ (c, [(i,j) | (i+j) == d ]) | i<- [0..m], j<-[0..n], let c = if (rem j 3) == 0 then 2 else 1 ] where d = m + n - 3 f (!c,!h) (c1,h1) = case h1 of []->(c+c1, h) ; (x:_)->(c+c1, x:h) -- for 1000,1000/2000,2000: time: 0.12s/0.45s memory: 3740 kB -- no bang-pats -> stack overflow -- FOLDL' instead of FOLDL, w/out the bang -> 0.47s-74.4MB STACK OVERFLOW