Сортировать список в списке списков F #

Question

Я пытаюсь отсортировать каждую позицию (которая является списком) в списке позиций.В настоящее время я делаю вот так:

type Position = Position of  list<int * Piece>

и моя функция:

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

На мой взгляд, это можно сделать путем рекурсивной сортировки фактического заголовка списка, а затемэто с остальной частью списка, но это не работает.Ошибки в этой функции:

Несоответствие типов.Ожидается список со списком (int * Piece), но задан список списка со списком (int * Piece) Тип 'int * Piece' не соответствует типу списка (int * Piece) в подчеркнутом loop tl

Несоответствие типов.Ожидается список позиций, но задан список списков (int * Piece) Тип 'Позиция' не соответствует типу списка списков (int * Piece) в подчеркивании вызова цикла, loop positionList

Надеюсь, вы можете помочь, заранее спасибо

Педро Дуссо

РЕДАКТИРОВАТЬ AList.map передача функции сортировки будет хорошим подходом?

SOLUTION

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

Поскольку моя структура Position является (int * Piece) lst, я сопоставляю ее с шаблоном в анонимной функции и сортирую.

Спасибо за ответы!

Answer 1

Как насчет просто:

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

Затем вы используете List.map в списке Position, отображающий каждый элемент (сам список) в функцию List.sortBy. Для этого требуется функция, которая возвращает ключ для сравнения. В этом случае мы используем встроенное сопоставление с образцом для сопоставления с индексом из кортежа int * Piece.

Answer 2

В общем, есть два способа сделать что-то в F #.Вы можете использовать рекурсию явно или использовать существующие функции.В вашем случае вам нужно сделать две вещи во вложенном виде - вам нужно перебрать внешний список и отсортировать внутренние списки.Сортировка может быть выполнена с использованием List.sortBy, а итерация (проекция) - с помощью List.map.

Чтобы исправить исходный подход (с использованием рекурсии) - я немного упростил его (потому что вам не нужнофункция loop - вы можете сделать саму функцию рекурсивной):

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)

Решение с использованием существующих функций (List.map) уже опубликовано JDU.Я бы просто добавил, что он использует частичное применение функции - поэтому параметр, переданный в List.map, является функцией.Если это вызывает недоумение, вы можете переписать это с использованием лямбда-функции в явном виде:

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

Что может быть написано более идиотски с использованием оператора конвейеризации и функции fst вместо явного параметра лямбда (как упоминал Брайан):

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

Это означает то же самое, что и код, опубликованный JDU, но вы можете найти его более читабельным.Наконец, вы можете написать то же самое, используя выражения последовательности (что, пожалуй, является наиболее элегантным вариантом):

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

EDIT Функции, которые я здесь написал, работают со значениямитипа (int*Point) list list, а не типа Positions list.Чтобы изменить это, вам нужно добавить некоторые упаковки и распаковки.Рекурсивная реализация должна быть:

  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))

Аналогично, для реализации List.map:

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

Answer 3

Вы делаете это неправильно. :)

Понятия не имею, что вы пытаетесь сделать, но, глядя на ваш код, я просто знаю, что это неправильно, и вот что я вижу.

Во-первых, у вас есть

... List.sortBy blah1 blah2 ...

что не идиоматично, вы хотите

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

, который поможет с выводом типа. Это своего рода переходит во второй выпуск, который является

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

ерунда Вы могли бы написать

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

или

(fun (i,p) -> i)

или просто

fst

и это означало бы то же самое, но то, что вы написали, непостижимо для людей (во всяком случае, для меня). Я ожидаю, что, возможно, вы попали в этот джем в первую очередь из-за того, что у вас не было возможности запустить трубопровод.

Наконец, еще больше, нехватка пробелов в вашем примере кода также делает его нечитаемым; избегать когда-либо

)(

без пробела и используйте больше горизонтальных и вертикальных пробелов, чтобы сделать синтаксический анализ кода более очевидным.

Это в основном стилистическая и поверхностная обратная связь, но я думаю, что если вы решите это, глубокие проблемы с типами, которые не работают, станут более понятными и станут более очевидными.

Answer 4

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