String search (see http://stackoverflow.com/q/33001838/4925216 )

FSharp · Script

/Program.fs

module Holditch =

  let allIndexOf (str: string) (c: string) =
    let rec inner (s: string) acc =
      match s.IndexOf c, s.IndexOf c + 1 = s.Length with
       -1, _ -> acc
      | x, true -> x :: acc
      | x, false -> inner <| s.Substring (x + 1) <| x :: acc
    inner str []
    
(*-------------------------------------------------------------------*)
(*-------------------------------------------------------------------*)

module Sehnsucht =

  module Comprehension =
    let allIndexOf str1 str2 = [
      let lgt2 = String.length str2
      for i in 0 .. String.length str1 - lgt2 do
        if str1.[i .. i + lgt2 - 1] = str2
        then yield i
    ]
    
  (*-----------------------------------------------------------------*)
  
  module RecursionWithAccumulator =

    let allIndexOf str1 str2 =
      let lgt1, lgt2 = String.length str1, String.length str2
    
      let rec inner idx acc =
        if idx > lgt1 - lgt2 
        then acc
        else inner (idx + 1) <| if str1.[idx .. idx + lgt2 - 1] = str2
                                then idx :: acc
                                else acc

      inner 0 []
      |> List.rev // needed to reorder correctly results
      
  (*-----------------------------------------------------------------*)
  
  module RecursionWithContinuation =

    let allIndexOf str1 str2 =
      let lgt1, lgt2 = String.length str1, String.length str2
    
      let rec inner idx cont =
        if idx > lgt1 - lgt2 
        then cont
        else inner (idx + 1) <| if str1.[idx .. idx + lgt2 - 1] = str2
                                then (fun acc -> cont (idx :: acc))
                                else cont

      inner 0 id []
      
(*-------------------------------------------------------------------*)
(*-------------------------------------------------------------------*)
module Program =

  [<EntryPoint>]
  let main _ =
  
    // type annotation needed for printf to know it's not really a string
    [
      ("Using Holditch : %A": Printf.TextWriterFormat<_>), Holditch.allIndexOf
      "Using Sehnsucht.Comprehension : %A", Sehnsucht.Comprehension.allIndexOf
      "Using Sehnsucht.RecursionWithAccumulator : %A", Sehnsucht.RecursionWithAccumulator.allIndexOf
      "Using Sehnsucht.RecursionWithContinuation : %A", Sehnsucht.RecursionWithContinuation.allIndexOf
    ]
    |> List.iter (fun (msg, fct) ->
      printfn msg <| fct "foobar" "o"
      printfn msg <| fct "foobarmanhelloman" "man"
      printfn "")
    
    0 // exit code