你如何以递归方式实现"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

使用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以惰性语言返回惰性结构时,最好是corecursive(你的原始实现)而不是tail递归.

这个函数的大部分时间都会被左嵌套(++)调用吃掉,这是O(n)左边的参数.解决方案是使用差异列表,这是一种延续传递方式本身.

另请参阅基于延续的程序转换策略,其中讨论了如何通过转换为CPS来获得有效的算法,然后将延续的结构转换为更具体的结果,以获得尾递归解决方案.