由于 "fold" 不够强大，无法编写带缩进的树形漂亮打印机，那么高阶组合器是什么？

Question

例如，给定以下树数据类型：

data Tree a = Node [Tree a] | Leaf a deriving Show
type Sexp = Tree String

如何使用高阶组合子表达 "pretty" 函数，以正确的缩进打印树？例如：

sexp = 
    Node [
        Leaf "aaa", 
        Leaf "bbb",
        Node [
            Leaf "ccc",
            Leaf "ddd",
            Node [
                Leaf "eee",
                Leaf "fff"],
            Leaf "ggg",
            Leaf "hhh"],
        Leaf "jjj",
        Leaf "kkk"]
pretty = ????
main = print $ pretty sexp

我希望该程序的结果是：

(aaa 
   bbb 
   (ccc 
       ddd 
       (eee 
           fff) 
       ggg 
       hhh) 
   jjj 
   kkk)

这是一个不完整的解决方案，使用 "fold" 作为组合子，没有实现缩进：

fold f g (Node children) = f (map (fold f g) children)
fold f g (Leaf terminal) = g terminal
pretty = fold (\ x -> "(" ++ (foldr1 ((++) . (++ " ")) x) ++ ")") show
main = putStrLn $ pretty sexp

用fold显然不可能写出我想要的函数，因为它忘记了树结构。那么，什么是合适的高阶组合器，它足够通用，可以让我编写我想要的函数，但不如编写直接递归函数那么强大？

Answer 1

fold够强；诀窍是我们需要将 r 实例化为当前缩进级别的 reader monad。

fold :: ([r] -> r) -> (a -> r) -> (Tree a -> r)
fold node leaf (Node children) = node (map (fold node leaf) children)
fold node leaf (Leaf terminal) = leaf terminal

pretty :: forall a . Show a => Tree a -> String
pretty tree = fold node leaf tree 0 where

  node :: [Int -> String] -> Int -> String
  node children level = 
    let childLines = map ($ level + 1) children
    in unlines ([indent level "Node ["] ++ childLines ++ [indent level "]"])

  leaf :: a -> Int -> String
  leaf a level = indent level (show a)

  indent :: Int -> String -> String -- two space indentation
  indent n s = replicate (2 * n) ' ' ++ s

请注意，我向 fold 的调用传递了一个额外的参数。这是缩进的初始状态，它之所以有效，是因为有了 r、fold returns 函数的这种特化。

Answer 2

简直了

onLast f xs = init xs ++ [f (last xs)]

pretty :: Sexp -> String
pretty = unlines . fold (node . concat) (:[]) where
    node  []    = [""]
    node (x:xs) = ('(' : x) : map ("  " ++) (onLast (++ ")") xs)

由于 "fold" 不够强大，无法编写带缩进的树形漂亮打印机，那么高阶组合器是什么？

Since "fold" isn't powerful enough to write a tree pretty-printer with indentation, what high-order combinator is?

recursion

haskell

combinators

fold