CODEWITHSUNDEEP
haskellmemoization
rityzmon
rityzmon

Reputation: 1965

Does this Haskell function memoize?

I'd like to pre-calculate some values that are then used when I need to do further lookups. I came up with the following:

import qualified Data.Vector.Unboxed as V

lcgen s =
  lc
  where
    lc 0 b  = lengths V.! b
    lc a b  = lengths V.! b - lengths V.! (a - 1) - 1
    lengths = V.fromList $ scanl1 ((+) . (1 +)) $ map length $ words s

The function essentially returns the number of characters used in-between two words. I use it as follows:

let lc = lcgen "some sentence with a lot of words"
lc 0 0 -- == 4
lc 0 1 -- == 13

In this implementation, would the lengths vector be memoized? Furthermore, how can I know and/or confirm this?

Upvotes: 2

Views: 178

Answers (2)

Random Dev
Random Dev

Reputation: 52300

if you add a trace to your lengths like this:

lengths = trace "building list..." $ V.fromList ...

you will see the output every time the lengths value is calculated

As it is it should only be evaluated/build once per lc = lcgen s

Upvotes: 1

Nikita Volkov
Nikita Volkov

Reputation: 43360

In this case lengths clearly cannot be memoized, because it depends on the outer function's argument, which is why it is regenerated each time you call that function.

It could have been memoized if there was no such dependency. To check whether that happened you could use one of the methods suggested in the comments. To ensure that the memoization did happen, you could have used the standard approach of extracting the desired piece to the top level with the NOINLINE pragma. E.g.,

{-# NOINLINE lengths #-}
lengths :: Vector Int
lengths =
  error "define me"

Upvotes: 1

Related Questions