Haskell 程序内存不足(无限递归？循环？什么？)

Question

编辑:更新为包含完整代码。

我是 Haskell 的新手，我编写的一个程序有问题，该程序用于为类(class)作业做一些熵计算(作业就是计算，Haskell 的使用是一种选择，所以我'我不是要别人帮我做作业，用 Python 做这件事会花费我微不足道的时间和精力)。代码采用一维数组:

--- first input (length 2): 
---     0,0   0,1   1,0   1,1
---    [.48,  .02,  .02,  .48]
--- or:
---     0    1   
---    .48  .02  0
---               
---    .02  .48  1

然后我定义了几个通用函数:

log2 :: Float -> Float
log2 x =
  logBase 2 x

entropy :: [Float] -> Float
entropy probArray =
  sum(map (\i -> (i * (log2 (1/i)))) probArray)

以及每个特定计算的函数:

-- calculate joint entropy
jointEntropy :: [Float] -> Float
jointEntropy probArray =
  entropy probArray

-- calculate entropy of X
splitByCol :: Int -> [Float] -> [[Float]]
splitByCol length probArray =
  [(take length probArray)] ++ (splitByCol length (drop length probArray))

xEntropy :: Int -> [Float] -> Float
xEntropy length probArray =
  entropy (map sum (splitByCol length probArray))

-- calculate entropy of Y
ithElements :: Int -> Int -> [Float] -> [Float]
ithElements level length matrixArray =
  let indexArray = zip [0..(length^2 - 1)] matrixArray
  in [snd x | x <- indexArray, fst x `mod` length == level]

splitByRow :: Int -> Int -> [[Float]] -> [[Float]]
splitByRow level length lists =
  if level == length
  then
    tail lists -- return list sans full matrix array which was being carried at the front
  else
    splitByRow (level+1) length (lists ++ [(ithElements level length (lists !! 0))]) 

yEntropy :: Int -> [Float] -> Float
yEntropy length probArray =
  entropy (map sum (splitByRow 0 length [probArray]))

--calculate mutual information
mutualInfo :: Float -> Float -> Float
mutualInfo xEnt yEnt =
  xEnt - yEnt

-- calculate conditional of X given Y - (X|Y)
xCond :: Float -> Float -> Float
xCond xEnt mInfo =
  xEnt - mInfo

-- calculate conditional of Y given X - (Y|X)
yCond :: Float -> Float -> Float
yCond yEnt mInfo =
  yEnt - mInfo

然后将这些链接在一起以返回一个数组，其中包含我想要执行的每个计算:

-- caller functions -> resArray ends up looking like [H(X,Y), H(X), H(Y), I(X;Y), H(X|Y), H(Y|X)]
calcJointEnt :: [Float] -> [Float]
calcJointEnt probArray =
  calcVarEnt probArray [(jointEntropy probArray)]

calcVarEnt :: [Float] -> [Float] -> [Float]
calcVarEnt probArray resArray =
  let len = floor (sqrt (fromIntegral (length probArray)))
  in calcMutual probArray (resArray ++ [(xEntropy len probArray), (yEntropy len probArray)])

calcMutual :: [Float] -> [Float] -> [Float]
calcMutual probArray resArray =
  calcCond probArray (resArray ++ [(mutualInfo (resArray !! 1) (resArray !! 2))])

calcCond :: [Float] -> [Float] -> [Float]
calcCond probArray resArray =
  resArray ++ [(xCond (resArray !! 1) (resArray !! 3)), (yCond (resArray !! 2) (resArray !! 3))]

等等...然后我有一些函数来格式化打印字符串，还有一个主要函数将它们放在一起:

-- prepare printout
statString :: (String, String) -> String
statString t =  
  (fst t) ++ ": " ++ (snd t)

printOut :: [Float] -> String
printOut resArray =
  let statArray = zip ["H(X,Y)", "H(X)", "H(Y)", "H(X;Y)", "H(X|Y)", "H(Y|X)"] (map show resArray)
  in "results:\n\t" ++ intercalate "\n\t" (map statString statArray) ++ "\n\n---\n"

-- main
main :: IO()
main = 
  let inputs = [[0.48,  0.02,  0.02,  0.48], [0.31,  0.02,  0.00,  0.02,  0.32,  0.02,  0.00,  0.02,  0.29]]
  in putStrLn (intercalate "" (map printOut (map calcJointEnt inputs)))

所以我确信有更好的方法可以做很多这样的事情，但在我看来，从我最少的 haskell 经验和我稍微广泛但仍然有限的函数式风格编程经验来看，它应该可行。

我的问题是，当我编译并运行时，我得到了这个输出:

bash-4.2$ ./noise 
results:
    H(X,Y): 1.2422923
noise: out of memory (requested 1048576 bytes)

在打印出一个结果和内存错误消息之间有很长的时间。当我在 ghci 调试器(这是我第一次使用的)中弹出它时，如果我试图在 printOut 函数中强制执行 resArray，它会执行相同的操作，并且当我尝试在链接功能的最低级别:

calcCond :: [Float] -> [Float] -> [Float]
calcCond probArray resArray =
  resArray ++ [(xCond (resArray !! 1) (resArray !! 3)), (yCond (resArray !! 2) (resArray !! 3))]

我得到以下信息:

[noise.hs:101:3-96] *Main> seq _t1 ()
()
[noise.hs:101:3-96] *Main> :print resArray
resArray = (_t2::Float) : (_t3::[Float])
[noise.hs:101:3-96] *Main> seq _t2 ()
()
[noise.hs:101:3-96] *Main> :print resArray
resArray = 1.2422923 : (_t4::[Float])
[noise.hs:101:3-96] *Main> seq _t3 ()
()
[noise.hs:101:3-96] *Main> :print resArray
resArray = 1.2422923 : (_t5::Float) : (_t6::[Float])
[noise.hs:101:3-96] *Main> seq _t5 ()
^C^C^C^C^CInterrupted.
[noise.hs:101:3-96] *Main> 

我研究了 RTS 调试工具，它似乎是推荐的工具，用于在网站上提出类似问题时弹出引擎盖，但当我使用 +RTS -xc 运行它时，没有任何反应。我认为这是因为 RTS 似乎要求它实际抛出异常，而不是操作系统介入？

我认为来自命令式背景的我自己的主要问题是程序可以通过某种无限循环过程到达 IO 语句的概念仍然在逻辑上的某个地方进行是一个陌生的概念。当然，我可能完全错误地认为那是正在发生的事情，但在我看来就是这样。非常感谢你们能提供的任何帮助(不仅是在这段代码上，而且还有我对 Haskell 的一般方法)。

Answer 1

由于 H(X) 从未被打印出来，所以查看它的计算位置是有意义的，即 xEntropy。 xEntropy 调用 splitByCol 有一个明显的错误。它返回一个无限列表!这意味着 entropy 永远不会终止，因为它试图在无限列表上调用 sum。