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 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
不导出Data.Map.Tip
和Data.Map.Bin
,除非启用TESTING
,我不知道如何启用TESTING
,请参见:
https://hackage.haskell.org/package/containers-0.4.0.0/docs/src/Data-Map.html
1条答案
按热度按时间bxfogqkk1#
编译
findWithDefault
时,对lookup
的调用将被内联,这将导致Maybe
被删除。使用containers
包中的实际代码来证明这一点有点困难,但您可以在以下简化的、自包含的示例中看到这一点:如果使用
ghc -O2 -fforce-recomp -ddump-simpl -dsuppress-all -dsuppress-uniques MyMap.hs
编译该代码,您会发现为myFindWithDefault
生成了以下内核:注意,这里没有调用
myLookup
,也没有涉及Just
、Nothing
或Maybe
。并使用相同的标志重新编译,您可能会惊讶地发现,针对
myOptimizedFindWithDefault
的GHC编译代码如下所示:GHC不仅自动优化原始的
myFindWithDefault
,而且它足够聪明,能够确定“难以置信的愚蠢”和手动优化的定义是等价的,并且它消除了重复的代码。因此,即使
Data.Map
中的findWithDefault
定义“愚蠢得令人难以置信”,但聪明得令人难以置信的GHC编译器弥补了这一点,而且没有特别的理由去尝试优化它。然而,回到你的问题上,当你试图修改一个包时,作者不明智地决定将内部结构保留在内部,你会陷入困境。看看
containers-0.4.0.0
的源代码,启用TESTING
的唯一方法是使用-DTESTING
标志重新编译Data.Map
。如果你无论如何都要重新编译Data.Map
,你也可以直接修改findWithDefault
的定义,你实际安装修改后的包的方法取决于你如何管理你的Haskell安装和Haskell项目。幸运的是,正如评论中所指出的,
containers
的最新版本在适当命名的模块中导出内部组件,因此这可能是最好的方法。不过,正如注解中 * 也 * 指出的那样,在容器的后续版本中,
findWithDefault
的定义已经被重写,大致如下所示: