Tutorial :Sort list in a list of lists F#


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?


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!


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  


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.


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)  


(fun (i,p) -> i)  

or just


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.


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

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Next Post »