2

我试图通过采用备用元素将 F# 列表分成两部分。这是我的尝试：

let split l =  
    let rec loop l isEven result1 result2 =  
        match l with  
        | [] -> result1 result2  
        | [head::tail] when isEven -> loop tail (not isEven) head::result1 result2  
        | [head::tail] -> loop tail (not isEven) result1 head::result2  
    loop l false [] []

这给了我一个错误：

Program.fs(5,39): error FS0001: Type mismatch. Expecting a  
    'a    
but given a  
    'b -> 'a list      
The resulting type would be infinite when unifying ''a' and ''b -> 'a list'

我不明白它怎么可能是无限的，我不明白为什么它认为我给它一个从 'b 到 'a 列表的函数。有人可以告诉我哪里出错了吗？

4

3 回答 3

6

杰克很好地解释了问题所在。这是一次匹配两个元素的替代解决方案。F# 的模式匹配文档有很多很好的例子。

let split list = 
    let rec split odd even list =
        match list with
        | a::b::tail -> split (a::odd) (b::even) tail
        | a::tail -> split (a::odd) even tail
        | [] -> List.rev odd, List.rev even

    split [] [] list

示例输出。

printfn "%A" (split [1 .. 10])
System.Console.ReadLine() |> ignore

([1; 3; 5; 7; 9], [2; 4; 6; 8; 10])
于 2013-01-30T19:03:56.047 回答
5

这是一个固定版本：

let rec loop l isEven result1 result2 =
    match l with
    | [] ->
        result1, result2
    | head :: tail when isEven ->
        loop tail (not isEven) (head :: result1) result2
    | head :: tail ->
        loop tail (not isEven) result1 (head :: result2)
  • 在第一种情况 ( []) 中，我添加了一个逗号，因为loop函数需要将值作为元组返回。没有逗号，你基本上result1就像一个函数一样对待并应用result2它。
  • 空列表模式是正确的 ( [])，但在其他情况下，您不使用方括号 - 仅使用 cons ( ::) 模式。
  • 您需要将head :: result括号括起来，否则 F# 会像您编写以下代码一样读取代码：(loop tail (not isEven) head) :: (result1 result2).

哦，如果您希望返回的列表与原始列表的顺序相同，则需要在返回列表时使用 List.rev，如下所示：

match l with
| [] ->
    List.rev result1, List.rev result2

最后，这是您的函数的一个稍微简化的版本——您实际上并不需要isEven参数来使函数工作。相反，您只需尝试保持列表的长度相同：

let rec loop (result1, result2) l =
    match l with
    | [] ->
        List.rev result1, List.rev result2
    | hd :: tl ->
        if List.length result1 = List.length result2 then
            loop (hd :: result1, result2) tl
        else
            loop (result1, hd :: result2) tl
于 2013-01-30T17:15:43.567 回答
1

最简单的解决方案不是尾递归，但非常容易理解：

let prepend2 (x, y) (xs, ys) = x::xs, y::ys

let rec split = function
  | [] | [_] as xs -> xs, []
  | x0::x1::xs -> prepend2 (x0, x1) (split xs)
于 2013-01-31T17:54:36.577 回答