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

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

я написал 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

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

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

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

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

Источник

2 ответа

Решение

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

Кортежи с индексными элементами - довольно распространенная вещь в 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
Источник
Другие вопросы по тегам