遞歸構建列表

只要遞歸調用的返回類型是Any，下面的代碼就會編譯，但顯然我做錯了什麼，因爲它不應該是Any。遞歸構建列表

case class Group(
    id: Long = -1, 
    parentId: Long = -1, 
    name: String = "") 

    def makeTree(groupId: Long, groups: List[Group]) = { 
    def getAllChildren(gid: Long): Any = { 
     def children = for { 
     g <- groups; if g.parentId == gid 
     } yield g 

     if (children.isEmpty) List() 
     else { 
     children map { x => 
      getAllChildren(x.id) 
     } 
     } 
    } 
    getAllChildren(groupId) 
    }            
    val groups = List(Group(1, 0, "A"), 
        Group(2, 1, "B"), 
        Group(3, 1, "C"), 
        Group(4, 2, "D")) 

    makeTree(1, groups) 
    //Results in: Any = List(List(List()), List()) 
    }

如果我改變getAllChildren到簽名：

def getAllChildren(gid: Long): List[Group]

然後我得到一個錯誤：

type mismatch; found : List[List[Group]] required: List[Group]

我在做什麼錯在這裏。

來源

2013-07-12 Jack

不是真的說scala，但它看起來像某些id，你收集這個id的組，然後用它的子組的列表替換每個組，等等。

具體來說，在這裏：

if (children.isEmpty) List() 
    else { 
    children map { x => 
     getAllChildren(x.id) 
    } 
    }

事實上，這裏是你的錯誤的根源：您的算法允許無限遞歸，每個遞歸又增加了List[...]在你的返回類型。但是你不能有一個具有動態深度的類型。

例如，如果您嘗試通過給定類型List[List[Group]]來解決此問題，它會抱怨發現List[List[List[Group]]]等等，直到您放棄爲止。

這是typecheckers告訴我們的方式，我們即將編程一個潛在無限遞歸。你可能已經假設你的層次結構不能包含循環的不變量，但這並不反映在類型中。事實上，構建一個兩個小組彼此都是父母的例子並不難。在這種情況下，你的程序會產生一個更深的嵌套列表，直到它由於內存不足而終止。

請注意，您無法簡單地通過使用flatMap而不是map來修復代碼：原因是getAllChildren永遠不會使用Group元素生成列表。它要麼返回一個空列表，要麼是空列表的扁平列表，即空列表。因此，如果它應該返回，它會在平面映射版本中返回一個空列表。

來源

2013-07-12 13:19:39 Ingo

謝謝Ingo的好解釋。我現在看到爲什麼我總是得到空列表。 Chirlo的例子確實會返回內容，但不幸的是，flatMap會導致父子關係的結構丟失。我正在嘗試構建一棵樹。我想我可以通過創建我自己的集合類型來解決這個問題，但我希望能夠簡單地修復當前的代碼。只是看看是否有可能。 – Jack

如果您拼合名單上children map這樣回到你的代碼將工作：

def makeTree(groupId: Long, groups: List[Group]) = { 
    def getAllChildren(gid: Long): List[Group] = { 
    def children = for { 
     g <- groups; if g.parentId == gid 
    } yield g 

    if (children.isEmpty) List() 
    else { 
     val listList = children map { x => 
     x :: getAllChildren(x.id) 
     } 

     listList.flatten 
    } 
    } 
    getAllChildren(groupId) 
}

出現這種情況的原因是，你正在服用的List [組]，它在功能映射也回報一個List[Group]，從而導致List[List[Group]]。簡單地展開該列表將產生所需的結果。

來源

2013-07-12 13:16:19 cmbaxter

「簡單地展開該List將產生所需的結果。」 - 不，它不會，除非空列表是期望的結果。當數據引入週期時，它甚至不會終止。 – Ingo

您需要將children map ...更改爲children flatMap ...，否則您不會返回List[Group]，但可能會返回List[List[.....]]，如@Ingo所示。 flatMap會將每個元素映射到List，然後將所有列表平鋪以創建包含所有子項的僅一個List[Group]。

編輯：作爲@Ingo指出，即使flatMap會解決輸入問題，你的功能仍然無法正常工作，因爲你總是返回一個空列表。你應該去

children flatMap { x => x :: getAllChildren(x.id, acc) }

要將孩子預先安排給孩子的孩子。

來源

2013-07-12 13:58:32 Chirlo

請注意，這不會像現在這樣工作。 'getAllChildren'永遠不會產生實際包含'Group'元素的列表。想想看。 – Ingo

對，他總是返回一個空的'List'。我添加了解決方案的答案 – Chirlo

是的，看起來更好。但是，我們還應該檢測輸入中的週期以防止無限循環。考慮'groups = List（Group（1,2，「A」），Group（2,3，「B」），Group（3,1，「C」））' – Ingo

遞歸構建列表

回答

相關問題