F # функция, чтобы проверить, отсортирован ли список или нет - PullRequest
Новая
       10

F # функция, чтобы проверить, отсортирован ли список или нет

2 голосов
/ 04 сентября 2010

Мне нужно написать функцию, которая возвращает true, если данный список отсортирован в порядке возрастания. Пустой и 1-элементный списки отсортированы. Кроме того, [5,12,12] должно возвращать true.

Я написал функцию, которая работает: 

let rec isSorted (l: int list) = 
    match l with
    | [] -> true
    | [x] -> true
    | [x;y] -> x <= y
    | x::y::xr -> if x > y then false else isSorted([y] @ xr);

Но, похоже, это немного не так ... Я думаю, что должен быть более простой способ сделать это? Ненавижу, что должен соответствовать 4 случаям, но я не могу понять, как сделать это умнее.

Есть ли лучшие решения?

Ответы [ 4 ]

14 голосов
/ 04 сентября 2010

Вы можете комбинировать существующие функции: 

let isAscending l = l |> Seq.pairwise |> Seq.forall (fun (a, b) -> a <= b)

printfn "%b" (isAscending []) // true
printfn "%b" (isAscending [1]) // true
printfn "%b" (isAscending [5;12]) // true
printfn "%b" (isAscending [5;12;12]) // true
printfn "%b" (isAscending [5;12;12;11]) // false
7 голосов
/ 04 сентября 2010

Ну, никогда не говори 

[y] @ xr

когда 

y :: xr

будет так же хорошо. (В общем, @ - это кодовый запах.)

Вроде придирчиво, но последняя строка может быть 

| x::((y::_)as t) -> if x > y then false else isSorted(t)

и избавит вас от каких-либо выделений.

Теперь вам нужен третий случай? Что произойдет, если вы удалите его?

5 голосов
/ 10 сентября 2010

Возвращаясь к исходному коду (в отличие от предложенных библиотечных вызовов), я бы сказал, что вы можете сделать несколько улучшений:

  • Третий случай совпадения действительно не нужен (былуже упоминалось).
  • Во втором случае вы не хотите давать значение имени, вы не получаете к нему доступ.
  • В четвертом случае это выглядит неправильноразобрать y::xr просто чтобы снова сшить его вместе с [y] @ xr (или y::xr).Выражение as кажется лучше.
  • Вы просто объединяете два логических результата, if..then выглядит немного неуместно.

Я предложил следующую пересмотренную версию: 

let rec isSorted l =
    match l with
    | [] | [_] -> true
    | h1::(h2::_ as tail) -> h1 <= h2 && isSorted tail

Сомневаюсь, что он более эффективен, чем оригинал, но на глаз легче.

2 голосов
/ 04 сентября 2010

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

let isSorted l = l = (l |> List.sort)

...