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

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

Я написал validQueens ниже, экспериментируя с проблемой N-queens здесь...

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

Заимствование 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..]

Ответ 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