Agn*_*yay 10 io recursion haskell tail-recursion
请考虑以下两个变体:
myReadListTailRecursive :: IO [String]
myReadListTailRecursive = go []
where
go :: [String] -> IO [String]
go l = do {
inp <- getLine;
if (inp == "") then
return l;
else go (inp:l);
}
myReadListOrdinary :: IO [String]
myReadListOrdinary = do
inp <- getLine
if inp == "" then
return []
else
do
moreInps <- myReadListOrdinary
return (inp:moreInps)
在普通的编程语言中,人们会知道尾递归变体是更好的选择.
但是,通过这个答案,显然haskell的递归实现与重复使用递归堆栈的实现并不相似.
但是因为在这种情况下,所讨论的程序涉及行动和严格的单子行列,我不确定是否适用相同的推理.事实上,我认为在这种IO情况下,尾递归形式确实更好.我不确定如何正确推理这一点.
编辑:大卫杨指出,这里最外面的电话是(>>=).即使在这种情况下,这些风格中的一种是否优于另一种？
那\xe2\x80\x99s确实不是我会怎么写，但它\xe2\x80\x99s足够清楚你\xe2\x80\x99正在做什么。（顺便说一句，如果您希望能够有效地插入链中任何函数的任意输出，而不使用 monad，您可以尝试使用Data.ByteString.Builder。）
您的第一个实现与左折叠非常相似，第二个实现与右折叠或地图非常相似。（您可以尝试实际这样编写它们！）第二个对于 I/O 有几个优点。对于处理输入和输出来说，最重要的因素之一是它可以是交互式的。
\n\n你\xe2\x80\x99会注意到第一个从外到内构建整个列表：为了确定列表的第一个元素是什么，程序需要计算整个结构以到达最里面的thunk，即return l。程序首先生成整个数据结构，然后开始处理它。当您减少列表时，\xe2\x80\x99 非常有用，因为尾递归函数和严格的左折叠非常有效。
对于第二个，最外层的 thunk 包含列表的头部和尾部，因此您可以抓住尾部，然后调用 thunk 生成第二个列表。这可以处理无限列表，并且可以生成并返回部分结果。
\n\n这里\xe2\x80\x99是一个人为的例子：一个程序每行读入一个整数并打印到目前为止的总和。
\n\nmain :: IO ()\nmain = interact( display . compute 0 . parse . lines )\n where parse :: [String] -> [Int]\n parse [] = []\n parse (x:xs) = (read x):(parse xs)\n\n compute :: Int -> [Int] -> [Int]\n compute _ [] = []\n compute accum (x:xs) = let accum' = accum + x\n in accum':(compute accum' xs)\n\n display = unlines . map show\n如果您以交互方式运行此命令，您\xe2\x80\x99将得到类似以下内容的信息：
\n\n$ 1\n1\n$ 2\n3\n$ 3\n6\n$ 4\n10\n但您也可以compute使用累积参数以尾递归方式编写：
main :: IO ()\nmain = interact( display . compute [] . parse . lines )\n where parse :: [String] -> [Int]\n parse = map read\n\n compute :: [Int] -> [Int] -> [Int]\n compute xs [] = reverse xs\n compute [] (y:ys) = compute [y] ys\n compute (x:xs) (y:ys) = compute (x+y:x:xs) ys\n\n display = unlines . map show\n这是一个人为的例子，但严格的左折叠是一种常见的模式。但是，如果您使用累积参数编写computeor parse，则当您尝试交互式运行并在数字 4 之后点击 EOF（control-D在 Unix 上，在 Windows 上）时，您会得到以下结果：control-Z
$ 1\n$ 2\n$ 3\n$ 4\n1\n3\n6\n10\n这个左折叠版本需要计算整个数据结构，然后才能读取任何数据结构。这可以\xe2\x80\x99t在无限列表上工作（你什么时候会达到基本情况？如果你这样做了，你甚至如何反转无限列表？）和一个可以\xe2\x80\x99t响应用户的应用程序输入直到退出是一个交易破坏者。
\n\n另一方面，尾递归版本可以严格控制其累积参数，并且运行效率更高，特别是当它\xe2\x80\x99s 不立即被消耗时。除了参数之外，它不需要保留任何 thunk 或上下文，甚至可以重复使用相同的堆栈帧。Data.List.foldl'当您\xe2\x80\x99 将列表减少到一个值而不是构建急切评估的输出列表时，严格的累积函数（例如 ）是一个不错的选择。sum、product或等函数any可以\xe2\x80\x99t 返回任何有用的中间值。他们本质上必须先完成计算，然后返回最终结果。