CODEWITHSUNDEEP
recursionocamlsubstring
P basak
P basak

Reputation: 5004

Creating own substring functions recursively in Ocaml

How can i write a substring function in ocaml without using any assignments lists and iterations, only recursions? i can only use string.length.

i tried so far is 

let substring s s2 start stop=
if(start < stop) then 
    substring s s2 (start+1) stop
    else s2;;

but obviously it is wrong, problem is that how can i pass the string that is being built gradually with recursive calls?

Upvotes: 1

Views: 409

Answers (2)

Sam I am says Reinstate Monica
Sam I am says Reinstate Monica

Reputation: 31194

Now I can't give you the answer to this, Partly because it's your homework, and partly because it's been 3 years since I've touched OCaml syntax, but I could try to help you along.

Now the Basic principle behind recursion is to break a problem down into smaller versions of itself.

You don't pass the string that is slowly being built up, instead use your recursive function to generate a string that is almost built up except for a single character, and then you add that character to the end of the string.

Upvotes: 0

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66793

This feels like a homework problem that is intended to teach you think think about recursion. For me it would be easier to think about the recursion part if you decide on the basic operations you're going to use. You can't use assignments, lists, or iterations, okay. You need to extract parts of your input string somehow, but you obviously can't use the built-in substring function to do this, that would defeat the purpose of the exercise. The only other operation I can think of is the one that extracts a single character from a string:

# "abcd".[2];;
- : char = 'c'

You also need a way to add a character to a string, giving a longer string. But you're not allowed to use assignment to do this. It seems to me you're going to have to use String.make to translate your character to a string:

# String.make 1 'a';;
- : string = "a"

Then you can concatenate two strings using the ^ operator:

# "abc" ^ "def"
- : string = "abcdef"

Are you allowed to use these three operations? If so, you can start thinking about the recursion part of the substring problem. If not, then I probably don't understand the problem well enough yet to give advice. (Or maybe whoever set up the restrictions didn't expect you to have to calculate substrings? Usually the restrictions are also a kind of hint as to how you should proceed.)

Moving on to your specific question. In beginning FP programming, you don't generally want to pass the answer down to recursive calls. You want to pass a smaller problem down to the recursive call, and get the answer back from it. For the substring problem, an example of a smaller problem is to ask for the substring that starts one character further along in the containing string, and that is one character shorter.

(Later on, you might want to pass partial answers down to your recursive calls in order to get tail-recursive behavior. I say don't worry about it for now.)

Upvotes: 2

Related Questions