Using list elements and indices together

Question

I've always found it awkward to have a function or expression that requires use of the values, as well as indices, of a list (or array, applies just the same) in Haskell.

I wrote validQueens below while experimenting with the N-queens problem here ...

validQueens x = 
     and [abs (x!!i - x!!j) /= j-i | i<-[0..length x - 2], j<-[i+1..length x - 1]]

I didn't care for the use of indexing, all the plus and minuses, etc. It feels sloppy. I came up with the following:

enumerate x = zip [0..length x - 1] x

validQueens' :: [Int] -> Bool
validQueens' x = and [abs (snd j - snd i) /= fst j - fst i | i<-l, j<-l, fst j > fst i]
                   where l = enumerate x 

being inspired by Python's enumerate (not that borrowing imperative concepts is necessarily a great idea). Seems better in concept, but snd and fst all over the place kinda sucks. It's also, at least at first glance, costlier both in time and space. I'm not sure whether or not I like it any better.

So in short, I am not really satisfied with either

1. Iterating thru by index bounded by lengths, or even worse, off-by-ones and twos
2. Index-element tuples

Has anyone found a pattern they find more elegant than either of the above? If not, is there any compelling reason one of the above methods is superior?

Finish

Answer 1

Borrowing enumerate is fine and encouraged. However, it can be made a bit lazier by refusing to calculate the length of its argument:

enumerate = zip [0..]

(In fact, it's common to just use zip [0..] without naming it enumerate.) It's not clear to me why you think your second example should be costlier in either time or space. Remember: indexing is O(n), where n is the index. Your complaint about the unwieldiness of fst and snd is justified, and can be remedied with pattern-matching:

validQueens' xs = and [abs (y - x) /= j - i | (i, x) <- l, (j, y) <- l, i < j]
    where l = zip [0..] xs

Now, you might be a bit concerned about the efficiency of this double loop, since the clause (j, y) <- l is going to be running down the entire spine of l, when really we just want it to start where we left off with (i, x) <- l. So, let's write a function that implements that idea:

pairs :: [a] -> [(a, a)]
pairs xs = [(x, y) | x:ys <- tails xs, y <- ys]

Having made this function, your function is not too hard to adapt. Pulling out the predicate into its own function, we can use all instead of and:

validSingleQueen ((i, x), (j, y)) = abs (y - x) /= j - i
validQueens' xs = all validSingleQueen (pairs (zip [0..] xs))

Or, if you prefer point-free notation:

validQueens' = all validSingleQueen . pairs . zip [0..]

Via

Answer 2

Index-element tuples are quite a common thing to do in Haskell. Because zip stops when the first list stops, you can write them as

enumerate x = zip [0..] x

which is both more elegant and more efficient (as it doesn't compute length x up front). In fact I wouldn't even bother naming it, as zip [0..] is so short.

This is definitely more efficient than iterating by index for lists, because !! is linear in the second argument due to lists being linked lists.

Another way you can make your program more elegant is to use pattern-matching instead of fst and snd:

validQueens' :: [Int] -> Bool
validQueens' x = and [abs (j2 - i2) /= j1 - i1 | (i1, i2) <-l, (j1, j2) <-l, j1 > i1]
                   where l = zip [0..] x

Hedges