Cubesumming en Haskell

Question

Haskell tiene la función suma

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

Cuál puede ser muy bien compuesta para resumir una matriz por

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

Profundizando, sin embargo, como la suma de un cubo, crea la restricción Num [a]

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

Que, si lo piensas bien, es natural. Entonces, con el intento anterior de definir la función sumcube explotando en la cara, necesitamos encontrar una ruta diferente. Uno de estos intentos sería:

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

Lo que no parece ser tan natural como la función summatrix.

En mi búsqueda de la posesión de herramientas mentales para la resolución de problemas en Haskell, estoy interesado en saber cómo abordar este problema de sumar una estructura de cualquier profundidad, por ejemplo, apilando map sum como en mi tercer ejemplo de código. ¿Es esto posible? Y en ese caso, ¿cómo lo harías?

Answer 1

Tendrás que trabajar desde adentro hacia afuera. Cuando tiene una función f para sumar una estructura de datos, entonces sum . map f es la forma de sumar una lista de esas estructuras de datos.

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

Answer 2

En primer lugar, está Template Haskell (aunque la extensión GHC). O usted podría utilizar un data que apoya la lista de profundidad arbitraria anidación así:

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]] 

que imprimirá 19 aquí. Sin embargo, esto no garantiza que todas las hojas tengan la misma profundidad de anidamiento y no sé cómo construir esto a partir de las listas.

Answer 3

Quizás esto? Asume asociatividad, pero agregar nueva capa es simple

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

Answer 4

¿Qué tal tipo de clases?

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

Parece más natural para mí para definir de sum en cuanto a la dimensión anterior sum una dimensión adicional.

-- 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 

Esto es básicamente la misma idea que lo que dijo Sjoerd. Si desea utilizar solamente map y sumy no Refactor subexpresiones comunes en nombres útiles ... a continuación, utilizar el razonamiento ecuacional para reemplazar las funciones personalizadas sum2, sum3, etc.