Random Tree in Racket

Question

I am trying to create a random tree from lists in Racket.

The tree is made from a list of operators and a list of terminals.

The output will look like this:

'(* (+ 2 4) 2)

So the list can be called with the eval function.

Further there should be a maximum level specified.

So my guess is the procedure will look like the following.

(define (make-tree tree level) ... )

I thought about using the map function and expanding each level at depth, but I'm new to lisp-likes so I'm finding it hard to figure the algorithm I need.

At the moment each operator only takes two parameters (essentially the generated trees are binary trees), but it would be useful to include in any answer how to expand the function to enable three or more parameters.

Racket and lisp aren't the same. Further your question isn't clear to me, could you elaborate it a bit more ? For example, which tree does '(* (+ (2 4) 2)) represent ? — Kevin
My apologies, I should have said lisp-like, it represents * being the root, which contains the nodes (+ 2 4) and 2 — HedgepigMatt
If * is the root and has 2 children, (+ 2 4) and 2, shouldn't it be '(* (+ 2 4) 2) ? — Kevin

soegaard soegaard · Accepted Answer · 2015-09-25T15:45:26

#lang racket

(define (random-from-list xs)
  (list-ref xs (random (length xs))))

;; A TERMINAL is one if terminal1, terminal2, ...

(define TERMINALS '(0 1 2 3 4 5 6 7 8 9))

(define (random-terminal)
  (random-from-list TERMINALS))

;; An OPERATOR is one of '+ '-, '* '/ .

(define OPERATORS '(+ - * /))

(define (random-operator)
  (random-from-list OPERATORS))

;; A TREE is either
;;      i) a terminal
;; or  ii) (list operator terminal1 terminal2 ... terminalN)

(define (random-tree . ignore)
  (match (random 5)               
    [0 (random-list-tree)]      ; probability 1/5 = 20%
    [_ (random-terminal)]))

(define (random-list-tree)
  (define N (+ 2 (random (+ 3 1)))) ; at least two operands, at most 2+3
  (cons (random-operator) (build-list N random-tree)))

To generate trees of a specific depth:

1. generate a tree T
2. find the depth D of T
3. if the depth D is of the desired depth return T
4. otherwise go to 1.

Random Tree in Racket

1 Answers