Add this to your .cabal file It will save us from a pitfall.

common warnings
    ghc-options: -Werror=unbanged-strict-patterns

library
  import: warnings
  ...

executable myAwesomeProgram
  import: warnings

import Data.Map.Lazy -- it is fine, really.
import Data.Vector

type MyMap a = Map (ForcedWHNF Char) (ForcedNF (Maybe Vector))

-- Prompt removal of deleted elements.
type MyMap2 a = ForcedWHNF (Map (ForcedWHNF Char) (ForcedNF (Maybe Vector)))

This way it will be a type error to store a thunk that is keeping references alive.

1. Strictly let bound on your current context the result of a call to strictlyWHNF or strictlyNF. This is the most important part.
2. Use a lazy let to extract the underlying ForcedWHNF a or ForcedNF a with the paired extractor.
3. Store the previous result on the long lived data structure.

The ideal code piece looks like this:

import Data.Map.Lazy

type MyMap a = Map Char (ForcedNF (Maybe Int))

noThunksForWHNF :: IO ()
noThunksForWHNF = do
    let map0 :: ML.Map Char (ForcedWHNF Int)
        map0 = ML.empty

        -- Step 1. Strict let bound is done given the kind of
        -- StrictValueExtractor
        val0 :: StrictValueExtractor (ForcedWHNF Int)
        val0 = strictlyWHNF (const (2 + 2) map0)

        -- Step 2. The extractor is inside the Pairy constructor of val0
        val1 = case val0 of { Pairy v ext -> ext v }

        -- Step 3. Store as a lazy thunk without the references.
        map1 = ML.insert a val1 map0
    pure ()

Types that have kind UnliftedType have an different calling convention than normal values. To achieve the correct evaluation level:

1. We should bound with a name (let) computations that return a type with UnliftedType kind to the top level of our current context.
2. We must not inline computation with kind UnliftedType at use sites. Specially if the use site is inside of a lazy function.

The first kind of mistake is hard to trigger if we follow the first section rules. The library also steers you in the right direction by recommending the following stanza.

common warnings
    ghc-options: -Wall -Werror=unbanged-strict-patterns

on the cabal file of your project. It will protect your against this common error

noThunksForWHNF :: IO (ML.Map Char (Forced Int))
noThunksForWHNF = do
    let map0 :: ML.Map Char (ForcedWHNF Int)
        map0 = ML.empty

        -- Step 1 & 2 merged
        val0 :: StrictValueExtractor (ForcedWHNF Int)
        val0@(Pairy v ext) = strictlyWHNF (const (2 + 2) map0)

        -- Step 3. Store as a lazy thunk without the references.
        map1 = ML.insert a val1 map0
    pure map1

Now val0 merged steps 1 and 2. But in doing so it turned a strict let into a lazy let. The -Werror=unbanged-strict-patterns will highlight this at compile time and require you to put a BangPattern on val0.

The problem about inlining is hiding a strict computation inside of a lazy computation. So in the previous example

noThunksForWHNF :: IO (ML.Map Char (Forced Int))
noThunksForWHNF = do
    let map0 :: ML.Map Char (ForcedWHNF Int)
        map0 = ML.empty

        -- Step 1 & 2 merged
        val1= case strictlyWHNF (const (2 + 2) map0) of
                Pairy v ext -> ext

        -- Step 3. Store as a lazy thunk without the references.
        map1 = ML.insert a val1 map0
    pure map1

val1 has been bound by a lazy let. Top level bound plus explicit types in let bindings will help us to avoid this.

We need these so whenever we bound a strict computation, all the lazy values will be forced as needed.

The invariants of ForcedWHNF and ForcedNF depends on the constructors not being exported. The only way to construct these value is through the CBV functions. Pattern matching is done via a unidirectional pattern.