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.unfoldandSeq.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 回答