同样的东西冻结或立即工作

Question

下面的代码解决了这个问题 challenge:

Find the number of ways in which a given integer, X, can be expressed as the sum of the the Nth power of unique natural numbers.

import Control.Monad (guard)
import qualified Data.Map.Strict as Map
import Data.Map ((!),fromList,Map(..),member)

-- depth first search higher order function
depthFirstSearch :: (node -> [node]) -> -- successor node generator
                   (node -> Bool) -> -- is goal checker
                   [node] -> -- starting root nodes
                   [node] -- goal nodes
depthFirstSearch succ goal roots = search' roots
  where search' [] = []
        search' (x:xs) | goal x = x : search' xs
                       | otherwise = search' (succ x ++ xs)


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

-- generates valid successor nodes
succN :: Goal -> Map Int Int -> Node -> [Node]
succN goal _map (i,sum) = do
  i' <- [(i+1)..goal]
  guard (member i' _map)
  let sum' = sum + _map!i'
  guard (sum' <= goal)
  return (i',sum')
-- checks if the node is the goal
goalN :: Goal -> Node -> Bool
goalN goal (_,sum) = goal == sum

-- counts solutions
solCount :: Degree -> Goal -> Int
solCount d goal =
  let roots = [(i,i^d) | i <- [1..goal], i^d <= goal]
      _map = Map.fromList roots
      nodes = depthFirstSearch (succN goal _map) (goalN goal) roots
      c = length nodes
  in c

奇怪的事情发生了。它冻结在 solCount 10 1000。如果我运行在 ghci 中手动 solCount 它会按预期冻结

let roots = [(i,i^10) | i <- [1..1000], i^10 <= 1000] -- [(1,1)]
let _map = Map.fromList roots 
let nodes = depthFirstSearch (succN 1000 _map) (goalN 1000) roots
nodes

但是当它被替换成"same"这样的东西时

let nodes = depthFirstSearch (succN 1000 $ Map.fromList [(1,1)]) (goalN 1000) [(1,1)]
nodes

它会立即打印结果。不知道为什么会冻不冻

Answer 1

假设：

let roots = [(i,i^10) | i <- [1..1000], i^10 <= 1000] -- [(1,1)]

for Ints 由于溢出而不正确。您可以通过使用整数执行比较并转换来解决此问题：

let roots = [(b,b^10) | a <- [(1::Integer)..1000], a^1000 <= 1000, let b = fromInteger a ]

您可能没有发现这个问题，因为 ghci 在 REPL 中默认为整数，但在您的代码中 roots 的类型为 [Int].

同样的东西冻结或立即工作

Same thing freezes or works in an instant

haskell