Sort list in a list of lists F#

Question

Hello guys,

I'm trying to sort each Position (which is a list) in a Position list. Currently I'm doint like this:

type Position = Position of  list<int * Piece>

and my function:

let SortPositionList positionList : Position list = 
let rec loop list =
    match (list: Position list) with
    | [] -> []
    | hd::tl -> [List.sortBy(fun (x:(int*Piece)) -> fst x)(GetInternStruct(hd))::loop tl]
loop positionList

In my mind, this could be done by recursivelly sorting the actual head of the list and then concat it with the rest of the list, but it's not working. The errors in this function are:

Type mismatch. Expecting a (int * Piece) list list but given a (int * Piece) list list list The type 'int * Piece' does not match the type '(int * Piece) list', in the underlined loop tl

Type mismatch. Expecting a Position list but given a (int * Piece) list list list The type 'Position' does not match the type '(int * Piece) list list', in the underline calling of loop, loop positionList

Hope you can help, thanks in advance

Pedro Dusso

EDIT AList.map passing the sorting function would be a nice aproach?

SOLUTION

let SortPositionList (positionList : Position list) =
    List.map (fun (Position(position)) -> List.sort(position)) positionList

As my Position struct is a (int * Piece) lst, I'm pattern matching it in the anonimous function and sorting it.

Thanks for the answers!

Answer 1

You are doing it wrong. :)

I have no clue what you're trying to do, but looking at your code, I just know it's wrong, and so here's what I see.

First, you have

... List.sortBy blah1 blah2 ...

which is non-idiomatic, you want

... blah2 |> List.sortBy blah1 ...

which will help with the type inference. This kinda segues into the second issue, which is

(fun (x:(int*Piece)) -> fst x)

is nonsense. You could write

(fun (i:int,p:Piece) -> i)

or

(fun (i,p) -> i)

or just

fst

and it would mean the same thing, but what you've written is unintelligible to humans (me, anyway). I expect perhaps that you got into that jam in the first place by not having the pipeline to start maybe.

Finally, more aside-ish, the lack of whitespace in your code sample also makes it unreadable; avoid ever having

)(

without a space in between, and use more horizontal and vertical whitespace to make the parsing of the code more apparent.

This is mostly stylistic and superficial feedback, but I think if you address that, the deep issues about the types not working out will start making more sense and become more readily apparent.

Answer 2

How about just:

let SortPositionList (positionList : Position list) =
    List.map (fun pos -> List.sortBy (fun (index, _) -> index) pos) positionList

What you are then using is a List.map on the Position list, mapping each element (itself a list) to the List.sortBy function. This requires a function that returns a key for comparison. In this case we are using the built in pattern matching to match the index from the 'int * Piece' tuple.

Answer 3

In general, there are two ways of doing things in F#. You can either use recursion explicitly or you can use existing functions. In your case, you need to do two things in a nested way - you need to iterate over the outer list and sort the inner lists. The sorting can be done using List.sortBy and the iteration (projection) can be done using List.map.

To correct your original approach (using recursion) - I simplfied it slightly (because you don't need the loop function - you can make the function itself recursive):

let rec sortPositionList list =  
  match list with 
  | [] -> [] 
  | hd::tl -> 
    // Sort the list of positions first - by storing this as a new value
    // using 'let', you get more readable code (and you can use IntelliSense
    // to explore the type of 'sorted' and understand what's going on)
    let sorted = List.sortBy (fun (x, _) -> x) (GetInternStruct(hd))

    // As Brian suggests, more idiomatic F# encoding of the line would be:
    //   let sorted = GetInternStruct(hd) |> List.sortBy (fun (x, _) -> x)
    // but both of the options would work in this case.

    // Note: The result shouldn't be wrapped in '[ .. ]'. The operator '::'
    // takes an element and a list and returns a new list created by 
    // prepending the element in front of the list
    sorted::(sortPositionList tl)

The solution using existing functions (List.map) has been already posted by JDU. I would just add that he uses partial function application - so the parameter passed to List.map is a function. If this feels confusing, you can rewrite that using lambda function explicitly:

let SortPositionList (positionList) = 
  List.map (fun positions -> 
    List.sortBy (fun (index, _) -> index) positions) positionList 

Which could be more idiomatically written using the pipelining operator and the fst function instead of explicit lambda parameter (as Brian mentioned):

let SortPositionList (positionList) = 
  positionList |> List.map (fun positions -> 
    positions |> List.sortBy fst)  

This means exactly the same thing as the code posted by JDU, but you may find it more readable. Finally, you can write the same thing using sequence expressions (which is perhaps the most elegant option in my opinion):

let SortPositionList (positionList) = 
  [ for positions in positionList do
      yield positions |> List.sortBy fst ]

EDIT The functions as I wrote them here work with values of type (int*Point) list list and not with the type Positions list. To change this, you need to add some wrapping and unwrapping. The recursive implementation should be:

  match list with         // List is always 'Positions', so we use pattern 
  | Positions [] -> []    // matching to unwrap the underlying list in 
  | Positions (hd::tl) -> // both cases
    // Wrap the resulting list into the positions type
    let sorted = Positions(List.sortBy (fun (x, _) -> x) (GetInternStruct(hd)))
    (sorted::(sortPositionList tl))

Similarly, for the List.map implementation:

let SortPositionList (positionList) = 
  positionList |> List.map (fun (Positions positions) -> // pattern matching
    positions |> List.sortBy fst |> Positions)  // wrapping

Answer 4

let apply f (Position xs) = Position(f xs)
let sorts = List.map (apply List.sort)