| Copyright | Copyright (C) 2021 Yoo Chung |
|---|---|
| License | GPL-3.0-or-later |
| Maintainer | dev@chungyc.org |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
Problems.P73
Description
Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P73.
Synopsis
- treeToSexp :: MultiwayTree Char -> String
- sexpToTree :: String -> Maybe (MultiwayTree Char)
Documentation
treeToSexp :: MultiwayTree Char -> String Source #
An s-expression is
commonly represented as a list of items between parentheses.
In particular, s-expressions can be nested, e.g., (a b (c d) e (f g)).
It is used by programming languages such as Lisp
and Scheme.
A possible way to represent a multiway tree with an s-expression is for the first element in a list to represent the root of the tree, and the rest of the elements in the list would be its children. As a special case, a multiway tree with no children is represented without parentheses.
Write a function which will return this s-expression representation of a multiway tree as a string.
Examples
>>>treeToSexp multitree1"a"
>>>treeToSexp multitree2"(a b)"
>>>treeToSexp multitree3"(a (b c))"
>>>treeToSexp multitree4"(b d e)"
>>>treeToSexp multitree5"(a (f g) c (b d e))"
Notes
This has been substantially rewritten from problem 73 in the original list, although it is still really the same problem. It made it sound like the representation outlined would be a natural one in Lisp, but it is hard to find multiway trees represented in this exact way with Lisp. All references I have found claiming this is a common representation are derived from the problem in the original list of 99 Prolog Problems.
I have tried to avoid giving an impression that this is the standard representation of trees in Lisp.
sexpToTree :: String -> Maybe (MultiwayTree Char) Source #
Write a function which will convert an s-expression, representing
a multiway tree as in treeToSexp, into a MultiwayTree.
Examples
>>>sexpToTree "(a (f g) c (b d e))" == Just multitree5True