Function returning two outputs

Question

I would like to create a function that produces two outputs. Please consider the following example:

I built two functions that, given a list of integers, return a list of elements in even position and elements in odd position.

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)

And here everything is fine. Now, the problem: I would like to create a single function alternate that returns both lists with signature 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))

So far, no solution worked. I am pretty sure the problem is even silly, but my reference did not help me to solve the problem.

Answer 1

Since you're calling alternate recursively, the recursive call will also return you two outputs, so of course you can't treat that tuple as a list - as in y::alternate xs.

You have to first take the tuple apart, process the parts separately, and recombine them into a tuple before returning:

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

And then, your base cases should also return two outputs - otherwise your function has unclear return type:

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

(also note that your match case [x::y] actually matches a list of lists, which contains exactly one list, in which the first element will be named x, and the tail of the list will be named y. In order to match a list of exactly two elements, use [x; y] or x::y::[])

Combining it together:

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

Also: technically, the [x; y] base case is not needed, because it would be covered by the last case just fine.

Answer 2

Fyodor's answer is complete (as usual)
So I just wanted to add a tail-recursive version of his code (along with some reduction) to those who wanted to know how to make it tail-recursive (using 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

Alternatively one can use 2 continuation for each side list, but here I think it's not so useful as both sides are manipulated each time, but anyway

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