[Haskell-cafe] List-to-outline

[Chris Kuklewicz]

process [] = []
process (a:t) = let (kids,sibs) = span (>a) (t)
                in (Nd a (process kids)):process sibs

Ok, modules loaded: Main.
*Main> process  [0,1,2,2,3,3,3,2,1,2,3,3,1]
[0{1{2 2{3 3 3} 2} 1{2{3 3}} 1}]
*Main>


Steve Schafer wrote:
> I have some lists of integers; e.g.,
> 
>   [0,1,2,2,3,3,3,2,1,2,3,3,1]
> 
> Think of each integer value as representing the indentation level in a
> hierarchical outline: e.g.,
> 
>   0
>     1
>       2
>       2
>         3
>         3
>         3
>       2
>     1
>       2
>         3
>         3
>     1
> 
> I want to convert the list into a structure that better represents the
> hierarchy. So, I first define a datatype to represent each node of the
> new structure:
> 
>   data Node = Nd Int [Node]
> 
> That is, a node consists of an Int representing the value of the node,
> followed by a list of its immediate child nodes. (In principle, I can
> deduce the value of a node simply from the nesting level, of course, but
> in the real problem I'm trying to solve, each node contains other
> information that I need to preserve as well.)
> 
> Next, I define some functions to perform the transformation
> 
>   isChild :: Int -> Node -> Bool
>   isChild i (Nd j _) = (j > i)
>   isChild _ _ = False
> 
>   prepend :: Int -> [Node] -> [Node]
>   prepend i [] = [Nd i []]
>   prepend i ns = (Nd i f):s
>     where (f,s) = span (isChild i) ns
> 
>   unflatten :: [Int] -> [Node]
>   unflatten ns = foldr prepend [] ns
> 
> Finally, I add some code to display the result in an aesthetically
> pleasing way:
> 
>   showsNodeTail :: [Node] -> String -> String
>   showsNodeTail []     = showChar '}'
>   showsNodeTail (n:ns) = showChar ' '.shows n.showsNodeTail ns
> 
>   showsNodeList :: [Node] -> String -> String
>   showsNodeList []     = showString ""
>   showsNodeList (n:ns) = showChar '{'.shows n.showsNodeTail ns
> 
>   showsNode :: Node -> String -> String
>   showsNode (Nd i ns) = shows i.showsNodeList ns
> 
>   instance Show Node where
>     showsPrec n = showsNode
> 
> This all works just fine, and when I enter
> 
>   unflatten [0,1,2,2,3,3,3,2,1,2,3,3,1]
> 
> I get
> 
>   [0{1{2 2{3 3 3} 2} 1{2{3 3}} 1}]
> 
> as expected.
> 
> The reason I'm posting this here is that I have a gnawing suspicion that
> the unflatten/prepend/isChild functions, and possibly the Node data type
> as well, are not the most elegant way to go about solving the problem,
> and that I'm missing another more obvious way to do it.
> 
> Any suggestions?
> 
> Thanks,
> 
> Steve Schafer
> Fenestra Technologies Corp.
> http://www.fenestra.com/
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>