创建循环的好方法

Question

Haskell没有像许多其他语言一样的循环.我理解它背后的原因以及用于解决没有它们的问题的一些不同方法.但是,当需要循环结构时,我不确定我创建循环的方式是否正确/良好.

例如(平凡的功能):

dumdum = do
         putStrLn "Enter something"
         num <- getLine
         putStrLn $ "You entered: " ++ num
         dumdum

这工作正常,但代码中是否存在潜在问题？

一个不同的例子:

a = do 
    putStrLn "1"
    putStrLn "2"
    a

如果用像Python这样的命令式语言实现,它看起来像:

def a():
     print ("1")
     print ("2")
     a()

这最终导致最大递归深度误差.在Haskell中似乎并非如此,但我不确定它是否会导致潜在的问题.

我知道还有其他选项来创建循环,例如Control.Monad.LoopWhile和Control.Monad.forever- 我应该使用它们吗？(我仍然是Haskell的新手,还不了解monad.)

Answer 1

对于一般迭代,具有递归函数调用本身绝对是可行的方法.如果您的调用处于尾部位置,则它们不会使用任何额外的堆栈空间,并且行为更像是goto¹.例如,这是一个使用常量堆栈空间²对前n个整数求和的函数:

sum :: Int -> Int
sum n = sum' 0 n

sum' !s 0 = s
sum' !s n = sum' (s+n) (n-1)

它大致相当于以下伪代码:

function sum(N)

    var s, n = 0, N
    loop: 
       if n == 0 then
           return s
       else
           s,n = (s+n, n-1)
           goto loop

注意在Haskell版本中我们如何使用sum累加器的函数参数而不是可变变量.这是尾递归代码的常见模式.

到目前为止,尾调用优化的一般递归应该给你所有的循环功能.唯一的问题是手动递归(有点像getos,但有点好)是相对非结构化的,我们经常需要仔细阅读使用它来查看正在发生的事情的代码.就像命令式语言如何使用循环机制(for,while等)来描述最常见的迭代模式一样,在Haskell中我们可以使用更高阶的函数来完成类似的工作.例如,许多列表处理函数(如³map或foldl'³⁾类似于纯代码中的直接for循环,当处理monadic代码时,可以使用Control.Monad或monad-loops包中的函数.最后,它是一个风格问题,但我会错误地使用更高阶的循环函数.

¹您可能想查看"Lambda the ultimate GOTO",这是一篇关于尾递归如何与传统迭代一样高效的经典文章.另外,由于Haskell是一种惰性语言,在某些情况下,非尾部位置的递归仍然可以在O(1)空间中运行(搜索"Tail recursion modulo cons")

²那些感叹号是为了使累加器参数得到热切评估,因此加法与递归调用同时发生(默认情况下Haskell是惰性的).如果需要,可以省略"!",但是你可能会遇到空间泄漏的风险.

³由于前面提到的空间泄漏问题,请始终使用foldl'而不是foldl.

Answer 2

我知道还有其他选项来创建循环,例如Control.Monad.LoopWhile和Control.Monad.forever- 我应该使用它们吗？(我仍然是Haskell的新手,还不了解monad.)

是的你应该.您会发现在"真正的"Haskell代码中,显式递归(即在函数中调用函数)实际上非常罕见.有时,人们这样做是因为它是最易读的解决方案,但通常使用诸如此类的东西forever要好得多.

事实上,说Haskell没有循环只是半真半假.这是正确的,语言中没有内置循环.但是,在标准库中,有多种循环,而不是在命令式语言中.在像Python这样的语言中,for只要需要迭代某些东西,就可以使用" 循环".在Haskell,你有

• map,fold,any,all,scan,mapAccum,unfold,find,filter(Data.List模块)
• mapM,forM,forever(Control.Monad)
• traverse,for(Data.Traversable)
• foldMap,asum,concatMap(Data.Foldable)

还有很多很多人!

这些循环中的每一个都针对特定用例进行定制(并且有时针对其进行优化).

在编写Haskell代码时,我们大量使用它们,因为它们允许我们更加智能地推理我们的代码和数据.当你看到有人for在Python中使用循环时,你必须阅读并理解循环以了解它的作用.当你看到有人map在Haskell中使用一个循环时,你知道它没有阅读它的作用,它不会在列表中添加任何元素 - 因为我们有"Functor法则",这些规则说明任何map函数必须以这种或那种方式工作!

回到你的例子,我们可以先定义一个askNum"函数"(它在技术上不是一个函数,而是一个IO值...我们可以假装它暂时是一个函数),它要求用户只输入一次,并显示它回到他们身边.当你希望你的程序永远不断询问时,你只需将这个"函数"作为forever循环的参数,forever循环就会永远地问!

整个事情可能看起来像:

askNum = do
         putStrLn "Enter something"
         num <- getLine
         putStrLn "You entered: " ++ num

dumdum = forever askNum

然后,一个更有经验的程序员可能会摆脱askNum这种情况下的"功能",并把整个事情变成

dumdum = forever $ do
           putStrLn "Enter something"
           num <- getLine
           putStrLn "You entered: " ++ num