关于 scala：如何在 Haskell 中创建相互引用的数据结构？

How to create mutually referencing data structures in Haskell?

我利用了这样一个事实，即当 JVM 创建一个对象(不可变或不可变)时，它的指针是在其字段初始化之前创建的。

这让我可以创建这样的东西：

1
2
3
4
5

class BackRefdNode(val parent:Option[BackRefdNode],
node:ClassicNode){
val children=node.children.map{c=>
new BackRefdNode(Some(this), c)
}

Haskell 不是这种情况(据我所知)，如果是这种情况，Haskell 不会给我工具来利用它(我没有提到”this”)。

所以我想知道，我如何在 Haskell 中实现这一点？

我认为也许 th fix 函数可以解决问题，但这实际上不会给我一个”this”引用，而是一个对 thunk 的引用，在计算时，理论上它的结构与创建了 BackRefdNode

相关讨论

Haskell 确实允许使用 let 进行循环引用。
相关：如何实现双向链表

Haskell 实际上在这里更进一步。它是惰性求值的，这意味着您可以在初始化之前获得对任何东西的引用，而不仅仅是带有字段的对象。使用数据类型

1 2	data ClassicNode = ClassicNode { children :: [ClassicNode] } data BackRefdNode = BackRefdNode { parent :: Maybe BackRefdNode, children :: [BackRefdNode] }

你可以创建一个函数

1
2
3

backRefdNode :: Maybe BackRefdNode –> ClassicNode –> BackRefdNode
backRefdNode parent node = let result = BackRefdNode parent (backRefdNode result <$> children node)
in result

请注意在初始化 result 本身的表达式中如何引用 result。这可以很好地工作并且有效地共享具有循环引用的树对象。

比 Scala 更难的是解开这种数据结构，因为 Haskell 中没有参考 eq 实体。 BackRefdNode 的每个孩子都将其作为其父母的不变量无法测试，必须从构造中证明。

不是 Scala 代码

1
2
3
4
5
6
7
8
9
10

trait ClassicNode {
def children: List[ClassicNode]
}

class BackRefdNode(val parent: Option[BackRefdNode],
node: ClassicNode) {
val children = node.children.map { c =>
new BackRefdNode(Some(this), c)
}
}

类似于 Haskell 代码

1
2
3
4
5
6
7
8
9

data ClassicNode

data BackRefdNode = BRN { parent :: Maybe BackRefdNode, node :: ClassicNode }

children1 :: ClassicNode –> [ClassicNode]
children1 _ = undefined

children :: BackRefdNode –> [BackRefdNode]
children this = map (\\c –> BRN (Just this) c) (children1 (node this))

或者使用 Haskell 中的类型类

1
2
3
4
5
6
7
8
9
10
11
12

class GetChildren a where
children :: a –> [a]

data ClassicNode

data BackRefdNode = BRN { parent :: Maybe BackRefdNode, node :: ClassicNode }

instance GetChildren ClassicNode where
children _ = undefined

instance GetChildren BackRefdNode where
children this = map (\\c –> BRN (Just this) c) (children (node this))

即双重翻译成 Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

trait ClassicNode

class BackRefdNode(val parent: Option[BackRefdNode],
val node: ClassicNode)

trait GetChildren[A] {
def children(a: A): List[A]
}
object GetChildren {
implicit val classicNodeGetChildren: GetChildren[ClassicNode] = _ => ???
implicit val backRefdNodeGetChildren: GetChildren[BackRefdNode] = a =>
a.node.children.map { c =>
new BackRefdNode(Some(a), c)
}
}

implicit class GetChildrenOps[A](val a: A) extends AnyVal {
def children(implicit getChildren: GetChildren[A]): List[A] =
getChildren.children(a)
}

或者你的意思是在 Java/Scala 中 this 上的调度是动态的(与类型类的静态调度相反)。那么请看

Haskell 中的动态调度

Haskell TypeClass 的调度是动态的吗？

GHC 是否对存在类型使用动态调度？

How to create mutually referencing data structures in Haskell?

猜你喜欢