Haskell: Filtering a list based on a predicate for all other elements in the list

user_12632986 0
Viewed 128

I have a list of natural numbers [1..n] (this list is never empty) and I would like to filter each element by testing a predicate with all other elements in the list. I would like to return a list of those numbers who never fulfilled the predicate. My idea is this:

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

I am testing if the length is equal to 1 since for x==y the predicate returns true.

This does work as intended, however, I was wondering if there is a cleaner way to do this. I'm not really looking for more performance, but rather a more simple solution.

haskell
1 Answers

As far as complexity, I don't think you can do better than quadratic, since, after all, the very definition of the problem is to test each element with each other. So unless there is more to be known about the structure of the problem, you're stuck there.

But you can perhaps cut down on the performance somewhat by stopping early. Calculating length every time means enumerating all elements from 1 to n, but you don't actually need that, right? You can stop enumerating once pred returns True for the first time. To do that you can use and:

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

Or, alternatively, you can move the predicate to the condition part and then test the resulting list for emptiness:

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

But I like the former variant better, because it better describes the intent.

Finally, I think this would look cleaner as a list comprehension:

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

But that's a matter of personal taste, of course.

user_1802860
Related