标签: recursive-datastructures

递归程序在内部创建堆栈,并使用户编写更少的代码.

除了上面提到的原因之外,是否有任何情况下递归实际上比手动堆栈更受欢迎？

编辑1:

动态内存分配以什么方式比递归程序在堆上的分配更"昂贵"？

我有一个复杂的Python数据结构(如果它很重要,它是一个很大的music21 Score对象),由于在对象结构内部某处存在弱化,它不会发痒.我以前用堆栈跟踪和python调试器调试过这样的问题,但总是很痛苦.是否有一个工具以递归方式对对象的所有属性运行dir(),查找隐藏在列表,元组,dicts等中的对象,并返回与特定值匹配的那些(lambda函数或类似的东西).一个很大的问题是递归引用,因此需要某种备忘录函数(如copy.deepcopy使用).我试过了:

import weakref
def findWeakRef(streamObj, memo=None):
    weakRefList = []
    if memo is None:
        memo = {}
    for x in dir(streamObj):
        xValue = getattr(streamObj, x)
        if id(xValue) in memo:
            continue
        else:
            memo[id(xValue)] = True
        if type(xValue) is weakref.ref:
            weakRefList.append(x, xValue, streamObj)
        if hasattr(xValue, "__iter__"):
            for i in xValue:
                if id(i) in memo:
                    pass
                else:
                    memo[id(i)] = True
                    weakRefList.extend(findWeakRef(i), memo)
        else:
            weakRefList.extend(findWeakRef(xValue), memo)
    return weakRefList

我大概可以继续在此堵孔(在ITER是不是我想要什么类型的字典,例如),但在此之前我把更多的时间到了,如果有人知道一个更简单的回答不知道.它可能是一个非常有用的通用工具.

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

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

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

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

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

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

我想编写一种数据类型来评估像这样的表达式：

a 被评估为 a

a + b * c / d -e 被评估为 a + (b * (c / (d - e)))

因此，第一个参数始终是数字，第二个参数是数字或表达式

我试图定义这样的数据类型

 data Exp  = Single Int
          | Mult (Single Int) Exp

但这给了我这个编译错误：

    Not in scope: type constructor or class ‘Single’
    A data constructor of that name is in scope; did you mean DataKinds?
  |         
9 |           | Mult (Single Integer ) Exp 
  |            

我可以这样定义：

data Exp  = Single Integer
          | Mult Exp  Exp

但是它没有给出我想要的类型的精确定义。我该如何定义？

考虑以下代码：

import Data.Maybe (fromMaybe)

data MyStructure = Foo Int | Bar String MyStructure | Baz MyStructure MyStructure | Qux Bool Bool MyStructure MyStructure deriving(Eq,Show)

