Fast sums of power algorithm This code reaches time limit on 1 test case, solving this challenge. The approach that I'm using is from the book Algorithms Functional Programming Approach, which is a backtracking depth searching method. How do I improve speed of this code? Or is there better way to do it?

searchDfs :: (Eq node) =&gt;
             (node -&gt; [node]) -&gt; -- generates successor nodes
             (node -&gt; Bool) -&gt; -- is goal
             node -&gt; -- first node
             [node]
searchDfs succ goal x = search' ([x])
  where
    search' s
      | null s = []
      | goal (head s) = head s : search' (tail s)
      | otherwise = let x = head s
                    in search' (succ x ++ tail s)

type Degree = Int
type CurrentSum = Int
type CurrentNumber = Int
type Node = (CurrentSum,CurrentNumber,Degree,Goal)
type Goal = Int

succN :: Node -&gt; [Node]
succN (sum,i,d, goal)  = [( sum+i'^d, i', d, goal) | i' &lt;- [(i+1)..goal], sum+i'^d &lt;= goal ]

goal :: Node -&gt; Bool
goal (sum,_,_,m) = sum == m


countSols :: Degree -&gt; Goal -&gt; Int
countSols d m = foldr (+) 0 $ map (\(sum,i) -&gt; length (searchDfs succN goal (sum,i,d,m))) startingNumbers
  where startingNumbers = [ (i^d,i) | i &lt;- [1..m], i^d &lt;= m]

main = do
  m &lt;- readLn
  d &lt;- readLn
  let c = countSols d m
  print c
The search' could could be written more idiomatically (but not necessarily faster) as

search' [] = []
search' (x:xs) | goal x    = x : search' xs
               | otherwise = search' (succ x ++ xs)

The Eq constraint on searchDfs seems to be unused.
In succN, you are calculating sum+i'^d twice (unless the compiler optimizes that away, but it’s better not to rely on that). Also, it will calculate it for all values of i' until goal, although you probably want to abort early. Maybe using takeWhile would be better:

 succN (sum,i,d, goal) =
     takeWhile (\(s,_,_,_) -&gt; s &lt;= goal)
               [( sum+i'^d, i', d, goal) | i' &lt;- [(i+1)..goal]]

It looks as if the d and goal field of your Nodes is always the same. Then you shouldn’t have it as part of the Node, but rather pass it around explicitly. You can do that without modifying searchDfs!