haskell - 有限双射的有效功能数据结构

我正在寻找一种能表示两种类型之间有限双射的功能数据结构，既节省空间又节省时间。

例如，如果考虑大小为n的双射f，我会很高兴:

用新的一对元素扩展f的复杂度为O(ln n)

查询f(x)或f ^ -1(x)具有复杂度O(ln n)

f的内部表示比具有2个有限映射(表示f及其逆向)的空间效率更高。

我知道排列的有效表示形式，例如this paper，但它似乎无法解决我的问题。

最佳答案

对于相对类似的问题，请查看my answer。 provided code可以处理一般的NxM关系，但也可以专门用于双射(就像对二叉搜索树一样)。

为了完整起见，将答案粘贴到此处: