Re: I need help! Substrings

(Some of this overlaps John Reppy's reply.)

This not too bad as a first attempt.  It actually will compile  
successfully
if you remove the semicolon at the end of the definition of findmatch
and change the "fun" keyword in the definition of checkrest to "and".
This is necessary because findmatch and checkrest are mutually
recursive functions (as you have written them), so their declarations  
have
to fit the pattern for declarations of mutually recursive functions:

fun f (...) = ... g(...) ...   (* no semicolon *)
and g(...) = ... f(...) ...

Semicolons after declarations are optional, except that in the  
interactive
top-level loop they signal that a declaration is complete.  You have
to declare mutually recursive functions as a single declaration (using
the "and" keyword).

As John Reppy pointed out, your variable index is just an alias for the
value 0.  It will not change throught your program (as written).  This
also means that the expression

	inc(index)

in the body of function findmatch is always going to evaluate to 1.

A couple additional hints:

1. index should be an argument of findmatch, and should be incremented
when calling findmatch recursively.

2. checkrest should just return a boolean value (true or false).   
Once you've
detected an initial character match, you can call checkrest to see if  
it extends
to a complete match of S with an initial segment of L.  checkrest  
should not
call findmatch recursively (because the recursive scanning in  
checkrest can
move beyond the point where findmatch should continue searching).

One more note on style.  It is usually more concise and clearer to use
pattern matching instead of operators like null, hd and tl.  Thus  
your findmatch
could be rewritten using pattern matching as

fun findmatch(nil,l) = 0  (* the empty string is always a substring!)
     | findmatch(s, nil) = ~1
     | findmatch(c1::s,c2::l) =
         if c1 = c2 then checkrest(s,l)
         else findmatch(c1::s, l) + 1

(This isn't correct, but it correspond with the version you wrote.)

Now see if you can finish it from here.

Dave MacQueen


On May 30, 2007, at 1:59 PM, turbosol wrote:

>
> this is what I have been able to write so far...
>
>
>
> val index = 0;
>
> fun inc x= x+1;
>
>
> fun findmatch(S,L) =
> if null S then ~1
> else if null L then ~1
> else if hd(S) = hd(L) then checkrest(tl S,tl L)
> else findmatch(S, tl L) + inc(index);
>
> fun checkrest(S, L) =
> if null(tl S) then index
> else if hd(tl S)= hd(tl L) then checkrest(tl S, tl L)
> else findmatch(S, tl L);
>
> fun substring (S,L)= findmatch(explode S,explode L);
>
>
> substring("abc","bdabcd");
>
> ////// however, this does not run, it throws errors about the explode.
> Also, I know that if this was able to compile, it will return the  
> size of
> the list if the string is not found.  It is also only checking for  
> the first
> char in the string S, and does nothing with the rest as of now.
>
>
>
>
>
> turbosol wrote:
>>
>> So i signed up for my last compscience class so i can graduate... the
>> class i needed was canceled so i was put into a more difficult  
>> class for
>> majors.  Comp science is my minor... anyways, I am currently doing  
>> twice
>> the work i would normally do in half the time.  I am lost.  if  
>> anyone can
>> help me, i would appreciate it SOOO much.
>>
>> I need to write a function SubString : string * string -> int that  
>> checks
>> whether the first string is a substring of the second (case  
>> sensitive).
>> return the index position (starting from 0) if the string is a  
>> substring
>> or -1 otherwise.  for multiple occurances, just return the index  
>> of the
>> first appearance.  you may assume both input parameters are strings.
>>
>> subString("ab","abcdefg")=> 1
>> subString("aaa","aaaa")=>0
>> subString("bc","absge") =>-1
>> subString("ab","cdabd") => 2
>>
>
> -- 
> View this message in context: http://www.nabble.com/I-need-help%21-- 
> Substrings-tf3836438.html#a10880352
> Sent from the SML/NJ mailing list archive at Nabble.com.
>
>
> ---------------------------------------------------------------------- 
> ---
> This SF.net email is sponsored by DB2 Express
> Download DB2 Express C - the FREE version of DB2 express and take
> control of your XML. No limits. Just data. Click to get it now.
> http://sourceforge.net/powerbar/db2/
> _______________________________________________
> Smlnj-list mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/smlnj-list
>


-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/