通过代数定律分析 API 设计 :: 合理多态

主要观点:讨论了 Data.Map 函数 unionWithintersectionWith 的类型差异及相关实现问题,从 API 设计和高效实现的角度进行探究,重新审视 Map 的概念及 unionWith 的类型,分析不同实现方式的效率和可行性。
关键信息:

  • 提出 unionWith 不同值类型的可能类型,如 unionWith :: (Maybe a -> Maybe b -> c) -> Map k a -> Map k b -> Map k c,但存在局限性。
  • 从哲学角度思考“什么是映射”,将 Map k v 视为 k -> Maybe v 的高效实现,推广为 Monoid v => k -> v,使 lookup 符合半群同态。
  • 重新评估 unionWith 的类型为 unionWith :: (a -> b -> c) -> Map k a -> Map k b -> Map k c,与 liftA2 相似,但存在实现问题。
  • 给出 Map 的新数据结构 data Map k v = Map {defaultValue :: v, implementation :: Data.Map.Map k v} 及其 unionWith 的实现,遇到半群同态时效率问题更复杂。
    重要细节:
  • 分析了在新的 Map 结构下实现 unionWith 时遇到的问题,如无论查找哪个键都返回固定值 nontrivial,只能通过关联每个键或保留默认值来解决,且保留默认值在 Data.Map.Map 的平衡二叉搜索树实现中较难高效处理。
  • 得出 Data.Map.Map 没有 Applicative 实例的原因是即使能约束结果也无法高效实现,通过观察明显的定律和代入特殊输入来思考高效答案所需的条件,未查看 Data.Map 的实现代码仅从理论角度进行分析。
阅读 15
0 条评论