你如何实现 "show" 尾递归？

Question

Haskell的show通常递归实现为：

data Tree = Node Tree Tree | Leaf

show' (Node left right) = "(Node " ++ show' left ++ " " ++ show' right ++ ")"
show' Leaf              = "Leaf"

main = putStrLn $ show' (Node (Node Leaf Leaf) Leaf)

如何使用尾递归实现 show？

Answer 1

您可以通过 Continuation passing style 将此尾递归。查看 wiki 页面上的示例。

Answer 2

使用 CPS，如 M. Shaw 所述。

show' :: Tree -> String
show' = \tree -> go tree id
    where
    go (Node left right) c = 
      go left (\l -> go right (\r -> c ("(Node " ++ l ++ " " ++ r ++ ")")))
    go Leaf c = c "Leaf"

重要的是要记住 Haskell 的惰性在许多情况下避免了尾递归的需要。在这种情况下，尾递归版本必须遍历整个树才能返回输入的任何部分。尝试在每个版本中显示一棵无限树。在惰性语言中返回诸如 String 之类的惰性结构时，最好是核心递归（您的原始实现是）而不是尾递归。

此函数的大部分时间将被左嵌套 (++) 调用占用，即其左参数中的 O(n)。解决方案是使用 difference list，它本身就是延续传递样式的一种形式。

另请参阅 Continuation-Based Program Transformation Strategies，其中讨论了如何通过转换为 CPS 来获得高效算法，然后将延续的结构转换为更具体的内容以得出尾递归解决方案。

你如何实现 "show" 尾递归？

How do you implement "show" tail-recursively?

haskell

tail-recursion