2

私は現在、F# を使用した関数型プログラミングでかなりうまくやっています。ただし、F#/関数型プログラミング コミュニティにもっと優れたイディオムがあると思われる場合は、再帰を使用して多くのプログラミングを行う傾向があります。それで、学習の精神で、再帰なしで以下の関数を書くためのより良い/より慣用的な方法はありますか?

let rec convert line =
    if line.[0..1] = "  " then
        match convert line.[2..] with
        | (i, subline) -> (i+1, subline)
    else
        (0, line)

次のような結果が得られます。

> convert "asdf";;
val it : int * string = (0, "asdf")
> convert "  asdf";;
val it : int * string = (1, "asdf")
> convert "      asdf";;
val it : int * string = (3, "asdf")
4

4 に答える 4

6

再帰は、関数型言語でループを記述するための基本的なメカニズムであるため、(サンプルで行っているように) 文字を反復処理する必要がある場合は、再帰が必要です。

コードを改善したい場合は、line.[2..]非効率になるため、使用を避ける必要があります (文字列はこの種の処理用に設計されていません)。文字列をリストに変換してから処理することをお勧めします。

let convert (line:string) = 
  let rec loop acc line =
    match line with
    | ' '::' '::rest -> loop (acc + 1) rest
    | _ -> (acc, line)
  loop 0 (List.ofSeq line)

標準ライブラリのさまざまな関数を使用して、これをより短い方法で実装できますが、通常は再帰的でもあります (再帰が表示されないだけです! Seq.unfold) Seq.fold。コードよりも複雑です）。

標準ライブラリを使用したより簡潔なアプローチは、TrimLeftメソッド (コメントを参照) を使用するか、標準の F# ライブラリ関数を使用して、次のようにすることです。

let convert (line:string) =
  // Count the number of spaces at the beginning
  let spaces = line |> Seq.takeWhile (fun c -> c = ' ') |> Seq.length
  // Divide by two - we want to count & skip two-spaces only
  let count = spaces / 2
  // Get substring starting after all removed two-spaces
  count, line.[(count * 2) ..]

編集文字列とリスト処理のパフォーマンスに関して、問題は、リストをスライスすると参照が変更されるだけで、スライスすると新しい文字列が割り当てられることです (これは、.NET プラットフォームでの文字列の表現方法であるためです)。簡単なテストを次に示します。

let rec countList n s = 
  match s with 
  | x::xs -> countList (n + 1) xs
  | _ -> n

let rec countString n (s:string) =
  if s.Length = 0 then n
  else countString (n + 1) (s.[1 ..])


let l = [ for i in 1 .. 10000 -> 'x' ]
let s = new System.String('x', 10000)

#time 
for i in 0 .. 100 do countList 0 l |> ignore    // 0.002 sec (on my machine)
for i in 0 .. 100 do countString 0 s |> ignore  // 5.720 sec (on my machine)
于 2012-09-15T09:16:39.303 に答える
2

不均一な方法で文字列をトラバースするため、この例では再帰的なソリューションがはるかに適しています。読みやすくするために、末尾再帰ソリューションを次のように書き直します。

let convert (line: string) =
    let rec loop i line =
        match line.[0..1] with
        | "  " -> loop (i+1) line.[2..]
        | _ -> i, line
    loop 0 line

あなたが尋ねたので、ここに（奇妙な）非再帰的な解決策があります:)。

let convert (line: string) = 
    (0, line) |> Seq.unfold (fun (i, line) -> 
                                let subline = line.[2..]
                                match line.[0..1] with
                                | "  " -> Some((i+1, subline), (i+1, subline))
                                | _ -> None)
              |> Seq.fold (fun _ x -> x) (0, line)
于 2012-09-15T08:25:40.590 に答える
1

末尾再帰を使用すると、次のように記述できます。

let rec convert_ acc line =
    if line.[0..1] <> "  " then
        (acc, line)
    else
        convert_ (acc + 1) line.[2..]
let convert = convert_ 0

ただし、まだ非再帰的な答えを探しています。

于 2012-09-15T08:00:41.693 に答える
0

関数を作成するより速い方法は次のとおりです。文字列のスライスを使用する代わりに、文字を明示的にチェックします（Tomasが言ったように、これは遅いです）。また、末尾再帰です。最後に、StringBuilderを使用して「フィルター処理された」文字列を作成します。これにより、入力文字列が適切な長さに達するとパフォーマンスが向上します（ただし、StringBuilderの作成のオーバーヘッドのため、非常に小さい文字列の場合は少し遅くなります）。

let convert' str =
    let strLen = String.length str
    let sb = System.Text.StringBuilder strLen

    let rec convertRec (count, idx) =
        match strLen - idx with
        | 0 ->
            count, sb.ToString ()

        | 1 ->
            // Append the last character in the string to the StringBuilder.
            sb.Append str.[idx] |> ignore
            convertRec (count, idx + 1)

        | _ ->
            if str.[idx] = ' ' && str.[idx + 1] = ' ' then
                convertRec (count + 1, idx + 2)
            else
                sb.Append str.[idx] |> ignore
                convertRec (count, idx + 1)

    // Call the internal, recursive implementation.
    convertRec (0, 0)
于 2012-09-15T21:24:34.623 に答える