Блог

Главная - Вопросы по программированию - Проверка равномерности проекции по последовательности F#

Проверка равномерности проекции по последовательности F#

#f#

Вопрос:

Я хочу проверить, имеет ли проекция на последовательность одинаковое значение в F#.

Вот что у меня есть:

 module Seq = 

  let isUniformBy (f) (xs : seq<_>) = 
    let l = 
      xs
      |> Seq.map f
      |> Seq.distinct
      |> Seq.truncate 2
      |> Seq.length
    
    l < 2

  let isUniform xs = isUniformBy id xs

printfn "%b" <| Seq.isUniformBy id [ 1; 2; 3 ] // false
printfn "%b" <| Seq.isUniformBy id [ 1; 1; 1 ] // true
printfn "%b" <| Seq.isUniformBy id [ ] // true
printfn "%b" <| Seq.isUniformBy id [ 1; 1 ] // true
printfn "%b" <| Seq.isUniformBy id [ 1; 1; 2 ] // false
printfn "%b" <| Seq.isUniformBy id [ 1; 2 ] // false
printfn "%b" <| Seq.isUniformBy (fun x -> x % 2) [ 2; 4; 6; 8 ] // true

Мне было интересно, есть ли уже встроенная функция для этого?
И если нет, то каков наилучший способ реализовать это?

Ответ №1:

Мы можем свести проблему к сравнению соседних элементов — потому что для обеспечения однородности у нас не может быть элемента, который не совпадает с предыдущим.

Это означает, что нам нужно только проверить, есть ли одна такая пара — нам нужно только перечислить последовательность, пока мы не найдем пару.

 let isUniform xs = 
    xs
    |> Seq.pairwise
    |> Seq.exists (fun (a, b) -> a <> b)
    |> not

let isUniformBy (f) (lst : seq<_>) = 
    lst |> Seq.map f |> isUniform

Базовый метод заключается isUniform в том , чтобы мы могли передать ему проецируемую последовательность isUniformBy , избегая сквозного прохода id . Кроме того, мы используем только O(1) пробел.

Тесты

 assert( Seq.isUniformBy id [ 1; 2; 3 ] = false)
assert( Seq.isUniformBy id [ 1; 1; 1 ] = true)
assert( Seq.isUniformBy id [ ] = true)
assert( Seq.isUniformBy id [ 1; 1 ] = true)
assert( Seq.isUniformBy id [ 1; 1; 2 ] = false)
assert( Seq.isUniformBy id [ 1; 2 ] = false)
assert( Seq.isUniformBy (fun x -> x % 2) [ 2; 4; 6; 8 ] = true)

Комментарии:

1. Мне нравится такой подход, но я думаю , что вы действительно хотите isUniform быть Seq.forall (fun (a, b) -> a = b) или добавить |> not в конце функции.

2. @brianberns Забыл об этом. Спасибо.

Ответ №2:

Вы можете объединить первые два вызова с помощью Seq.distinctBy (ссылка), а затем немного упростить с помощью Seq.tryExactlyOne (ссылка), хотя затем он сообщит false о пустой последовательности:

 let isUniformBy f xs =
    xs
        |> Seq.distinctBy f
        |> Seq.tryExactlyOne
        |> Option.isSome

Ответ №3:

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

 module Seq =
    let isUniformBy f x = Seq.groupBy f x |> Seq.length < 2
    // val isUniformBy : f:('a -> 'b) -> x:seq<'a> -> bool when 'b : equality

[ id, [ 1; 2; 3 ] // false
  id, [ 1; 1; 1 ] // true
  id, [ ]         // true
  id, [ 1; 1 ]    // true
  id, [ 1; 1; 2 ] // false
  id, [ 1; 2 ]    // false
  (fun x -> x % 2), [ 2; 4; 6; 8 ]] // true
|> Seq.iter ((<||) Seq.isUniformBy >> printfn "%b")
Метки: