如何实现更高效的Data.Map.findWithDefault？遇构造函数导出难题

现有Data.Map.findWithDefault的实现如下：

findWithDefault :: Ord k => a -> k -> Map k a -> a
findWithDefault def k m = case lookup k m of
    Nothing -> def
    Just x  -> x

该实现因生成并匹配Maybe值被认为效率低下。我尝试自行实现lookup逻辑以避免Maybe开销：

lookup k = k `seq` go
   where
      go Data.Map.Tip = (0,0,0,0)
      go (Data.Map.Bin _ kx x l r) =
         case compare k kx of
            LT -> go l
            GT -> go r
            EQ -> x

但Data.Map未导出Tip和Bin构造函数，仅在开启TESTING标志时才会导出，不清楚如何开启该标志。

开启TESTING编译标志的方法 #

要访问Data.Map的内部构造函数，需通过以下方式开启TESTING预编译标志：

• GHC命令行编译：直接在编译命令中添加-DTESTING参数：

  ghc -DTESTING YourModule.hs
  

• Cabal项目配置：在项目的.cabal文件中，给目标组件（可执行文件或库）添加ghc-options配置：

  executable your-app
    main-is: Main.hs
    build-depends: base >=4.14, containers
    ghc-options: -DTESTING
  

• Stack项目配置：可以在stack.yaml的ghc-options字段中添加-DTESTING，或者直接修改.cabal文件的对应配置。

不推荐依赖TESTING标志的注意事项 #

虽然开启该标志能拿到内部构造函数，但生产代码中不建议这么做：

• 内部实现不稳定：Tip和Bin是Data.Map的未公开实现细节，后续版本的containers库可能随时修改这些构造函数的定义，导致代码无法编译。
• GHC优化可消除Maybe开销：开启GHC的-O2优化后，原有的findWithDefault实现中Maybe类型带来的额外开销会被编译器消除，性能表现和手动实现的版本差距极小。
• 可用公开API替代：如果确实需要避免Maybe的中间值，可使用Data.Map提供的公开函数，比如find（找不到键时抛出异常，需谨慎使用），或者结合lookupLE/lookupGE实现自定义逻辑。

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