Tag Archives: Tree

Lexical Tree – The redo Exercises

Ok, so the first code I made for this exercise was bad, and I couldn’t get to the solution, so this is a redo!

 

The exercise is from the O’Reilly book on Ocaml, “Developping Application with Ocaml”.

Its the Second exercise of the second chapter, Lexical Trees.

 

The exercise is simple. A structure for the Lexical Tree is given, and also its nodes, and what is asked is to build the methods to access and modify the tree.

Its functional programming so the point is not to reuse variables but to make copies, I want to keep that in mind this time.

 

As opposed to before, I will first use a pen and papers and then code it in Ocaml.

 

1. Write the function exists which testes wether a word belongs to a dictionary or not, of type lex_tree

Its impossible not to be biased after viewing the solution, so:

1. Pattern match dictionary with 3 cases:

Empty Dictionary

Filled and Letter = word.[i]

Filled and Letter != word [i]

2. Make it recursive, after all its the point of the xercise

Create an auxiliary function that you can call and increment i

3. Everytime you call the function, it only happens in the second case, call it with the substring of word

4. Return the value as boolean

(5. End case of recursion is n = 1!, when the word reaches the last word, return the node boolean)

 

From O’Reilly

# let rec exists w d = 
let aux sw i n = match d with
[] -> false
| (Letter (c,b,l))::t when c=sw.[i] ->
if n = 1 then b else exists (String.sub sw (i+1) (n-1)) l
| (Letter (c,b,l))::t -> exists sw t
in aux w 0 (String.length w) ;;
val exists : string -> lex_tree -> bool = <fun>

 

2. Write function insert element, which should only insert if it doesn’t exist already


Here we use almost the same algorithm as above.

Keeping in mind we have to return the modified dictionary 

 

From O’Reilly

# let rec insert w d = 
let aux sw i n =
if n = 0 then d
else match d with
[] -> [Letter (sw.[i], n = 1, insert (String.sub sw (i+1) (n-1)) [])]
| (Letter(c,b,l))::t when c=sw.[i]->
if n = 1 then (Letter(c,true,l))::t
else Letter(c,b,insert (String.sub sw (i+1) (n-1)) l)::t
| (Letter(c,b,l))::t -> (Letter(c,b,l))::(insert sw t)
in aux w 0 (String.length w) ;;
val insert : string -> lex_tree -> lex_tree = <fun>

 

3. Write a function construct which takes a list of words and constructs the dictionary

Simple as it sounds. With what I learned before, I will create a simple recursive function.

I did a solution of mine, almost similar, but the one in the solutions is far simpler.

 

1. Receives a list of strings and returns a dictionary

2. Create récursive aux fonction, just as done above. 

3. If empty list, its the end so, return dictionary

4. If not empty, call aux recursion with rest of list and new dictionary (returned from insert head dictionary)

5. Done

From O’Reilly

# let construct l = 
let rec aux l d = match l with
[] -> d
| h::t -> aux t (insert h d)
in aux l [] ;;
val construct : string list -> lex_tree = <fun>

 

To continue…


Tagged , ,