Qual é uma boa maneira de lidar com tarefas que exigem matrizes usando Haskell?

Geralmente, uma tarefa requer matrizes reais. Tomemos, por exemplo, a tarefa de implementar o Befunge ou> <>. Tentei usar o Arraymódulo para isso, mas é realmente complicado, pois parece que estou codificando muito detalhadamente. Alguém pode me ajudar a resolver essas tarefas de código-golfe menos detalhadas e mais funcionais?

Antes de tudo, recomendo examinar o Data.Vector , uma alternativa mais agradável ao Data.Array em alguns casos.

Arraye Vectorsão ideais para alguns casos de memorização, conforme demonstrado na minha resposta para "Encontrar caminhos máximos" . No entanto, alguns problemas simplesmente não são fáceis de expressar em um estilo funcional. Por exemplo, o Problema 28 no Projeto Euler pede somar os números nas diagonais de uma espiral. Claro, deve ser bem fácil encontrar uma fórmula para esses números, mas construir a espiral é mais desafiador.

Data.Array.ST fornece um tipo de matriz mutável. No entanto, a situação do tipo é uma bagunça: ela usa uma classe MArray para sobrecarregar cada um de seus métodos, exceto o runSTArray . Portanto, a menos que você planeje retornar uma matriz imutável a partir de uma ação de matriz mutável, será necessário adicionar uma ou mais assinaturas de tipo:

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

No entanto, minha solução para o Euler 28 resultou muito bem e não exigia a assinatura desse tipo porque eu o usava runSTArray.

Usando Data.Map como uma "matriz mutável"

Se você deseja implementar um algoritmo de matriz mutável, outra opção é usar o Data.Map . Quando você usa uma matriz, você deseja ter uma função como esta, que altera um único elemento de uma matriz:

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

Infelizmente, isso exigiria a cópia de toda a matriz, a menos que a implementação usasse uma estratégia de copiar na gravação para evitá-la quando possível.

A boa notícia é que, Data.Maptem uma função como esta, insira :

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

Como Mapé implementado internamente como uma árvore binária balanceada, insertocupa apenas O (log n) tempo e espaço e preserva a cópia original. Portanto, Mapnão apenas fornece uma "matriz mutável" um tanto eficiente que é compatível com o modelo de programação funcional, mas também permite "voltar no tempo", se assim o desejar.

Aqui está uma solução para o Euler 28 usando o 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

Os padrões de estrondo impedem que um estouro de pilha causado pelos itens do acumulador (cursor, número e mapa) não seja usado até o final. Para a maioria dos golfistas de código, os casos de entrada não devem ser grandes o suficiente para precisar dessa provisão.

A resposta rápida é: Não use matrizes. A resposta não tão simplista é: tente repensar seu problema para que ele não precise de matrizes.

Freqüentemente, um problema com alguma reflexão pode ser resolvido sem nenhuma matriz semelhante à estrutura. Por exemplo, aqui está a minha resposta para 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]

O que é expresso no código aqui é o padrão da sequência de números à medida que crescem em torno da espiral retangular. Não havia necessidade de representar a própria matriz de números.

A chave para pensar além das matrizes é pensar sobre o que o problema em questão realmente significa, não como você pode representá-lo como bytes na RAM. Isso só vem com a prática (talvez uma razão pela qual eu tanto codigo de golfe!)

Outro exemplo é como eu resolvi a busca de caminhos máximos code-golf. Lá, o método de passar as soluções parciais como uma onda através da matriz, linha por linha, é expresso diretamente pela operação de dobra. Lembre-se: Na maioria das CPUs, você não pode lidar com a matriz como um todo de uma só vez: o programa terá que operar com ela ao longo do tempo. Pode não ser necessário todo o array de uma só vez, a qualquer momento.

Obviamente, alguns problemas são declarados de forma a serem inerentemente baseados em array. Idiomas como> <>, Befunge ou Brainfuck têm matrizes no coração. No entanto, mesmo lá, as matrizes geralmente podem ser dispensadas. Por exemplo, veja minha solução para interpretar Brainfuck , o verdadeiro núcleo de sua semântica é um zíper . Para começar a pensar dessa maneira, concentre-se nos padrões de acesso e na estrutura mais próxima do significado do problema. Muitas vezes, isso não precisa ser forçado a uma matriz mutável.

Quando tudo mais falhar e você precisar usar uma matriz - as dicas do @ Joey são um bom começo.