haskell - 有限双射的高效函数数据结构

Question

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

例如，如果考虑大小为 n 的双射 f:

• 用一对新元素扩展 f 的复杂度为 O(ln n)
• 查询 f(x) 或 f^-1(x) 的复杂度为 O(ln n)
• f 的内部表示比 2 个有限映射(表示 f 及其逆)更节省空间

我知道排列的有效表示，例如 this paper ，但这似乎并没有解决我的问题。

Answer 1

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

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

The simplest way is to use a pair of unidirectional maps. It has some cost, but you won't get much better (you could get a bit better using dedicated binary trees, but you have a huge complexity cost to pay if you have to implement it yourself). In essence, lookups will be just as fast, but addition and deletion will be twice as slow. Which isn't so bad for a logarithmic operation. Another advantage of this technique is that you can use specialized maps types for the key or value type if you have one available. You won't get as much flexibility with a specific generalist data structure.

A different solution is to use a quadtree (instead of considering a NxN relation as a pair of 1xN and Nx1 relations, you see it as a set of elements in the cartesian product (Key*Value) of your types, that is, a spatial plane), but it's not clear to me that the time and memory costs are better than with two maps. I suppose it needs to be tested.