c – 在Haskell中使用O(1)元素访问实现高效的拉链,如数据结构

我想创建一个数据类型,允许快速访问和修改其元素.是否有可能在Haskell中创建一个结构和函数,它的执行速度与简单的C实现一样快？

问题详情

我正在Haskell中编写一个编译器.我有一个数据类型代表AST,让我们考虑以下一个：

import Prelude hiding (id)

-- this is a sample data type,the real one has got a lot of constructors
data AST = A { id :: Int,x :: AST,y :: AST,z :: AST }
         | B { id :: Int }
         | C { id :: Int,y :: AST }
         | D { id :: Int,u :: AST,v :: AST,w :: AST}

每个AST节点都有一个唯一的标识符.我希望在Haskell中实现以下功能：

>函数getById,它将返回O(1)时间复杂度中选择id的AST节点.
>能够在结构上创建“焦点”并相互独立地修改焦点元素.因此,我希望能够记住对某些子树的关注,并能够在O(1)时间复杂度中修改每个这样的焦点.

我在考虑Zippers,但它们有3个问题：

>它们(据我所知)使用简单的数据类型,如二叉树,我们可以说,我们选择“左”或“右”分支.是否有任何简单的方法在复杂的数据类型上使用它们,如上所述？
>我认为他们不允许我实现具有O(1)时间复杂度的函数getById,对吗？
>我认为使用Zippers创建一些独立的焦点是不可能的.通过独立焦点,我的意思是焦点,这将允许我们修改数据类型的不同部分,而无需重新计算其他焦点(在O(1)中).

C的思维方式

在C中,我们将能够创建指向AST节点nodePtrs的指针数组.函数nodeById将在O(1)中执行,只需访问*(nodePtrs [id])即可.因为C结构是可变的,所以我们能够在O(1)中没有任何限制地修改它的元素.