Совместное использование элементов списка и индексов

Question

Мне всегда было неудобно иметь функцию или выражение, которое требует использования значений, а также индексов списка (или массива, применяемого точно так же) в Haskell.

Iнаписал validQueens ниже, когда экспериментировал с проблемой N-ферзей здесь ...

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

Меня не волновало использование индексации, всех плюсов и минусов и т. д.Это чувствует себя неряшливо.Я придумал следующее:

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 

, вдохновленный Python enumerate (не то, что заимствование императивных понятий обязательно является хорошей идеей).Кажется лучше в концепции, но snd и fst повсюду вроде как отстой.Это также, по крайней мере, на первый взгляд, дороже как во времени, так и в пространстве.Я не уверен, нравится мне это или нет.

Короче говоря, я не очень доволен либо

1. Итерацией по индексу, ограниченному по длине, или дажехуже, по одному и по двое
2. кортежи с индексными элементами

Кто-нибудь нашел шаблон, который они находят более элегантным, чем любой из вышеперечисленных?Если нет, то есть ли убедительная причина, по которой один из вышеперечисленных методов лучше?

Answer 1

Заимствование enumerate хорошо и поощряется. Однако это можно сделать немного ленивее, отказавшись вычислить длину аргумента:

enumerate = zip [0..]

(На самом деле, обычно стоит просто использовать zip [0..], не называя его enumerate.) Мне непонятно, почему вы считаете, что ваш второй пример должен быть более дорогостоящим во времени или пространстве. Помните: индексирование - это O (n), где n - это индекс. Ваша жалоба на громоздкость fst и snd обоснована и может быть исправлена ​​путем сопоставления с образцом:

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

Теперь вы можете быть немного обеспокоены эффективностью этого двойного цикла, так как пункт (j, y) <- l будет проходить по всему позвоночнику l, когда на самом деле мы просто хотим, чтобы он начинался там, где мы оставили с (i, x) <- l. Итак, давайте напишем функцию, которая реализует эту идею:

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

Сделав эту функцию, ваша функция не слишком сложна для адаптации. Извлекая предикат в его собственную функцию, мы можем использовать all вместо and:

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

Или, если вы предпочитаете бессмысленную запись:

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

Answer 2

Кортежи с индексными элементами - довольно распространенная вещь в Haskell. Поскольку zip останавливается при остановке первого списка, вы можете записать их как

enumerate x = zip [0..] x

, который является одновременно более элегантным и эффективным (так как он не вычисляет length x заранее). На самом деле, я бы даже не стал называть это, так как zip [0..] такой короткий.

Это определенно более эффективно, чем итерация по спискам для списков, потому что !! является линейным во втором аргументе из-за того, что списки являются связанными списками.

Другой способ сделать вашу программу более элегантной - использовать сопоставление с шаблоном вместо fst и 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