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

概述这个问题 我想创建一个数据类型,允许快速访问和修改其元素.是否有可能在Haskell中创建一个结构和函数,它的执行速度与简单的C实现一样快？ 问题详情 我正在Haskell中编写一个编译器.我有一个数据类型代表AST,让我们考虑以下一个： import Prelude hiding (id)-- this is a sample data type, the real one has got 这个问题

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

问题详情

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

import Prelude hIDing (ID)-- this is a sample data type,the real one has got a lot of constructorsdata 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)中没有任何限制地修改它的元素.

解决方法 我认为拉链实际上总是可以接受的,你听说过 differentiation吗？

好吧,关于getByID,我不确定这是个好主意.你可能想要一个像getByID :: Int – >这样的Haskell函数. IO AST在数组或其他东西中使用查找.但是,由于您以后希望能够修改值(至少在概念上),您是否希望getByID返回新修改的AST值或存储的第一个AST值？这一切都成了问题.看看你是否可以删除你的haskell版本的ID可能是一个好主意.

我认为你的专注听起来很可行.如果我们说ZAST是AST的zipper数据类型.然后你也许会有类似的东西.

makeFocus :: ZAST -> Focus ZASTtype Focus =  (ZAST -> ZAST) -> -- The modifIEr of the "below part"  ZAST ->           -- The new "above part",you have to provIDe it again as it might have changed  ZAST              -- The Result

但是,它并不像C方式那么方便.

总而言之,我认为你应该退后一步,看看你实际上要做的事情(AST优化,发射装配等)是否可以通过不可变数据结构有效地完成.而不是试图在Haskell中尝试实现可变C数据结构的相同规范.

总结

以上是内存溢出为你收集整理的c – 在Haskell中使用O(1)元素访问实现高效的拉链,如数据结构全部内容，希望文章能够帮你解决c – 在Haskell中使用O(1)元素访问实现高效的拉链,如数据结构所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。