标签: recursive-datastructures

类型值如何:

type Tree =
    | Node of int * Tree list

有一个值引用自己以功能方式生成的值吗？

对于Tree的合适定义,结果值应该等于以下Python代码中的x:

x = Tree()
x.tlist = [x]

编辑:显然需要更多解释.我正在尝试学习F#和函数式编程,所以我选择实现之前用其他语言编写的封面树.这里相关的是每个级别的点是下面级别的点的子集.结构在概念上达到了水平 - 无限.

在命令式语言中,节点具有包含其自身的子列表.我知道这可以在F#中强制执行.不,它不会在封面树算法的情况下创建无限循环.

我有一个表示表单的结构,我想使用RecursiveIterator迭代它.问题是这只会返回顶级问题.我究竟做错了什么？

整体形式:

class Form implements RecursiveIterator{
    private $id;
    private $caption;
    private $other_text;
    private $questions = array();
    private $current;

    private function __construct(DibiRow $row){
        $this->id = $row->id;
        $this->caption = $row->caption;
        $this->other_text = $row->other_text;
        $this->loadQuestions();
    }

    private function loadQuestions(){
        $questions = dibi::query('SELECT * FROM cyp_questions WHERE form_id = %i AND parent_id IS NULL', $this->id);
        while($question = $questions->fetch()) $this->questions[] = new Question($question->question_id, $question->type, $question->caption, $question->other_text, $question->triggers_unique == 1);
    }

