如何触发Data.Primitive.Array中fromListN的列表融合规则？

Hey, let's work through why your list fusion rules for fromListNArray aren't firing. I've debugged plenty of GHC rewrite rule issues before, so here's a breakdown of the key problems and fixes:

1. First: Your NOINLINE Pragma Is Blocking Fusion #

Your fromListNArray has a NOINLINE annotation, which stops GHC from expanding the function during optimization. List fusion (especially the foldr/build framework) relies on GHC being able to see through function definitions to match patterns like fromListNArray n (build f). That NOINLINE is almost certainly preventing your rule from matching.

Quick Fix for NOINLINE #

Either remove the NOINLINE entirely, or replace it with a phase-controlled INLINE pragma to let GHC expand the function at the right optimization stage:

{-# INLINE[2] fromListNArray #-}

This tells GHC to inline the function during phase 2 (right before most fusion rules are applied), giving your rewrite rule a chance to match.

2. Write a Rule That Directly Targets build #

List fusion works by replacing build-generated lists with direct computations. Your rule needs to match fromListNArray n (build f) and replace it with a version that fills the array without constructing the list first.

Here's a template for the correct rule structure:

{-# RULES "fromListNArray/build" forall !n f.
    fromListNArray n (build f) =
        createArray n fromListN_too_short $ \mi ->
            let fill i
                    | i >= n = return ()
                    | otherwise = 
                        -- Use the build function's logic to write elements directly
                        f (\x _ -> writeArray mi i x >> fill (i+1))
                          -- Handle early termination (too few elements)
                          (unless (i == n) fromListN_too_short)
            in fill 0
  #-}

Key details here:

• We use forall !n to match the strict n parameter in your original function (GHC is picky about matching strictness in rewrite rules).
• The f parameter from build has type forall b. (a -> b -> b) -> b -> b—we use it directly to write elements to the mutable array instead of building a list.
• We preserve the original error handling (fromListN_too_short/fromListN_too_long) to ensure the rule doesn't change the function's semantics (GHC skips rules that alter behavior).

3. Verify Error Handling Consistency #

Your original function throws fromListN_too_short if the list is too short, and fromListN_too_long if it's too long. Make sure your rule handles both cases correctly:

• For "too long" lists: once i >= n, we stop processing elements—this matches your original go function's behavior of throwing an error for extra elements.
• For "too short" lists: the base case of the f function triggers unless (i == n) fromListN_too_short, just like your original go i [] clause.

4. Debug with GHC's Rule Logs #

If the rule still isn't firing, use GHC's debugging flags to diagnose the issue. Compile your module with:

ghc -O2 -ddump-rule-firings -ddump-simpl YourModule.hs

• -ddump-rule-firings shows exactly which rules were applied (and which were skipped, with reasons like pattern mismatches or semantic differences).
• -ddump-simpl lets you inspect the Core code before/after optimization—you can check if your fromListNArray calls are being transformed as expected.

5. Avoid Common Pitfalls #

• List fusion only works for lists generated via build (most standard list functions like map/filter use build under the hood when optimizations are enabled). Test with map id [1..n] instead of literal lists to ensure the input is in build form.
• Keep your rule's right-hand side as close as possible to the original function's logic. GHC rejects rules that introduce unexpected side effects or change error behavior.

内容的提问来源于stack exchange，提问作者dfeuer