三元ツリー法として標準的なML

Question

は三木の種類が定義されます。私は、関数は三元ツリーに一致するように& foldlのをマップ変更する必要が

datatype ’a tree = 
Leaf of ’a 
| Node of ’a tree * ’a tree * ’a tree 

...

fun tree_map (f : ’a -> ’b) (t : ’a tree) : ’b tree = 
f,nil) = nil 
| map (f,x::xs) = f(x) :: (map (f,xs)) 


fun tree_foldl (f : ’a * ’a -> ’a) (n: ’a) (t : ’a tree) : ’a = 
(f,ie,nil) = ie 
| foldl (f,ie,x::xs) = foldl (f, f(x,ie), xs); 

私はこれを知っていますおそらく単純な変更ですが、私は論理の周りに私の頭を包んでいるように見えることはできません。私はそれがバイナリツリーのためにどのように異なるのか理解していません...どんなポインタ？

Answer 1

代数的データ型で関数を定義するときの良い出発点は、それぞれの場合に1つの "一致パターン"を持つことです。

ベースの例は、（かなり）明白ですので、私は、次のように起動します：

fun tree_map f (Leaf x) = Leaf (f x) 
    | tree_map f (Node (t1, t2, t3)) = Node (something involving t1, t2, and t3) 

fun tree_foldl f ie (Leaf x) = f(ie, x) 
| tree_foldl f ie (Node (t1, t2, t3)) = ... something involving t1, t2, and t3 ... 

興味深いビットは運動として残っています。