    /**
     * @throws InvalidArgumentException
     * @param $id
     * @return Form
     */
    public static function loadById($id){ …

二维空间索引问题:

你称之为基本上是无限*四叉树的数据结构,其节点既不包含绝对坐标也不包含绝对尺度 - 其中每个节点的坐标系已经标准化为单位平方(0,0) - (1,1 ),顶级节点绝对没有固定？

当然,这是一个四叉树 - 但它是什么类型的四叉树？(有一个共同的名称吗？我已经看到了文献中命名和定义的几十种类型的四叉树,但不是这个特别的.

要渲染场景,您将获得一些起始节点(不一定是根),其大小(以像素为单位)以及它在屏幕上的位置.然后,您可以通过使用当前变换矩阵缩放其坐标来绘制节点内的所有对象,当您向下移动树时,您可以将其推入堆栈并减半.因此,节点的绝对坐标仅在渲染期间通过临时工作变量可用,并且不包含在数据结构本身内.

如果节点内的对象移动到节点之外(例如,在单位方块外),则将其传递给父节点以重新分配给另一个节点.如果对象变得碎片化(例如,子弹击中小行星),则较小的部分向下传递给子节点,子节点必须适当地缩放坐标以维持每个节点内的单位平方归一化.

与空间索引中使用的传统四叉树实现的关键区别在于,对象的坐标始终相对于包含它们的节点的坐标系.这种相对主义不仅适用于立场,也适用于规模.

*缺乏绝对坐标的无限; 甚至双精度浮点坐标在用于绝对定位时也会限制位置和尺寸.

我正在使用haskell来实现一个涉及返回值的函数的模式,以及它们自己(或相同类型的函数).现在我已经实现了这样:

newtype R a = R (a , a -> R a)

-- some toy functions to demonstrate    
alpha :: String -> R String
alpha str
    | str == reverse str = R (str , omega)
    | otherwise          = R (reverse str , alpha)

omega :: String -> R String
omega (s:t:r)
    | s == t    = R (s:t:r , alpha)
    | otherwise = R (s:s:t:r , omega)

这些类型的函数的驱动力是一个称为级联的函数:

cascade :: (a -> R a) -> [a] -> [a]
cascade …

我尝试创建一个用于处理逻辑表达式的数据结构.乍一看,逻辑表达式看起来像Trees,所以从树上组成它似乎是合理的:

data Property a = And (Property a) (Property a) |
                 Or  (Property a) (Property a) |
                 Not (Property a) | Property a   deriving (Show,Eq)

但这不是一个好主意,因为我的树的左右分支之间确实没有区别,因为 A && B == B && A

好吧,也许List更好？

data Property a = Empty | And a (Property a) | Or a (Property a) | Not a (Property a)  deriving Show

但在这种情况下,我无法形成一个"逻辑树",只能形成一个"逻辑列表".所以我需要一个类似Tree但没有左右"分支" 的数据结构.

对于这类问题,有一个简单的迭代解决方案.

Node Insert(Node head,int data) {
    Node newNode = new Node();
    newNode.data = data;
    if (head == null) {
        return newNode;
    }
    Node current = head; 
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
    return head;
}

它工作得很好.但我想学习递归并用这种观点看待事物.因此我想出了下面的解决方案,看起来很优雅,但我不得不承认这只是直觉和给定的代码有效.我想开发一个用于递归的心理模型,或者至少某种方式来验证我的代码是否正常工作.如何从理论上验证以下解决方案是否有效.

递归版

Node Insert(Node head,int data) {
    // Base case.
    if (head == null) {
        Node newNode = new Node();
        newNode.data = data;
        return newNode;
    }
    // Smaller problem instance.
    head.next = Insert(head.next, data);
    return head;
}

我有一个嵌套的三层结构。我想在Go中使用reflect来解析它（使用递归函数）。使用反射和递归函数的原因是

• 可以有不同数量的字段（但前两个字段是固定的）
• 字段类型不固定。
• 嵌套层数可以不同（本例中只有三层。也可以更多）

这是一些代码。

type Edge struct{
    Uid string `json:"uid,omitempty"`
    Name string `json:"name,omitempty"` 
    Read Article `json:"visited,omitempty"` 
} 
type Article struct {
    Uid string`json:"uid,omitempty"` 
    Namestring`json:"name,omitempty"`
    From Site `json:"from,omitempty"`
}
type Site struct{
    Uid string `json:"uid,omitempty"`
    Name string `json:"name,omitempty"` 
}
func CheckNestedStruct(edges interface{}){ 
    rv := reflect.ValueOf(edges).Elem() 
    uidField := rv.FieldByName("Uid")
    uid := getStructField(edges, "Name") // get value of Name from database 
    if (uid != ""){
        uidField.SetString(uid)
    }
    for i := 0 ; i < rv.NumField() ; i++ {
        field := rv.Field(i)
        fieldType …

我一直试图建立一个嵌套的树状结构两天,并决定在这里寻求帮助.假设我有这样的数据:

rows = [
    {'Year': None, 'Region': None, 'Country': None, 'Manufacturer': None, 'Brand': None, 'Sales': 25}, # row 1 => SUM of (row 2 and row 14) = 15+25 = 40; this row represents, for example, all of the sales made so far (the ultimate total, if you will call it as such)
    {'Year': 2013, 'Region': None, 'Country': None, 'Manufacturer': None, 'Brand': None, 'Sales': 15}, # row 2 => SUM of sales from (row 3) = 15; this row represents, …

如果我理解正确的话,我们可以将归纳数据类型建模为初始F-代数和共感应数据类型作为最终的F-余代数(对于适当的endofunctor F)[ 1 ].据我所知,根据Lambek的引理,初始代数(和最终的余代数)是同构的不动点解T ? F T,但我不明白为什么初始代数是最不固定的点,而最终的代数是最大的固定点.(同构现象T ? F T有明显的解决方案吗？)

另外,我还不清楚类型理论中如何定义归纳和共感数据类型.是否有关于此主题的推荐资源,以及它们与类别理论的关系？

谢谢!

最简单的方法是删除和插入对象，但可能还有更快的方法。（如果我想太多了，我应该用简单的方法来做，请告诉我）

这是关于我的四叉树的一些注释

• 正在移动的对象是 AABB，并且可能比最小的四叉树节点还要大。
• 创建子四叉树时，不会删除对象。这意味着根四叉树有一个指向四叉树内每个对象的指针。
• 这些对象作为指针存储在四叉树外部的向量中。

到目前为止，每次对象移动时，它都会调用根四叉树上名为 Update() 的函数。它包含其自身以及在移入参数之前的过去的边界框。但我不确定如何实现该功能。

将整个代码发布到我的 QuadTree 会使我的帖子变得很长，因此我创建了一个GitHub 存储库以便于阅读。

编辑：对于任何寻找答案的人来说，这似乎是通过删除和删除对象来更新对象，并且从他在评论中所做的测试来看，这是相当有效的。