Does this Haskell function memoize?

Question

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?

you can add a [trace](https://hackage.haskell.org/package/base-4.9.0.0/docs/Debug-Trace.html#v:trace) to `length` (`length = trace "building..." $ V.fromList ...`) and see for yourself — Random Dev, Jul 03 '16 at 06:24
@Carsten Alternatively you could pass the `-ddump-simpl` option and look at the Core generated by the compiler, and check there. — Bakuriu, Jul 03 '16 at 07:56
@Bakuriu that's probably the *better* option yes - but then you have to understand the core ;) — Random Dev, Jul 03 '16 at 08:00
@Carsten Thanks. That's what I needed. If you can post as answer I'll accept. — rityzmon, Jul 05 '16 at 14:33

score 1 · Answer 1 · answered Jul 03 '16 at 09:35

1

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"

answered Jul 03 '16 at 09:35

Nikita Volkov

42,792
11
94
169

1

I believe he means "memoised in regards to the `lc` function" – Bergi Jul 03 '16 at 10:18
@Bergi Yes I did. Thanks for clarifying for me. I'm going to take this answer as meaning that the lc function would be memorized. – rityzmon Jul 05 '16 at 04:37

score 1 · Accepted Answer · answered Jul 05 '16 at 15:26

1

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

answered Jul 05 '16 at 15:26

Random Dev

51,810
9
92
119

Does this Haskell function memoize?

2 Answers2

Linked