Używanie elementów listy i indeksów razem

Question

Zawsze uważałem, że nie pasuje do funkcji lub wyrażenia, które wymaga użycia wartości, a także indeksów, listy (lub tablicy, stosuje się tak samo) w Haskell.

pisałem validQueens poniżej podczas eksperymentowania z problemem N-królowych here ...

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

nie dbałem za korzystanie z indeksowaniem, wszystko plus i minusy, itd. Wydaje się niechlujstwa. Wpadłem poniżej:

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 

inspirowana przez enumerate Pythona (nie że pożyczkowe nadrzędnymi pojęć zawsze jest dobrym pomysłem). Wygląda na to, że jest lepszy, ale w każdym miejscu jest trochę sroga. Jest to również, przynajmniej na pierwszy rzut oka, droższe zarówno w czasie, jak i przestrzeni. Nie jestem pewien, czy mi się to podoba, czy nie.

Tak w skrócie, nie jestem naprawdę zadowolony z obu

1. iteracji thru indeksem ograniczonym długości, lub nawet gorzej, off-by-jedynek i dwójek
2. Index-element krotki

Czy ktoś znalazł wzór, który jest bardziej elegancki niż któryś z powyższych? Jeśli nie, czy istnieje jakiś ważny powód, dla którego jedna z powyższych metod jest lepsza?

Answer 1

ZACIĄGANIA enumerate jest w porządku i zachęcać. Jednak może to być trochę leniwy odmawiając obliczyć długość swojej tezy:

enumerate = zip [0..] 

(W rzeczywistości, to jest wspólne dla prostu użyć zip [0..] bez nazywania go enumerate). To nie jest dla mnie jasne, dlaczego myślisz Twój drugi przykład powinien być droższy w danym czasie lub przestrzeni. Pamiętaj: indeksowanie to O (n), gdzie n to indeks.Skarga o wpływa to na poręczność z fst i snd jest uzasadnione i mogą być usunięte z wzorca dopasowywania:

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

Teraz, być może nieco zaniepokojony efektywność tej podwójnej pętli, ponieważ klauzula (j, y) <- l dzieje do biegania wzdłuż całego kręgosłupa l, kiedy naprawdę chcemy po prostu zacząć od miejsca, w którym skończyliśmy z (i, x) <- l. Napiszmy więc funkcję, która implementuje ten pomysł:

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

Po wykonaniu tej funkcji nie jest zbyt trudno dostosować twoją funkcję. Wyciąganie predykat do własnej funkcji, możemy użyć all zamiast and:

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

Lub, jeśli wolisz punktową wolne notacji:

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

Answer 2

Krotki indeksu są dość powszechne w Haskell. Ponieważ zip zatrzymuje się, gdy pierwsza lista przystanków, można zapisać je jako

enumerate x = zip [0..] x 

który jest zarówno bardziej elegancki i bardziej wydajne (gdyż nie obliczyć length x aż przodu). W rzeczywistości nawet nie zawracałbym sobie głowy nazewnictwem, ponieważ zip [0..] jest tak krótki.

Jest to zdecydowanie bardziej efektywne niż powtarzanie indeksu dla list, ponieważ !! jest liniowy w drugim argumencie z powodu list będących połączonymi listami.

Innym sposobem można uczynić program bardziej elegancki jest użycie dopasowywania wzorca zamiast fst i 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