makeReplacements :: [(MyStructure, MyStructure)] -> MyStructure -> MyStructure
makeReplacements replacements structure = fromMaybe (descend structure) (lookup structure replacements)
  where
    descend :: MyStructure -> MyStructure
    descend (Foo x) = Foo x
    descend (Bar x y) = Bar x (makeReplacements replacements y)
    descend (Baz x y) = Baz (makeReplacements replacements x) (makeReplacements replacements y)
    descend (Qux x y …

Python 中最接近 Haskell 中的递归数据类型的是什么？（即在定义自身时使用类型自己的定义。）

编辑：

为了给出递归类型的更具体的定义，下面是 Haskell 中的二叉树：

data Tree a             = Leaf a | Branch (Tree a) (Tree a) 

我的阅读方式如下：二叉树可以是叶子，也可以包含两个子树，这两个子树又是类型树本身。

有关Haskell中递归类型的更多信息，可以参考这里： https: //www.haskell.org/tutorial/goodies.html

我实际上想到的是将 Haskell 中的单词树定义转换为 Python。WordTree这是我的一个旧项目中的定义：

data WordTree = Word String | Subword String [WordTree] | Root [WordTree]

AWordTree是一个 n 叉树结构，其中单词的公共前缀存储在双亲中，其余部分以排序的方式存储在树的叶子中。我相信这种类型定义有点类似于 Trie。然而，由于 Haskell 是一种函数式编程语言，它允许这种类型定义是递归的。Python 中（或者一般来说，在面向对象的编程中）对于这种类型的定义最接近的可能是什么？

Data.Binary是很棒的.我只有一个问题.我们假设我有一个这样的数据类型:

import Data.Binary

data Ref = Ref {
    refName :: String,
    refRefs :: [(String, Ref)]
}

instance Binary Ref where
    put a = put (refName a) >> put (refRefs a)
    get = liftM2 Ref get get

很容易看出这是一个递归数据类型,因为Haskell是懒惰的.由于Haskell作为一种语言既不使用引用也不使用指针,而是按原样呈现数据,我不确定如何保存它.我有强烈的迹象表明,这种天真的责备将导致无限的字节串......

那么如何安全地保存这种类型呢？

我enum在 Swift 中创建了一个递归函数，编译时没有错误或警告，但当我尝试实例化它时，它会进入无限循环：

enum Tree<T> {
    case Leaf(T)
    case Branch(T, [Tree<T>])
}

Tree.Leaf(0) // enters infinite loop
Tree.Branch(0, []) // enters infinite loop

无限循环发生在实例化时，而不是在打印或任何其他使用实例时发生。即使对结果没有做任何事情，Tree.Leaf(0)仍然会永远运行。需要明确的是：无限循环发生在运行时，而不是编译时，而是在实例化时立即发生。

奇怪的是，以下非常相似的数据结构可以完美地工作：

enum WorkingTree<T> {
    case Leaf(T)
    case Branch([WorkingTree<T>]) // notice the lack of a `T` in this case
}

WorkingTree.Leaf(0) // works fine
WorkingTree.Branch([.Leaf(1), .Leaf(2)]) // works fine

也许更奇怪的是，以下数据结构也可以完美运行：

enum ConcreteTree {
    case Leaf(Int)
    case Branch(Int, [ConcreteTree])
}

ConcreteTree.Leaf(0) // works fine
ConcreteTree.Branch(0, []) // works fine

为什么当我尝试实例化它时，我的原始数据结构进入无限循环，而其他几乎相同的数据结构却没有？ …

我想要一个带注释的 AST，所以我使用Fix以下定义了这些递归数据结构：

data Term a 
  = Abstraction Name a
  | Application a a
  | Variable Name
  deriving (Read,Show,Eq,Functor,Foldable,Traversable)

data Label a b 
  = Label a (Term b)
  deriving (Read,Show,Eq,Functor,Foldable,Traversable)

newtype Labeled a 
  = Labeled (Fix (Label a))
  deriving (Show)

我希望能够showa Labeled a，但编译器不高兴：

No instance for (Show1 (Label a))  
arising from the first field of `Labeled' (type `Fix (Label a)')

Run Code Online (Sandbox Code Playgroud)

什么是类Show1以及如何定义适当的实例以显示Labeled a?

我有一个Python字典：

d = {
    "config": {
        "application": {
            "payment": {
                "dev": {
                    "modes": {"credit,debit,emi": {}},
                    "company": {
                        "address": {
                            "city": {"London": {}},
                            "pincode": {"LD568162": {}},
                        },
                        "country": {"United Kingdom": {}},
                        "phone": {"7865432765": {}},
                    },
                    "levels": {"0,1,2": {}},
                },
                "prod": {"modes": {"credit,debit": {}}, "levels": {"0,1": {}}},
            }
        }
    }
}

我想将其更改为类似这样的内容（如果值为空{}，则将键作为其父项的值）

d = {
    "config": {
        "application": {
            "payment": {
                "dev": {
                    "modes": "credit,debit,emi",
                    "company": {
                        "address": {
                            "city": "London", 
                            "pincode": "LD568162"
                        },
                        "country": "United Kingdom",
                        "phone": "7865432765"
                    },
                    "levels": "0,1,2" …