Category Archives: Exercises

Threading with Ocaml

Building, Check writing notes

Advertisements
Tagged , , , , ,

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 , ,

Lexical Trees and the quest for redefining a variable

I have been doing some exercises from the O’reilly book, which by the way is very good, and I always end up failing or missing the point of the exercises.

I discovered that the solutions are available in the online version of the text-book ( who would have guessed?), and since then have been confirming my solutions.

This post is about the Lexical Tree exercise.

My struggle has been to understand reset my mind to think recursively and not imperatively. Its hard. I have been a C, C# and Java programmer as long as I remember. I like recursive functions, but its hard for me to think of them as a first approach.

Anyway, after slowing down and think about all the possible cases and criteria’s I was able to find a suitable solution, however, not as good as the one provided by the authors.

The elegance in Ocaml keep amazing me, its so simple.

The functions are all the same after you know how to go though the tree. That’s the elegance.

I will redo the assignment and post here a good solutions and scheme.

For now I just want to record these thoughts and discoveries:

– Recursive always!
– Use pattern matching when possible, to attend the several constraints and cases
– Use the libraries, String in this specific case
– Practice in paper first!

Doubts:

I still can’t think of a good way of redefining values. The functions return a new data structure, a modified data structure but if I don’t use it again, or recursively I loose the information.

Right now, I am using let for re-assigining the values. for ex:

– let d = insert w d;;
– let d = insert w2 d;;

And so on.

Edit 3/12/12

After sleeping on this, I realized how stupid I was being by trying to force imperative thinking on this language again.

There is no need for mutable variables, here I have to start thinking about returning a new instance.

Its really hard to think like this, I have been completely formatted for imperative programming.

I just got a small new book to take a look, its called “Thinking Ocaml”. I post later a follow-up on this.

 

 

Tagged , , ,