Memoization for subsequent fold calls

I'm looking for a technique that allows for memoization between subsequent fold calls against the lists that is being prepended.

I looked at memoize library but this doesn't seem to support memoization of higher-order functions, which is the case for folds.

I also tried the technique with lazy evaluated map of results but to no avail.

Here's simple example code:

module Main where

import Data.Time

printAndMeasureTime :: Show a => a -> IO ()
printAndMeasureTime a = do
startTime <- getCurrentTime
print a
stopTime <- getCurrentTime
putStrLn $ " in " ++ show (diffUTCTime stopTime startTime)

main = do
let as = replicate 10000000 1
printAndMeasureTime $ foldr (-) 0 as -- just to resolve thunks
printAndMeasureTime $ sum as
printAndMeasureTime $ sum (1:as) -- recomputed from scratch, could it reuse previous computation result?
printAndMeasureTime $ length (as)
printAndMeasureTime $ length (1:as) -- recomputed from scratch, could it reuse previous computation result?


and the output:

0
in 1.125098223s
10000000
in 0.096558168s
10000001
in 0.104047058s
10000000
in 0.037727126s
10000001
in 0.041266456s


Times suggest that folds are computed from scratch. Is there a way to make the subsequent folds reuse previous fold results?

1 Answer
1

Make a data type!

module List (List, _elements, _sum, _length, toList, cons) where

data List = List
{ _elements :: [Int]
, _sum :: !Int
, _length :: !Int
}

toList :: [Int] -> List
toList xs = List xs (sum xs) (length xs)

cons :: Int -> List -> List
cons x (List xs t n) = List (x:xs) (x+t) (1+n)


Note that the List type is exported, but the List constructor is not, so that the only way to construct a List is using the toList function (commonly called a "smart constructor").

List

List

List

toList

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.