为什么我的函数在不同时间输出其结果的不同部分？

Question

目前我有一个函数需要很长时间才能完成运行，我们称它为 somefunction。 somefunction returns 一个元组，为简单起见，假设它是 (String,Int)。我想以一种简洁的方式输出这个函数的结果，所以我写了下面的代码（不完全是这段代码，但为了简单起见，我们会说它是）：

main :: IO ()
main = do
 putStr$ (\ (a,b) -> a ++ "\ninteger: " ++ (show b) ++ "\n" ) (somefunction args)

所以我开始了我的代码。过了一会儿，它打印了元组的 a 部分，没有 b。又过了很长一段时间后，它输出 b 部分。

为什么在输出元组的第二部分之前有这么大的延迟？这里发生了什么？

在我的例子中，somefunction 是以下代码中的函数 debugbrainflak：

module Interpreter (debugbrainflak) where

pop :: (Integral a) => [a] -> a
pop [] = 0
pop (x:_) = x

rest :: (Integral a) => [a] -> [a]
rest [] = []
rest (_:x) = x

topadd :: [Integer] -> Integer -> [Integer]
topadd [] x = [x]
topadd (a:[]) x = [a+x]
topadd (a:b) x = (a+x):b

ir :: [Char] -> Integer -> [Char]
ir x 0 = ""
ir ('{':x) y = "{" ++ (ir x (y+1))
ir ('}':x) y = "}" ++ (ir x (y-1))
ir (a:x)   y = [a] ++ (ir x   y  )

interior :: [Char] -> [Char]
interior x = init (ir x 1)

ex :: [Char] -> Integer -> [Char]
ex x 0 = x
ex ('{':x) y = ex x (y+1)
ex ('}':x) y = ex x (y-1)
ex  (a:x)  y = ex x y

exterior :: [Char] -> [Char]
exterior x = ex x 1

---

dbf :: [Char] -> ([Integer],[Integer],[Integer],Int) -> ([Integer],[Integer],[Integer],Int)
dbf []          (x,y,z,c)= (x,y,z,c)
dbf ('(':')':a) (x,y,z,c)= dbf a (x,y,((pop z+1):rest z),c+1)
dbf ('<':'>':a) (x,y,z,c)= dbf a (y,x,z,c+1)
dbf ('{':'}':a) (x,y,z,c)= dbf a ((rest x),y,(topadd z (pop x)),c+1)
dbf ('[':']':a) (x,y,z,c)= dbf a (x,y,(topadd z (toInteger (length x))),c+1)
dbf ('(':a)     (x,y,z,c)= dbf a (x,y,(0:z),c+1)
dbf ('<':a)     (x,y,z,c)= dbf a (x,y,(0:z),c+1)
dbf ('[':a)     (x,y,z,c)= dbf a (x,y,(0:z),c+1)
dbf (')':a) (x,y,(h:z),c)= dbf a ((h:x),y,(topadd z h),c+1)
dbf (']':a) (x,y,(h:z),c)= dbf a (x,y,(topadd z (-h)),c+1)
dbf ('>':a) (x,y,(_:z),c)= dbf a (x,y,z,c+1)
dbf ('{':a)      t     = dbf (exterior a) (drun (interior a) t)
dbf (_:a)        t     = dbf a t

drun :: [Char] -> ([Integer],[Integer],[Integer],Int) -> ([Integer],[Integer],[Integer],Int)
drun s ([],y,z,c)  = ([],y,z,c)
drun s (0:x,y,z,c) = (0:x,y,z,c)
drun s x         = drun s (dbf s x)

--

bl :: [Char] -> [Char] -> Bool
bl [] [] = True
bl [] _  = False
bl ('(':x) y   = bl x (')':y) 
bl ('[':x) y   = bl x (']':y) 
bl ('<':x) y   = bl x ('>':y) 
bl ('{':x) y   = bl x ('}':y) 
bl  (a:x) []
 | elem a ")]>}" = False
 | otherwise     = bl x []
bl (a:x) (b:y)
 | elem a ")]>}" = (a == b) && (bl x y)
 | otherwise     = bl x (b:y)

balanced :: [Char] -> Bool
balanced x = bl x []

clean :: [Char] -> [Char]
clean [] = []
clean ('#':'{':xs) = clean (exterior xs)
clean (x:xs)
 | elem x "()[]<>{}" = x:(clean xs)
 | otherwise         = clean xs

debugbrainflak :: [Char] -> [Integer] -> ([Integer], Int)
debugbrainflak s x
 | balanced s = (\(a,_,_,d) -> (a,d)) (dbf (clean s) (x,[],[],0))
 | otherwise  = error "Unbalanced braces."

如果您想要一个模拟您可以尝试的行为的测试用例（您可以通过增加或减少数字来更改所需的时间）：

debugbrainflak "({({}[()])}{})" [999999]

Answer 1

如果没有看到 somefunction，很难确切地说出发生了什么，但总的来说，GHC¹ 不会像那样重复工作。然而，由于 Haskell 是惰性的，一旦它完成足够的工作来生成字符串的开头，它就会打印出字符串的部分。所以如果你有

slow1 :: Args -> String
slow2 :: Args -> Int

somefunction :: Args -> (String, Int)
somefunction args = (slow1 args, slow2 args)

然后 GHC 将开始强制 slow1 args，打印出来，打印出 "\ninteger: "，然后然后强制 slow2 args，show 并打印出来。（然后打印尾随 "\n"。）

您可以按如下方式进行测试：

main :: IO ()
main =
  let (a,b) = somefunction args
  in putStr $ a `seq` b `seq` (a ++ "\ninteger: " ++ show b ++ "\n")

这里，x `seq` y等于y，但是强制y会强制同时x和y 在评估为 y 之前。这意味着 a `seq` b `seq` ... 将确保在返回包含它们的字符串之前完全计算 a 和 b。

这段代码使用 seq 应该一次打印出所有的东西——但它可能会像你的旧代码一样等待，只是在前面而不是在打印 a 之间和 show b.

¹ Haskell 报告没有具体说明有关评估的那种细节，因此我将在这个答案中特别讨论 GHC 的作用——这通常是人们正在寻找的。

Answer 2

不是直接的答案，而是更多关于这里发生的事情：看起来你在 dbf 中的 c 参数没有被强制，这意味着它正在建立一个大的thunk like 1+(1+(1+(1+(1+(1+(... 并且只有在显示它时才真正进行加法，如果它很大，这会花费时间。这样做的方法是确保 c 在 dbf.

的每个递归步骤中得到评估

按照你写的方式，这可能有点尴尬。一种方法是添加作为 dbf 的第一个方程：

dbf _ (_,_,_,c) | c `seq` False = undefined

这感觉有点像 hack，但允许您在不更改解释器的每一行的情况下进行试验。

在长运行中，我可能会为状态定义一个数据类型而不是元组，并将其设为 strict field:

data InterpState = InterpState {
    stack1 :: [Integer],
    stack2 :: [Integer],
    stack3 :: [Integer],
    instrCount :: !Int
  }

为什么我的函数在不同时间输出其结果的不同部分？

Why is my function outputting different parts of its result at different times?

lambda

haskell

ghc