Cubesumming in haskell

Question

Haskell ha la funzione di somma

sum :: Num a => [a] -> a 

Quale può essere ben composto sommare una matrice da

sum . map sum :: Num a => [[a]] -> a 

Andando più profondo, tuttavia, come somma di un cubo, crea la restrizione Num [a]

sum . map sum . map sum :: (Num a, Num [a]) => [[[a]]] -> a 

Il che, se ci pensate, è naturale. Quindi, con il precedente tentativo di definire la funzione sumcube che esplode in faccia, dobbiamo trovare un percorso diverso. Uno di questi tentativi potrebbe essere:

sum . map sum . map (map sum) :: Num a => [[[a]]] -> a 

Che non sembra naturale come la funzione di sommatore.

Nella mia ricerca per posessing degli strumenti mentali per la risoluzione dei problemi in Haskell, sono interessato a sapere come affrontare questo problema di sommare una struttura di qualsiasi profondità, ad esempio, impilando map sum s come nel mio terzo esempio di codice. È possibile? E in tal caso, come lo faresti?

Answer 1

Dovrai lavorare da dentro. Quando si ha una funzione f per sommare una struttura dati, quindi sum . map f è il modo di sommare un elenco di tali strutture dati.

     sum :: Num a => [a] -> a 
      sum . map sum :: Num a => [[a]] -> a 
sum . map (sum . map sum) :: Num a => [[[a]]] -> a 

Answer 2

In primo luogo, c'è Template Haskell (estensione GHC). Oppure si potrebbe usare un data che supporta arbitrario lista profonda nidificazione così:

data Tree a = Leaf a | Node [Tree a] 

sumTree (Leaf x) = x 
sumTree (Node xs) = (sum . map sumTree) xs 

main = print $ sumTree $ Node [ Node [Leaf 3, Leaf 4, Leaf 5] 
           , Node [Leaf 1, Leaf 4, Leaf 2]] 

che stamperà 19 qui. Tuttavia questo non garantisce che tutte le foglie abbiano la stessa profondità di annidamento e non so come costruirla dagli elenchi.

Answer 3

Forse questo? Assume l'associatività, ma l'aggiunta di un nuovo livello è semplice

sum . concat . concat :: Num c => [[[c]]] -> c 

Answer 4

E le tipette?

class Summable a where 
    total :: a -> Int 

instance Summable Int where 
    total = id 

instance Summable x => Summable [x] where 
    total = sum . map total 

total ([[[1,2,3],[4,5]],[[6],[7,8,9,10]]] :: [[[Int]]]) 
--55 

Answer 5

Sembra più naturale per me per definire di sum in termini di dimensioni del precedente sum una dimensione ulteriore.

-- given sum :: Num a => [a] -> a 

sum2 :: [[a]] -> a 
sum2 = sum . map sum 

sum3 :: [[[a]]] -> a 
sum3 = sum . map sum2 

sum4 :: [[[[a]]]] -> a 
sum4 = sum . map sum3 

Questa è fondamentalmente la stessa idea di quello che ha detto Sjoerd. Se si desidera utilizzare solo map e sum e non refactoring sottoespressioni comuni in nomi utili ... quindi utilizzare il ragionamento equazionale per sostituire le funzioni personalizzate sum2, sum3, ecc