Jaki jest dobry sposób radzenia sobie z zadaniami wymagającymi tablic przy użyciu Haskell?

Często zadanie wymaga prawdziwych tablic. Weźmy na przykład zadanie zaimplementowania Befunge lub> <>. Próbowałem do tego użyć Arraymodułu, ale jest to bardzo kłopotliwe, ponieważ wydaje mi się, że koduję o wiele za bardzo. Czy ktoś może mi pomóc w rozwiązywaniu takich zadań związanych z golfem mniej gadatliwym i bardziej funkcjonalnym?

Przede wszystkim polecam przyjrzeć się Data.Vector , w niektórych przypadkach ładniejszą alternatywą dla Data.Array .

Arrayi Vectorsą idealne do niektórych przypadków zapamiętywania, jak pokazano w mojej odpowiedzi na „Znajdowanie maksymalnych ścieżek” . Jednak niektóre problemy po prostu nie są łatwe do wyrażenia w funkcjonalnym stylu. Na przykład problem 28 w projekcie Euler wymaga zsumowania liczb na przekątnych spirali. Jasne, znalezienie wzoru na te liczby powinno być dość łatwe, ale zbudowanie spirali jest trudniejsze.

Data.Array.ST zapewnia zmienny typ tablicy. Jednak sytuacja typu jest bałaganem: używa klasy MArray do przeciążenia każdej z metod oprócz runSTArray . Tak więc, chyba że planujesz zwrócić niezmienną tablicę z działania zmiennej tablicy, będziesz musiał dodać jeden lub więcej podpisów typu:

import Control.Monad.ST
import Data.Array.ST

foo :: Int -> [Int]
foo n = runST $ do
    a <- newArray (1,n) 123 :: ST s (STArray s Int Int) -- this type signature is required
    sequence [readArray a i | i <- [1..n]]

main = print $ foo 5

Niemniej jednak moje rozwiązanie Euler 28 okazało się całkiem nieźle i nie wymagało tego podpisu, ponieważ go użyłem runSTArray.

Używanie Data.Map jako „tablicy zmiennych”

Jeśli chcesz zaimplementować zmienny algorytm tablicowy, inną opcją jest użycie Data.Map . Kiedy używasz tablicy, żałujesz, że nie masz takiej funkcji, która zmienia pojedynczy element tablicy:

writeArray :: Ix i => i -> e -> Array i e -> Array i e

Niestety, wymagałoby to skopiowania całej tablicy, chyba że implementacja zastosowała strategię kopiowania przy zapisie, aby tego uniknąć, jeśli to możliwe.

Dobrą wiadomością jest to, że Data.Mapma taką funkcję, wstaw :

insert :: Ord k => k -> a -> Map k a -> Map k a

Ponieważ Mapjest implementowany wewnętrznie jako zrównoważone drzewo binarne, insertzajmuje tylko O ​​(log n) czas i przestrzeń oraz zachowuje oryginalną kopię. Dlatego Mapnie tylko zapewnia nieco wydajną „zmienną tablicę”, która jest kompatybilna z funkcjonalnym modelem programowania, ale pozwala nawet „cofnąć się w czasie”, jeśli chcesz.

Oto rozwiązanie Euler 28 za pomocą Data.Map:

{-# LANGUAGE BangPatterns #-}

import Data.Map hiding (map)
import Data.List (intercalate, foldl')

data Spiral = Spiral Int (Map (Int,Int) Int)

build :: Int -> [(Int,Int)] -> Map (Int,Int) Int
build size = snd . foldl' move ((start,start,1), empty) where
    start = (size-1) `div` 2
    move ((!x,!y,!n), !m) (dx,dy) = ((x+dx,y+dy,n+1), insert (x,y) n m)

spiral :: Int -> Spiral
spiral size
    | size < 1  = error "spiral: size < 1"
    | otherwise = Spiral size (build size moves) where
        right   = (1,0)
        down    = (0,1)
        left    = (-1,0)
        up      = (0,-1)
        over n  = replicate n up ++ replicate (n+1) right
        under n = replicate n down ++ replicate (n+1) left
        moves   = concat $ take size $ zipWith ($) (cycle [over, under]) [0..]

spiralSize :: Spiral -> Int
spiralSize (Spiral s m) = s

printSpiral :: Spiral -> IO ()
printSpiral (Spiral s m) = do
    let items = [[m ! (i,j) | j <- [0..s-1]] | i <- [0..s-1]]
    mapM_ (putStrLn . intercalate "\t" . map show) items

sumDiagonals :: Spiral -> Int
sumDiagonals (Spiral s m) =
    let total = sum [m ! (i,i) + m ! (s-i-1, i) | i <- [0..s-1]]
     in total-1 -- subtract 1 to undo counting the middle twice

main = print $ sumDiagonals $ spiral 1001

Wzory uderzenia zapobiegają przepełnieniu stosu spowodowanemu przez to, że przedmioty akumulatorowe (kursor, liczba i mapa) nie były używane do samego końca. W przypadku większości golfów kodowych przypadki wprowadzania nie powinny być wystarczająco duże, aby potrzebować tego przepisu.

Odpowiedź glib brzmi: nie używaj tablic. Niezbyt glibowa odpowiedź brzmi: spróbuj przemyśleć swój problem, aby nie potrzebował tablic.

Często problem z niektórymi myślami można rozwiązać bez jakiejkolwiek struktury podobnej do tablicy. Na przykład oto moja odpowiedź na Euler 28:

-- | What is the sum of both diagonals in a 1001 by 1001 spiral?
euler28 = spiralDiagonalSum 1001

spiralDiagonalSum n
    | n < 0 || even n = error "spiralDiagonalSum needs a positive, odd number"
    | otherwise = sum $ scanl (+) 1 $ concatMap (replicate 4) [2,4..n]

To, co wyraża się w tym kodzie, to wzór sekwencji liczb rosnących wokół prostokątnej spirali. Nie było potrzeby przedstawiania samej macierzy liczb.

Kluczem do myślenia poza macierzami jest zastanowienie się, co tak naprawdę oznacza dany problem, a nie jak można go przedstawić jako bajty w pamięci RAM. To po prostu przychodzi z treningiem (być może powodem, dla którego tak często gram w golfa!)

Innym przykładem jest to, w jaki sposób rozwiązałem wyszukiwanie maksymalnych ścieżek golfa kodu. Tam metoda przepuszczania częściowych rozwiązań w postaci fali przez matrycę, rząd po rzędzie, jest wyrażana bezpośrednio przez operację składania. Pamiętaj: na większości procesorów nie możesz poradzić sobie z tablicą jako całością: program będzie musiał działać przez nią z czasem. Może nie potrzebować całej tablicy jednocześnie.

Oczywiście niektóre problemy są określone w taki sposób, że są z natury oparte na tablicy. Języki takie jak> <>, Befunge lub Brainfuck mają w sercu tablice. Jednak nawet tam często można zrezygnować z tablic. Na przykład zobacz moje rozwiązanie interpretacji Brainfuck , prawdziwym rdzeniem jego semantyki jest zamek błyskawiczny . Aby zacząć myśleć w ten sposób, skoncentruj się na wzorcach dostępu i strukturze bliższej znaczeniu problemu. Często nie trzeba tego zmuszać do modyfikowania tablicy.

Gdy wszystko inne zawiedzie i musisz użyć tablicy - wskazówki @ Joeya to dobry początek.