Skoro "fałdowanie" nie jest wystarczająco mocne, aby napisać ładną drukarkę do drzewa z wcięciem, czym jest kombinator wyższego rzędu?

Question

Biorąc pod uwagę, na przykład, następujące dane rodzaj drzewa:

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

Jak mogę wyrazić funkcję „Pretty” Używanie COMBINATOR wyższego rzędu, która drukuje drzewo z prawidłowego wcięcia? Na przykład:

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 

Chcę wynikiem tego programu będzie:

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

Oto niepełna rozwiązanie, za pomocą „spasować” jako Combinator, że nie realizuje wcięcia:

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 

to oczywiście nie jest możliwe, aby napisać funkcję chcę, używając fold, ponieważ zapomina strukturę drzewa. Więc, co jest właściwym kombinatorem wyższego rzędu, który jest na tyle ogólny, że pozwala mi pisać funkcję, której chcę, ale mniejszą niż pisanie bezpośredniej funkcji rekursywnej?

Answer 1

fold jest wystarczająco silny; Sztuką jest to, że musimy utworzyć instancję r jako monadę czytelnika na bieżącym poziomie wcięcia.

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 

Zwróćmy uwagę, że mijam dodatkowy parametr do wywołania fold. Jest to początkowy stan wcięcia i działa, ponieważ przy tej specjalizacji r, fold zwraca funkcję.

Answer 2

To po prostu

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)