CODEWITHSUNDEEP
haskell
Magnus Kronqvist
Magnus Kronqvist

Reputation: 1589

Cubesumming in haskell

Haskell has the sum function

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

Which can be nicely composed to sum a matrix by

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

Going deeper, however, such as summing a cube, creates the restriction Num [a]

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

Which, if you think about it, is natural. So with the former attempt to define the sumcube function blowing up in one's face, we need to find a different path. One such attempt would be:

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

Which seems nowhere as natural as the summatrix function.

In my quest to posessing the mental tools for problem solving in Haskell, I am interested in knowing how to tackle this problem of summing a structure of any depth by, say, stacking map sums as in my third code example. Is this at all possible? And in that case, how would you do it?

Upvotes: 8

Views: 466

Answers (5)

Dan Burton
Dan Burton

Reputation: 53665

It seems most natural to me to define an additional dimension's sum in terms of the previous dimension's sum.

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

This is basically the same idea as what Sjoerd said. If you want to only use map and sum and not refactor common subexpressions into useful names...then use equational reasoning to replace the custom functions sum2, sum3, etc.

Upvotes: 1

Landei
Landei

Reputation: 54574

How about typeclasses?

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

Upvotes: 14

sdcvvc
sdcvvc

Reputation: 25644

Maybe this? Assumes associativity, but adding new layer is simple

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

Upvotes: 5

Sjoerd Visscher
Sjoerd Visscher

Reputation: 12000

You'll have to work from the inside out. When you have a function f for summing a data structure, then sum . map f is the way to sum a list of those data structures.

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

Upvotes: 12

amoebe
amoebe

Reputation: 4982

First, there's Template Haskell (GHC extension though). Or you could use a data which supports arbitrary deep list nesting like that:

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

Which will print 19 here. However this does not ensure that all leaves have the same nesting depth and i don't know how to build this from lists.

Upvotes: 0

Related Questions