具有较少递归的函数式编程？

Question

我目前在使用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")

Answer 1

递归是在函数式语言中编写循环的基本机制,因此如果需要迭代字符(就像在样本中一样),那么递归就是你需要的.

如果你想改进你的代码,那么你应该避免使用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)