Utilisation conjointe d'éléments de liste et d'indices

Question

J'ai toujours trouvé gênant d'avoir une fonction ou une expression qui nécessite l'utilisation des valeurs, ainsi que des indices, d'une liste (ou d'un tableau, cela revient au même) en Haskell.

J'ai écrit validQueens ci-dessous en expérimentant avec le problème des N-queens. aquí ...

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

Je n'ai pas aimé l'utilisation de l'indexation, tous les avantages et les inconvénients, etc. C'est un peu négligé. Je suis arrivé à ce qui suit :

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 

en s'inspirant de Python enumerate (non pas que l'emprunt de concepts impératifs soit nécessairement une bonne idée). Le concept semble meilleur, mais snd et fst partout, ça craint. C'est aussi, du moins à première vue, plus coûteux en temps et en espace. Je ne sais pas si je l'aime mieux ou non.

Donc, en résumé, je ne suis pas vraiment satisfait de l'un ou l'autre des éléments suivants

1. Itération à travers un index limité par des longueurs, ou pire, par des nombres entiers et des nombres doubles.
2. Tuples d'éléments d'index

Quelqu'un a-t-il trouvé un modèle qu'il trouve plus élégant que l'un ou l'autre des modèles ci-dessus ? Sinon, y a-t-il une raison impérieuse pour laquelle l'une des méthodes ci-dessus est supérieure ?

Answer 1

Emprunter enumerate est bien et encouragée. Cependant, on peut le rendre un peu plus paresseux en refusant de calculer la longueur de son argument :

enumerate = zip [0..]

(En fait, il est courant d'utiliser simplement zip [0..] sans le nommer enumerate .) Je ne comprends pas pourquoi vous pensez que votre deuxième exemple devrait être plus coûteux en temps ou en espace. Rappelez-vous : l'indexation est O(n), où n est l'index. Votre plainte concernant la lourdeur de fst et snd est justifiée, et peut être corrigée par le filtrage de motifs :

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

Maintenant, vous pourriez être un peu inquiet quant à l'efficacité de cette double boucle, puisque la clause (j, y) <- l va courir le long de toute la colonne vertébrale de l alors que nous voulons simplement qu'il reprenne là où nous nous sommes arrêtés avec (i, x) <- l . Alors, écrivons une fonction qui implémente cette idée :

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

Ayant réalisé cette fonction, votre fonction n'est pas trop difficile à adapter. En retirant le prédicat dans sa propre fonction, nous pouvons utiliser all au lieu de and :

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

Ou, si vous préférez la notation sans points :

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

Answer 2

Les tuples d'éléments d'index sont une chose assez courante à faire en Haskell. Parce que zip s'arrête lorsque la première liste s'arrête, vous pouvez les écrire comme suit

enumerate x = zip [0..] x

qui est à la fois plus élégante et plus efficace (puisqu'elle ne calcule pas length x à l'avant). En fait, je ne prendrais même pas la peine de le nommer, car zip [0..] est si courte.

Cette méthode est définitivement plus efficace que l'itération par index pour les listes, car !! est linéaire dans le second argument, car les listes sont des listes liées.

Une autre façon de rendre votre programme plus élégant est d'utiliser le filtrage de motifs au lieu du filtrage d'images. fst et 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