{- |
Description: Tree representation with s-expressions
Copyright: Copyright (C) 2023 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P73" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P73 (treeToSexp,sexpToTree) where

import           Problems.MultiwayTrees

-- | An [s-expression](https://en.wikipedia.org/wiki/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](https://lisp-lang.org/)
-- and [Scheme](https://groups.csail.mit.edu/mac/projects/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.
treeToSexp :: MultiwayTree Char -> String
treeToSexp :: MultiwayTree Char -> String
treeToSexp (MultiwayTree Char
x []) = [Char
x]
treeToSexp (MultiwayTree Char
x [MultiwayTree Char]
ts) = String
"(" String -> String -> String
forall a. [a] -> [a] -> [a]
++ [Char
x] String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
" " String -> String -> String
forall a. [a] -> [a] -> [a]
++ [String] -> String
unwords ((MultiwayTree Char -> String) -> [MultiwayTree Char] -> [String]
forall a b. (a -> b) -> [a] -> [b]
map MultiwayTree Char -> String
treeToSexp [MultiwayTree Char]
ts) String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
")"

-- | Write a function which will convert an s-expression, representing
-- a multiway tree as in 'treeToSexp', into a 'MultiwayTree'.
sexpToTree :: String -> Maybe (MultiwayTree Char)
sexpToTree :: String -> Maybe (MultiwayTree Char)
sexpToTree = Maybe (MultiwayTree Char, String) -> Maybe (MultiwayTree Char)
forall {a}. Maybe (a, String) -> Maybe a
tree (Maybe (MultiwayTree Char, String) -> Maybe (MultiwayTree Char))
-> (String -> Maybe (MultiwayTree Char, String))
-> String
-> Maybe (MultiwayTree Char)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Maybe (MultiwayTree Char, String)
parse
  where tree :: Maybe (a, String) -> Maybe a
tree Maybe (a, String)
Nothing           = Maybe a
forall a. Maybe a
Nothing
        tree (Just (a
t,[]))     = a -> Maybe a
forall a. a -> Maybe a
Just a
t
        tree (Just (a
t,Char
' ':String
xs)) = Maybe (a, String) -> Maybe a
tree (Maybe (a, String) -> Maybe a) -> Maybe (a, String) -> Maybe a
forall a b. (a -> b) -> a -> b
$ (a, String) -> Maybe (a, String)
forall a. a -> Maybe a
Just (a
t,String
xs)
        tree (Just (a
_,String
_))      = Maybe a
forall a. Maybe a
Nothing

parse :: String -> Maybe (MultiwayTree Char, String)
parse :: String -> Maybe (MultiwayTree Char, String)
parse []       = Maybe (MultiwayTree Char, String)
forall a. Maybe a
Nothing
parse (Char
')':String
_)  = Maybe (MultiwayTree Char, String)
forall a. Maybe a
Nothing
parse (Char
' ':String
xs) = String -> Maybe (MultiwayTree Char, String)
parse String
xs
parse (Char
'(':String
xs) = do
  (Char
x,String
xs') <- String -> Maybe (Char, String)
parseNode String
xs
  ([MultiwayTree Char]
ts,String
xs'') <- ([MultiwayTree Char], String)
-> Maybe ([MultiwayTree Char], String)
parseList ([],String
xs')
  (MultiwayTree Char, String) -> Maybe (MultiwayTree Char, String)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Char -> [MultiwayTree Char] -> MultiwayTree Char
forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
x [MultiwayTree Char]
ts, String
xs'')
parse (Char
x:String
xs) = (MultiwayTree Char, String) -> Maybe (MultiwayTree Char, String)
forall a. a -> Maybe a
Just (Char -> [MultiwayTree Char] -> MultiwayTree Char
forall a. a -> [MultiwayTree a] -> MultiwayTree a
MultiwayTree Char
x [],String
xs)

parseNode :: String -> Maybe (Char, String)
parseNode :: String -> Maybe (Char, String)
parseNode []       = Maybe (Char, String)
forall a. Maybe a
Nothing
parseNode (Char
'(':String
_)  = Maybe (Char, String)
forall a. Maybe a
Nothing
parseNode (Char
')':String
_)  = Maybe (Char, String)
forall a. Maybe a
Nothing
parseNode (Char
' ':String
xs) = String -> Maybe (Char, String)
parseNode String
xs
parseNode (Char
x:String
xs)   = (Char, String) -> Maybe (Char, String)
forall a. a -> Maybe a
Just (Char
x, String
xs)

parseList :: ([MultiwayTree Char], String) -> Maybe ([MultiwayTree Char], String)
parseList :: ([MultiwayTree Char], String)
-> Maybe ([MultiwayTree Char], String)
parseList ([MultiwayTree Char]
_,[]) = Maybe ([MultiwayTree Char], String)
forall a. Maybe a
Nothing
parseList ([MultiwayTree Char]
ts,Char
')':String
xs) = ([MultiwayTree Char], String)
-> Maybe ([MultiwayTree Char], String)
forall a. a -> Maybe a
Just ([MultiwayTree Char] -> [MultiwayTree Char]
forall a. [a] -> [a]
reverse [MultiwayTree Char]
ts,String
xs)
parseList ([MultiwayTree Char]
ts,String
xs) = do
  (MultiwayTree Char
t,String
xs') <- String -> Maybe (MultiwayTree Char, String)
parse String
xs
  ([MultiwayTree Char], String)
-> Maybe ([MultiwayTree Char], String)
parseList (MultiwayTree Char
tMultiwayTree Char -> [MultiwayTree Char] -> [MultiwayTree Char]
forall a. a -> [a] -> [a]
:[MultiwayTree Char]
ts,String
xs')