英文:
Defining a treein Go without type erasure
问题
我正在尝试使用strings作为边缘和一些Leafs作为叶子来实现一棵树。
我的朴素方法是定义：
type Leaf int
type Node interface {
map[string]Node | Leaf
}
这导致了cannot use type Node outside a type constraint: interface contains type constraints的错误。
在C++中，我会使用std::variant来实现这个：在不丢失静态类型的情况下存储一组类型的值。go-ext/variant看起来设计用于其他目的。
在这种情况下，spf13/viper完全采用了Python的方式，只使用了：
map[string]interface{}
但我从不同的来源中不断阅读到擦除类型不是Go的惯用方式。
最后总是有一个笨拙的解决方案：
type Leaf int
type Node struct {
Tree
value *Leaf
}
type Tree map[string]Node
在这个问题上，什么是Go的惯用解决方案？
英文:
I'm trying to implement a tree with strings for edges and some Leafs for leafs.
My naive approach was to define
type Leaf int
type Node interface {
map[string]Node | Leaf
}
Which results in cannot use type Node outside a type constraint: interface contains type constraints
In C++ I would use std::variant for this: store values from a set of types without loosing static typing. go-ext/variant looks like designed for something else.
spf13/viper goes full on python in this case and just uses:
map[string]interface{}
But i keep reading from different sources that erasing types is not idiomatic go
In the end there is always a clumsy:
type Leaf int
type Node struct {
Tree
value *Leaf
}
type Tree map[string]Node
What is the idiomatic go solution to this problem?
答案1
得分: 2
以下是一种实现方法：
问题在于，如果没有类型擦除，你实际上无法拥有一个包含节点和叶子的映射，但你可以拥有一个包含节点的映射，其中一些节点可以是叶子。因此，可以构建一个使用叶子类型参数的树：
type Node[T any] interface {
GetChildren() map[string]Node[T]
}
type NodeImpl[T any] struct {
children map[string]Node[T]
}
func (n NodeImpl[T]) GetChildren() map[string]Node[T] {
return n.children
}
// 叶子也是一个节点
type Leaf[T any] interface {
Node[T]
GetValue() T
}
type LeafImpl[T any] struct {
value T
}
func (l LeafImpl[T]) GetValue() T {
return l.value
}
func (l LeafImpl[T]) GetChildren() map[string]Node[T] { return nil }
然后你可以这样做：
root := NodeImpl[int]{children: make(map[string]Node[int])}
nd := NodeImpl[int]{children: make(map[string]Node[int])}
root.children["b"] = nd
root.children["a"] = LeafImpl[int]{value: 1}
你可以使用类型断言来判断树中的节点是否是叶子节点：
leaf, ok := root.GetChildren()["a"].(Leaf[int])
英文:
Below is one way of doing it:
The problem is that you can't really have a map that contains nodes and leaves without type erasure, but you can have a map that contains nodes, some of which can be leaves. So a tree that uses a leaf type parameter can be constructed as:
type Node[T any] interface {
GetChildren() map[string]Node[T]
}
type NodeImpl[T any] struct {
children map[string]Node[T]
}
func (n NodeImpl[T]) GetChildren() map[string]Node[T] {
return n.children
}
// A leaf is also a node
type Leaf[T any] interface {
Node[T]
GetValue() T
}
type LeafImpl[T any] struct {
value T
}
func (l LeafImpl[T]) GetValue() T {
return l.value
}
func (l LeafImpl[T]) GetChildren() map[string]Node[T] { return nil }
The you can do:
root := NodeImpl[int]{children: make(map[string]Node[int])}
nd := NodeImpl[int]{children: make(map[string]Node[int])}
root.children["b"] = nd
root.children["a"] = LeafImpl[int]{value: 1}
You can use type assertion to see if a node in the tree is a leaf:
leaf, ok:=root.GetChildren()["a"].(Leaf[int])
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论