Was ist ein guter Weg, um Aufgaben zu erledigen, für die Arrays mit Haskell erforderlich sind?

Oft erfordert eine Aufgabe echte Arrays. Nehmen Sie zum Beispiel die Aufgabe, Befunge oder> <> zu implementieren. Ich habe versucht, das ArrayModul dafür zu verwenden, aber es ist wirklich umständlich, da ich das Gefühl habe, viel zu ausführlich zu programmieren. Kann mir jemand helfen, wie man solche Code-Golf-Aufgaben weniger ausführlich und funktionaler löst?

Zunächst empfehle ich Data.Vector , in einigen Fällen eine schönere Alternative zu Data.Array .

Arrayund Vectorsind ideal für einige Memoisierungsfälle, wie in meiner Antwort auf "Finden maximaler Pfade" gezeigt . Einige Probleme lassen sich jedoch nicht einfach in einem funktionalen Stil ausdrücken. Zum Beispiel fordert Problem 28 in Project Euler die Summierung der Zahlen auf den Diagonalen einer Spirale. Sicher, es sollte ziemlich einfach sein, eine Formel für diese Zahlen zu finden, aber die Konstruktion der Spirale ist schwieriger.

Data.Array.ST bietet einen veränderlichen Array-Typ. Allerdings ist die Art Situation ein Chaos: Es verwendet eine Klasse Marray jeden einzelnen seiner Methoden mit Ausnahme zu überlasten runSTArray . Sofern Sie nicht vorhaben, ein unveränderliches Array von einer veränderlichen Array-Aktion zurückzugeben, müssen Sie eine oder mehrere Typensignaturen hinzufügen:

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

Trotzdem fiel meine Lösung für Euler 28 ziemlich gut aus und erforderte diese Typensignatur nicht, weil ich sie verwendete runSTArray.

Verwenden von Data.Map als "veränderbares Array"

Wenn Sie einen veränderlichen Array-Algorithmus implementieren möchten , können Sie auch Data.Map verwenden . Wenn Sie ein Array verwenden, wünschen Sie sich eine Funktion wie diese, die ein einzelnes Element eines Arrays ändert:

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

Leider würde dies das Kopieren des gesamten Arrays erfordern, es sei denn, die Implementierung verwendete eine Copy-on-Write-Strategie, um dies nach Möglichkeit zu vermeiden.

Die gute Nachricht ist, Data.Maphat eine Funktion wie diese, einfügen :

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

Da Mapes intern als ausgeglichener Binärbaum implementiert ist, benötigt es insertnur O (log n) Zeit und Raum und behält die Originalkopie bei. Daher bietet es Mapnicht nur ein etwas effizientes "veränderbares Array", das mit dem funktionalen Programmiermodell kompatibel ist, sondern ermöglicht es Ihnen sogar, "in die Vergangenheit zu reisen", wenn Sie dies wünschen.

Hier ist eine Lösung für Euler 28 mit 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

Die Knallmuster verhindern einen Stapelüberlauf, der dadurch verursacht wird, dass die Akkumulatorelemente (Cursor, Nummer und Karte) erst am Ende verwendet werden. Bei den meisten Code-Golfspielen sollten Eingabefälle nicht groß genug sein, um diese Bestimmung zu benötigen.

Die glatte Antwort lautet: Verwenden Sie keine Arrays. Die nicht ganz so klare Antwort lautet: Versuchen Sie, Ihr Problem so zu überdenken, dass keine Arrays erforderlich sind.

Oft kann ein Problem mit einigen Gedanken überhaupt ohne Array-ähnliche Struktur gelöst werden. Hier ist zum Beispiel meine Antwort auf 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]

Was hier im Code ausgedrückt wird, ist das Muster der Folge von Zahlen, wenn sie um die rechteckige Spirale wachsen. Die Zahlenmatrix selbst musste nicht dargestellt werden.

Der Schlüssel zum Denken über Arrays hinaus besteht darin, darüber nachzudenken, was das vorliegende Problem tatsächlich bedeutet und nicht, wie Sie es als Bytes im RAM darstellen könnten. Dies kommt nur mit Übung (vielleicht ein Grund, warum ich so viel Code-Golf spiele!)

Ein anderes Beispiel ist, wie ich das Finden maximaler Pfade Code-Golf gelöst habe . Dort wird das Verfahren zum zeilenweisen Durchleiten der Teillösungen als Welle durch die Matrix direkt durch die Faltoperation ausgedrückt. Denken Sie daran: Auf den meisten CPUs können Sie das Array nicht als Ganzes gleichzeitig bearbeiten: Das Programm muss es im Laufe der Zeit durchlaufen. Möglicherweise wird zu keinem Zeitpunkt das gesamte Array auf einmal benötigt.

Natürlich werden einige Probleme so angegeben, dass sie von Natur aus Array-basiert sind. Sprachen wie> <>, Befunge oder Brainfuck haben Arrays im Herzen. Auf Arrays kann jedoch auch dort häufig verzichtet werden. Siehe zum Beispiel meine Lösung zur Interpretation von Brainfuck . Der eigentliche Kern seiner Semantik ist ein Reißverschluss . Um so zu denken, konzentrieren Sie sich auf die Zugriffsmuster und die Struktur, die näher an der Bedeutung des Problems liegt. Oft muss dies nicht in ein veränderliches Array gezwungen werden.

Wenn alles andere fehlschlägt und Sie ein Array verwenden müssen, sind die Tipps von @ Joey ein guter Anfang.