4
\$\begingroup\$

Is the MoveNext operation inefficient here? I really just want to increment an index. Originally, I had a mutable variable locally in ExtractTokens to accommodate this. I would have to believe that a mutable variable there would have been pretty efficient, but I'm trying hard not to have them. I can't help but feel that creating a new Record to increment an integer is bad somehow. I guess I'm wondering what a real-world F# developer would have chosen to do here.

This starts in ExtractTokens. It basically iterates each character in a string. On spaces it yields the previous word, unless in a quote either single or double.

type Quote = 
   | Single
   | Double
   | None

type State = {
   Start : int
   Index : int
   Quote : Quote
   }

let InitState : State = 
   {Start = 0; Index = 0; Quote = None }

let MoveNext (s : State) : State = 
   {s with Index = s.Index + 1}

let FlipQuote (s : State) (text : string) : State = 
   match text.[s.Index], s.Quote with
   | '\'', None   -> {s with Quote = Single}
   | '"' , None   -> {s with Quote = Double} 
   | '\'', Single -> {s with Quote = None}
   | '"' , Double -> {s with Quote = None}
   | _ -> s

let StartNew (s : State) : State = 
   {Start = s.Index; Index = s.Index; Quote = None}

let NotEmpty (s : string) : bool =
   not (System.String.IsNullOrWhiteSpace(s))

let GetToken (s : State) (text : string) : string =
   text.Substring(s.Start, s.Index - s.Start)

let GetChar (s : State) (text : string) : string =
   text.[s.Index].ToString()

let ExtractTokens (text : string) : seq<string> = 
   let rec loop state = 
      seq {
         if (state.Index < text.Length) then
            match text.[state.Index], state.Quote with
            | '"' , _  
            | '\'', _     -> yield! FlipQuote state text |> MoveNext |> loop
            | ' ' , None   
            | '(' , None
            | ')' , None  -> yield  GetToken state text
                             yield  GetChar  state text
                             yield! MoveNext state |> StartNew |> loop 
            | _   , _     -> yield! MoveNext state |> loop
         else
            yield GetToken state text
      }
   loop InitState |> Seq.where NotEmpty

Refactored

type Quote = 
   | Single
   | Double
   | None

type State = {
   Start : int
   Quote : Quote
   }

let InitState : State = 
   {Start = 0; Quote = None }

let FlipQuote (state : State) (index : int) (text : string) : State = 
   match text.[index], state.Quote with
   | '\'', None   -> {state with Quote = Single}
   | '"' , None   -> {state with Quote = Double} 
   | '\'', Single
   | '"' , Double -> {state with Quote = None}
   | _ -> state

let StartNew (state : State) (index : int) : State = 
   {Start = index; Quote = None}

let NotEmpty = 
   System.String.IsNullOrWhiteSpace >> not   

let GetToken (state : State) (index : int) (text : string) : string =
   text.Substring(state.Start, index - state.Start)

let GetChar (index : int) (text : string) : string =
   text.[index].ToString()

let ExtractTokens (text : string) : seq<string> = 
   let rec loop index state = 
      seq {
         if (index < text.Length) then
            match text.[index], state.Quote with
            | '"' , _  
            | '\'', _     -> yield! FlipQuote state index text |> loop (index + 1)
            | ' ' , None   
            | '(' , None
            | ')' , None  -> yield  GetToken state index text
                             yield  GetChar  index text
                             yield! StartNew state (index + 1) |> loop  (index + 1)
            | _   , _     -> yield! state |> loop (index + 1)
         else
            yield GetToken state index text
      }
   loop 0 InitState |> Seq.where NotEmpty
\$\endgroup\$
  • \$\begingroup\$ Is it slower than a mutable variable? Definitely yes. Does it matter? Probably not. Here's a rant I wrote recently on the subject: stackoverflow.com/questions/40202840/… \$\endgroup\$ – Fyodor Soikin Oct 31 '16 at 15:04
  • \$\begingroup\$ @FyodorSoikin I definitely agree with your point of view. I am of the same mindset. This example just seemed so local and incorruptible and I did work around it. I just wasn't sure if the mutable 'i' in what is essentially a for loop, falls into the optimization bucket or is it just being pragmatic. Sounds like it's optimization. Thanks!. \$\endgroup\$ – TBone Oct 31 '16 at 15:26
1
\$\begingroup\$

I'm not saying the below revision is an improvement but it has eliminated the need for MoveNext. The penalty is to have the index as a separate argument to loop which violates the idea of a state object. One could argue that the index is not a part of the (splitting)state but just an iterator variable and then everything are nicely justified again :-)

module RevisedSplitting =

    type String with
        member this.charAt index =
            this.[index]

    type Quote = 
       | Single
       | Double
       | None

    type State = {
       Start : int
       Quote : Quote
       }

    let InitState = 
       {Start = 0; Quote = None }

    let FlipQuote s index (text : string) = 
       match text.charAt index, s.Quote with
       | '\'', None   -> {s with Quote = Single}
       | '"' , None   -> {s with Quote = Double} 
       | '\'', Single -> {s with Quote = None}
       | '"' , Double -> {s with Quote = None}
       | _ -> s

    let StartNew s index = 
       {Start = index; Quote = None}

    let NotEmpty s =
       not (System.String.IsNullOrWhiteSpace(s))

    let GetToken s index text =
       (string text).Substring(s.Start, index - s.Start)

    let GetChar index (text : string) =
       sprintf "%c" (text.charAt index)

    let ExtractTokens (text : string) = 
       let rec loop index state = 
          seq {
             if index < (text |> Seq.length) then
                match text.charAt index, state.Quote with
                | '"' , _  
                | '\'', _     -> yield! FlipQuote state index text |> loop (index + 1)
                | ' ' , None   
                | '(' , None
                | ')' , None  -> yield  GetToken state index text
                                 yield  GetChar  index text
                                 yield! StartNew state (index + 1) |> loop (index + 1)  
                | _   , _     -> yield! state |> loop (index + 1)
             else
                yield GetToken state index text
          }
       loop 0 InitState |> Seq.where NotEmpty
\$\endgroup\$
  • \$\begingroup\$ let me write some comments \$\endgroup\$ – user110704 Nov 4 '16 at 9:31
  • \$\begingroup\$ 1. Now NotEmpty looks not in the style of F#. You can use >> forward composition operator instead: let NotEmpty = System.String.IsNullOrWhiteSpace >> not \$\endgroup\$ – user110704 Nov 4 '16 at 9:32
  • \$\begingroup\$ 2. In function FlipQuote two patterns return the same value. \$\endgroup\$ – user110704 Nov 4 '16 at 9:36
  • \$\begingroup\$ @FoggyFinder: Thanks for your comments, but maybe they are better aimed at the original post :-). My goal was entirely to get rid of MoveNext \$\endgroup\$ – Henrik Hansen Nov 4 '16 at 9:38
  • 1
    \$\begingroup\$ @TBone: I'm not sure charAt is more functional than referencing the index directly, but IMO it nicer to read and it show how to make extension functions in F#. The sprinf is the intrinsic F# string composer. The nice thing about it is that you get immediately response from the inference mechanism if you use the right markup or not for the argument. \$\endgroup\$ – Henrik Hansen Nov 4 '16 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.