由于“折叠”没有足够强大的功能来编写一个带有缩进功能的树型漂亮打印机，什么是高阶组合器？ [英] Since "fold" isn't powerful enough to write a tree pretty-printer with indentation, what high-order combinator is?

问题描述

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

 数据树a =节点[Tree a] |叶衍生显示
类型Sexp =树字符串
  

我如何表达一个漂亮函数使用高阶组合器，用适当的缩进打印树？例如：

  sexp = 
节点[
 Leafaaa，
 Leaf bbb，
节点[
 Leafccc，
 Leafddd，
节点[
 Leafeee，
 Leaffff ]，
 Leafggg，
 Leafhhh]，
 Leafjjj，
 Leafkkk] 
 pretty = ???? 
 main = print $ pretty sexp 
  

我希望程序的结果是：

 （aaa 
 bbb 
（ccc 
 ddd 
（eee 
 fff）
 ggg 
 hhh）
 jjj 
 kkk）
  

这是一个不完整的解决方案，使用fold作为combinator，它不会实现缩进：

  fold fg（Node children）= f（map（fold fg）children）
 fold fg（Leaf terminal）= g terminal 
 pretty = fold（\ x  - >（++（ foldr1（（++）。（++））x）++））show 
 main = putStrLn $ pretty sexp 
  

显然不可能用 fold 来编写我想要的函数，因为它忘记了树结构。那么，什么是一个适当的高阶combinator是足够通用的，可以让我编写我想要的函数，但是比编写直接递归函数的功能还要强大？

解决方案

fold 足够强大;诀窍是我们需要实例化 r 作为当前缩进级别的读者monad。

  fold ::（[r]  - > r） - > （a→r）→> （树a  - > r）
折叠节点叶子（节点子节点）=节点（映射（折叠节点叶子）子节点）
折叠节点叶子（叶子终端）=叶子终端
 
 pretty :: forall a。显示a =>树a  - > String 
 pretty tree = fold节点叶子树0其中
 
 node :: [Int  - >字符串]  - > Int  - >字符串
节点子级= 
 let childLines = map（$ level + 1）children 
 in unlines（[indent levelNode [] ++ childLines ++ [indent level] ]）
 
 leaf :: a  - > Int  - >字符串
叶级别=缩进级别（显示a）
 
 indent :: Int  - >字符串 - > String  - 两个空格缩进
 indent ns = replicate（2 * n）''++ s 
  

请注意，我将一个额外参数传递给 fold 的调用。这是缩进的初始状态，它的工作原理是因为通过这种特殊化 r ， fold 返回一个函数。 p>

Given, for example, the following tree data type:

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

How do I express a "pretty" function using an high-order combinator, that prints the tree with proper indentation? For example:

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

I want the result of that program to be:

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

Here is an incomplete solution, using a "fold" as the combinator, that doesn't implement the indentation:

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

It is obviously not possible to write the function I want using fold, since it forgets the tree structure. So, what is a proper high-order combinator that is generic enough to allow me to write the function I want, but less powerful than writing a direct recursive function?

解决方案

fold is strong enough; the trick is that we'll need to instantiate r as a reader monad of the current indentation level.

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

Take careful note that I pass an extra parameter to the call to fold. This is the initial state of indentation and it works because with this specialization of r, fold returns a function.

这篇关于由于“折叠”没有足够强大的功能来编写一个带有缩进功能的树型漂亮打印机，什么是高阶组合器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！