我目前正在為函式式編程考試學習OCaml，我在嘗試跟隨這個練習中的遞回函式的步驟時遇到了一些困難。任務是在一棵N-ary樹上找到最昂貴的葉子（葉子的成本由通往葉子的路徑上的整數之和給出）。
這是型別定義：
type 'a ntree = Ntree of 'a * 'a ntree List
這是練習中的一個輔助函式
let rec maxpair = function
| [] -> failwith "空串列"。
| [(x, y)] -> (x, y)
| (x, y) :: (a, b) :: rest ->
if y > b then maxpair ((x, y) :: rest)
else maxpair ((a, b) :: rest)
最后，這里是最后一個函式
let rec leaf_cost = function
| Ntree (x, []) -> (x, x)
| Ntree (x, tlist) ->
let (y, c) = maxpair (List.map leaf_cost tlist)
在中
(y, c x)
這就是練習的解決方案，也就是說，它是有效的。但我在試圖分析函式中的每一個遞回步驟時遇到了困難，特別是我對let (y, c) ... in (y, c x)宣告有些困惑。
uj5u.com熱心網友回復：
給定一棵樹，leaf_cost回傳一對(v, c)，它是具有最大成本v的葉子節點的值，而該成本c。
在基本情況下，當沒有子節點時，值是x，其成本也是x。
在一般情況下，一個節點由一個整數x和子節點串列children（又名tlist）組成。
List.map leaf_cost children
上述運算式是一個對的串列，每個對是最大的葉子和它在各自的子樹上的相關成本，根植于每個子節點。
一般來說，可能會有多個具有相同成本的葉子，但是你的問題忽略了這一點，并以一種實作定義的方式選擇一個具有迄今為止所有成本中最大成本的一對。
這是通過呼叫maxpair來實作的，它給出了一個配對(y, c)，其中y是所有遞回得到的配對中具有最大成本c的第一個葉子。
知道在所有子樹中，(y, c)是一個成本為c的葉子，而你當前節點的權重為x，當前節點的成本為c x。這就是為什么在一般情況下回傳的值是(y, c x)，保持跟蹤子樹中導致該成本的葉子。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/319309.html
標籤：
上一篇：遞回函式回傳意外的字串
下一篇：事件在遞回中執行了幾次函式