返回兩個輸出的函數

Question

我想創建一個產生兩個輸出的函數。 請考慮下面的例子：

我建立了兩個函數，給定一個整數列表，返回偶數位置的元素列表和奇數位置的元素。

let rec alternate1 lst = 
    match lst with 
    [] -> [] 
    | [x] -> [] 
    | x::y::xs -> y::(alternate1 xs) 

let rec alternate2 lst = 
    match lst with 
    [] -> [] 
    | [x] -> [x] 
    | x::y::xs -> x::(alternate2 xs) 

這裏一切都很好。現在，問題：我想創建一個單個函數alternate，它返回兩個具有簽名alternate: int list-> (int list * int list)的列表。

let rec alternate lst = 
    match lst with 
    [] -> [] 
    | [x] -> [] 
    | [x::y] -> [y] 
    (*My attempts:*) 
    | x::y::xs -> ((y::alternate xs), (x::alternate xs)) 
    | x::y::xs -> [(y::alternate xs); (x::alternate xs)] 
    | x::y::xs -> ((y::alternate xs) && (x::alternate xs)) 

到目前爲止，沒有解決方案的工作。我很確定這個問題甚至是愚蠢的，但我的reference並沒有幫助我解決這個問題。

Answer 1

既然你打電話alternate遞歸，遞歸調用將也回報，你兩路輸出，所以你當然不能把那個元組的列表 - 在y::alternate xs。

你必須首先採取的元組分開，加工零件分開，並把它們重新組合成一個元組返回前：

let nextXs, nextYs = alternate xs 
x::nextXs, y::nextYs 

然後，您的基本情況也應該返回兩路輸出 - 否則你的函數有目前還不清楚返回類型：

| [] -> [], [] 
| [x] -> [x], [] 
| [x; y] -> [x], [y] 

（也注意到，你的對手的情況下[x::y]確實匹配列表的列表，其中只包含一個列表，其中第一個元素將被命名爲x，而列表w的尾巴病名爲y。爲了精確匹配兩種元素的列表，使用[x; y]或x::y::[]）

結合一起：

let rec alternate lst = 
    match lst with 
    | [] -> [], [] 
    | [x] -> [x], [] 
    | [x; y] -> [x], [y] 
    | x::y::rest -> 
     let nextXs, nextYs = alternate rest 
     x::nextXs, y::nextYs 

另外：從技術上講，不需要[x; y]基的情況下，因爲它會被覆蓋最後一種情況就好了。

Answer 2

Fyodor's answer完成（像往常一樣）
所以我只是想補充他的代碼一尾遞歸版本（還有一些減少）那些誰想要知道如何尾遞歸（使用continuation-passing style），使

let alternate xs = 
    let aux cont even odd (evens, odds) = cont (even :: evens, odd :: odds) 

    let rec loop cont = function 
    | [] | [_] as xs -> cont (xs, []) 
    | even :: odd :: xs -> loop (aux cont even odd) xs 

    loop id xs 

或者可以使用2延續每個側名單，但在這裏我想既是雙方每次都操縱它不是那麼有用，但無論如何

let alternate xs = 
    let aux cont x xs = cont (x :: xs) 

    let rec loop evenCont oddCont = function 
    | [] | [_] as xs -> evenCont xs, oddCont [] 
    | even :: odd :: xs -> loop (aux evenCont even) (aux oddCont odd) xs 

    loop id id xs