Блог

У меня есть список натуральных чисел [1..n] (этот список никогда не бывает пустым), и я хотел бы отфильтровать каждый элемент, проверив предикат со всеми другими элементами в списке. Я хотел бы вернуть список тех чисел, которые никогда не выполняли предикат. Моя идея заключается в следующем:

 filter (x -> 1 == length [y| y <- [1..n], pred y x]) [1..n]
 

Я проверяю, равна ли длина 1, поскольку для x==y предиката возвращается true.

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

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

Но, возможно, вы можете несколько снизить производительность, остановившись раньше. Вычисление length каждый раз означает перечисление всех элементов от 1 до n , но вам это на самом деле не нужно, верно? Вы можете прекратить перечисление после pred первого возврата True . Для этого вы можете использовать and :

 filter (x -> and [not (pred y x) | y <- [1..n], y /= x]) [1..n]
 

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

 filter (x -> null [y <- [1..n], y /= x amp;amp; pred y x]) [1..n]
 

Но мне больше нравится первый вариант, потому что он лучше описывает намерение.

Наконец, я думаю, что это выглядело бы чище как понимание списка:

 [ x
| x <- [1..n]
, and [not (pred y x) | y <- [1..n], y /= x]
]
 

Но это, конечно, вопрос личного вкуса.