列表树typederacket

Question

我想将整数列表转换为树。 以下是我的函数定义：

(define-struct (Some T) 
    ([value : T])) 

(define-type (Option T) 
    (U 'None (Some T))) 

(define-type BST (U 'E Nd)) 

(define-struct Nd 
    ([root : Integer] 
    [lsub : BST] 
    [rsub : BST])) 

(: bst-from-list ((Listof Integer) -> BST)) 
;; build a BST from a list of integers: use foldl to do s 
(define (bst-from-list x) 
(cond 
    ('() 'E) 
    ((cons hd _) (Nd hd 'E 'E)) 
    (else 
    (foldl 

我从家里学习，不知道与foldl后做什么。有人能帮我吗？>

Answer 1

You already have an (: insert : Integer BST -> BST) function。
为了建立一个树的元件1，2，3，使用insert可以编写

(insert 3 (insert 2 (insert 1 'E))) 

这是左折叠(1 2 3)与insert作为函数和'E作为初始值。
左折叠将第一个元素与初始值组合，然后将其结果与第二个元素相结合，依此类推。

因此，所有你需要的是

(: bst-from-list : ((Listof Integer) -> BST)) 
(define (bst-from-list ls) 
    (foldl insert 'E ls))