二叉樹字符計數和CONCAT

Question

二叉樹的類型是「OCaml中一棵樹，如下：

type 'a tree = Leaf of 'a 
     | Fork of 'a * 'a tree * 'a tree 
let t3 = Fork ("Hello", Leaf "World", Leaf "!") 

我將如何編寫一個函數t_charcount接受一個string樹作爲輸入，並計算總數這些值包含的字符。函數的類型是：string tree - > int。

t_charcount t3 gives int = 11. 

我怎麼會寫一個函數：

寫一個函數t_concat將將字符串樹的值加在一起。這個函數的類型是：串樹 - >字符串

t_concat t3 gives string = "HelloWorld!". 

Answer 1

我將如何編寫一個函數t_charcount接受一個string樹作爲輸入和計算的值包含

字符總數

使用結構化歸納 - 考慮基本案例（例如，葉節點中有多少個字符），然後考慮如何結合來自Fork節點中左側和右側子樹的結果，這是您的一般框架：

let t_charcount tree = 
    let rec loop tree sum = match tree with 
    | Leaf x -> ...base case... 
    | Fork (x,t1,t2) -> ...induction case.. in 
loop tree 0 

編寫一個函數t_concat，它將字符串樹的值連接在一起。這個函數的類型是：串樹 - >字符串

您應該使用相同的方法與charcount功能，除了沒有在整數積累的結果，你應該堆積在一個字符串結果，使用連接符^。

P.S.別指望，那些人會做你的功課。