EDIT: while I m still interested in an answer on the problems the execution faces in this case, it appears that it was indeed related to strictness since a -O fixes the execution and the program can handle the tree really quickly.
https://projecteuler.net/ https://projecteuler.net/
I already solved it using simple lists and dynamic programming.
I d like to solve it now using a tree datastructure (well, where a Node can have two parents so it s not really a tree). I thought I d use a simple tree but would take care to craft it so that Nodes are shared when appropriate:
data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving (Show, Eq)
Solving the problem is then just a matter of going through the tree recursively:
calculate :: (Ord a, Num a) => Tree a => a calculate (Node v l r) = v + (max (calculate l) (calculate r)) calculate (Leaf v) = v
Obviously this has exponential time complexity though. So I tried to memoize the results with :
calculate :: (Ord a, Num a) => Tree a => a calculate = memo go where go (Node v l r) = v + (max (calculate l) (calculate r)) go (Leaf v) = v
http://hackage.haskell.org/package/stable-memo-0.2.2/docs/Data-StableMemo.html#v:memo http://hackage.haskell.org/package/stable-memo-0.2.2/docs/Data-StableMemo.html#v:memo
http://felsin9.de/nnis/ghc-vis/ http://felsin9.de/nnis/ghc-vis/
On the sample tree produced by my function as such: lists2tree [[1], [2, 3], [4, 5, 6]], it returns the following correct sharing:
http://public.crydee.eu/sample.png http://public.crydee.eu/sample.png
Here we can see that the node 5 is shared.
Yet it seems that my tree in the actual Euler Problem isn t getting memoized correctly. https://github.com/m09/project-euler/blob/master/61-70/67.lhs https://github.com/m09/project-euler/blob/master/61-70/67.lhs
lists2tree :: [[a]] -> Tree a lists2tree = head . l2t l2t :: [[a]] -> [Tree a] l2t (xs:ys:zss) = l2n xs ts t where (t:ts) = l2t (ys:zss) l2t (x:[]) = l2l x l2t [] = undefined l2n :: [a] -> [Tree a] -> Tree a -> [Tree a] l2n (x:xs) (y:ys) p = Node x p y:l2n xs ys y l2n [] [] _ = [] l2n _ _ _ = undefined l2l :: [a] -> [Tree a] l2l = map (l -> Leaf l)
It basically goes through the list of lists two rows at a time and then creates nodes from bottom to top recursively.
What is wrong with this approach? I thought it might that the program will still produce a complete tree parse in thunks before getting to the leaves and hence before memoizing, avoiding all the benefits of memoization but I m not sure it s the case. If it is, is there a way to fix it?