I would like to evaluate a function to its normal form without applying it, for example,
\n -> n + sum [1..100]
should be evaluated to
\n -> n + 5050
But there's no NFData instance for functions, which is reasonable since we cannot obtain the subterms of a function.
I'm wondering if it's possible to fully normalize a function with the help of some compiler magic.
No, it is not possible. However, in most cases, it is not needed. I suspect that the trick you're missing is lifting the expensive calculations that don't depend on the output out via let. Compare:
-- recomputes `sum [1..100]` each time you apply it to an argument
f1 :: Int -> Int
f1 n = n + sum [1..100]
-- computes `sum [1..100]` just once, then uses the "cached" result each time
-- you apply it to an argument
f2 :: Int -> Int
f2 = let s = sum [1..100] in \n -> n + s
Function f1 is expensive every time you use it. Function f2 is expensive the first time you use it, but cheap every time thereafter.
(This answer is specific to GHC. Other compilers, if they some time exist, may behave differently.)