what is wrong with my unpair implementation?

2
votes

I'm trying to figure out WHY i'm getting the error below more than I am interested in a correct implementation of my method.

I have the following f# code that is supposed to unpair a list of tuples into a list containing all the items in the tuples like so:

let unpair l =
    let rec loop acc l =
        match l with
        | [] -> acc
        | (x,y)::tl ->
            loop (acc @ x @ y) tl
    loop [] l

//should print:
// [1 2 3 4 5 6]

printf "["
List.iter (printf "%A") (unpair [(1, 2); (3, 4); (5, 6)])
printfn "]"

I get the following error for each of my ints when calling unpair: This expression was expected to have type 'a list but here has type int

Why is it expecting 'a list?

2
f#

2 Answers

4
votes

The problem is in the following expression

acc @ x @ y

The @ is used to combine list values together yet here x and y are typed to int. What you're looking for is the :: operator which will add items to a list. Additionally you are building up the list backwards in that expression. Use the following and it should fix your issue

x :: y :: acc
2
votes

As JaredPar explains, you need to use x::acc to add elements to the accumulator. If you want to append elements to the end, you could write acc @ [x], but that's very inefficient, as it needs to copy the whole list for every single element.

The usual solution is to add elements to the front and then reverse the list at the end of the processing:

let unpair l =
    let rec loop acc l =
        match l with
        | [] -> List.rev acc     // NOTE: Reverse the list here
        | (x,y)::tl ->
            loop (y::x::acc) tl  // Add elements to the front  
    loop [] l

This is a lot more efficient than using acc @ [x], because it keeps adding elements to the front (which takes just a small constant time) and then creates a single copy of the whole list at the end.

The same function can be also nicely & efficiently implemented using sequence expressions:

let unpair l =
  [ for x, y in l do
      yield x
      yield y ]