Uso de elementos de lista e índices juntos

Question

Siempre me ha resultado incómodo tener una función o expresión que requiera el uso de los valores, así como los índices, de una lista (o matriz, se aplica igual) en Haskell.

escribí validQueens abajo mientras que la experimentación con el problema N-queens here ...

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

no me importa para el uso de la indexación, todos los signos más y sus menos, etc. Se siente descuidado. Se me ocurrió lo siguiente:

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 

haber sido inspirado por enumerate de Python (no es que los préstamos conceptos imperativo es necesariamente una gran idea). Parece mejor en concepto, pero snd y fst por todas partes es una mierda. También es, al menos a primera vista, más costoso tanto en tiempo como en espacio. No estoy seguro de si me gusta o no.

Así que en resumen, no estoy realmente satisfecho con cualquiera

1. iteración a través por el índice delimitada por longitudes, o peor aún, off-by-unos y dos
2. tuplas Índice de elementos

¿Alguien ha encontrado un patrón que le parezca más elegante que cualquiera de los anteriores? Si no, ¿hay alguna razón de peso para que uno de los métodos anteriores sea superior?

Answer 1

endeudamiento enumerate está muy bien y animado. Sin embargo, se puede hacer un perezoso poco a negarse a calcular la longitud de su argumento:

enumerate = zip [0..] 

(De hecho, es común utilizar sólo zip [0..] sin nombrarlo enumerate.) No me queda claro por qué piensa su segundo ejemplo debería ser más costoso en tiempo o espacio. Recuerde: la indexación es O (n), donde n es el índice.Su queja sobre la pesadez de fst y snd se justifica, y se puede remediar con el patrón de coincidencia:

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

Ahora, usted podría ser un poco preocupado por la eficiencia de este doble circuito, ya que la cláusula (j, y) <- l va estar corriendo por todo el lomo de l, cuando en realidad solo queremos que comience donde lo dejamos con (i, x) <- l. Por lo tanto, vamos a escribir una función que implementa esa idea:

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

Habiendo hecho esta función, su función no es demasiado difícil de adaptar. Sacando el predicado en su propia función, se puede utilizar en lugar de alland:

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

O, si lo prefiere sin punto de notación:

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

Answer 2

Las tuplas de elementos índice son algo bastante común en Haskell. Debido zip se detiene cuando la primera lista se detiene, se puede escribir como

enumerate x = zip [0..] x 

que es tanto más elegante y más eficiente (ya que no computa length x por adelantado). De hecho, ni siquiera me molestaría en nombrarlo, ya que zip [0..] es muy corto.

Esto es definitivamente más eficiente que iterar por índice para las listas, porque !! es lineal en el segundo argumento debido a que las listas son listas vinculadas.

Otra forma puede hacer que su programa sea más elegante es usar el patrón de coincidencia en lugar de fst y 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