Subway Trees

subway.hs

{-# LANGUAGE OverloadedStrings #-}

import Control.Arrow

import Data.List
import Data.Maybe
import Control.Applicative
import Data.Attoparsec.ByteString.Char8
import qualified Data.ByteString.Char8 as C

import qualified ScannerBS as S


data Subway = Subway [Subway]
  deriving (Show,Ord,Eq)

cannonical :: Subway -> Subway
cannonical (Subway xs)   = Subway $ sort (map cannonical xs)

parseSubway :: Parser Subway
parseSubway = Subway <$> (string "0" *> many parseSubway <* string "1")

str2sub :: C.ByteString -> Subway
str2sub s = fromJust $ maybeResult $ parse parseSubway (C.cons '0' (C.snoc s '1'))

main :: IO ()
main = C.interact $
  S.runScanner (S.numberOf (S.two S.str))
  >>> map solve >>> C.unlines

solve :: [C.ByteString] -> C.ByteString
solve = (["","same","different"] !!) . length . group . map (cannonical . str2sub)

Any chance you could explain how parseSubway builds the tree from the input string? I suppose it hinges on what <* and *> do?

Sure. The <* and *> are standard forgetful applicative combinators. They are of types (<*) :: f a -> f b -> f a and (*>) :: f a -> f b -> f b. They evaluate both arguments, and then forget about the side without the arrow. So the expression string "(" *> integer <* string ")" says to definitely parse an open paren (and fail if there isn't one), then parse an integer, then parse a close paren (and fail if there isn't one), and return just the integer.

So parseSubway can be interpreted as "To get a Subway from a string, look for a 0 (and ignore it), zero or more sub-Subways, and then a 1, and build the parsed Subway from the list of sub-Subways.

This was based on the observation that the in-order traversal of the subway tree will always have a "0" when entering a list of sub-trees, and a "1" when it is done with a list of sub-trees. It has the same structure as the Dyck Language, except using "0" and "1" instead of parenthesis.

I should have used a more standard definition parseSubway = Subway <$> many ( string "0" *> parseSubway <* string "1" ), which would have saved me a lot of grief with the need to wrap the input string in an extra 0....1.

This was based on the observation that the in-order traversal of the subway tree will always have a "0" when entering a list of sub-trees, and a "1" when it is done with a list of sub-trees. It has the same structure as the Dyck Language, except using "0" and "1" instead of parenthesis.

Great insight. Thank you!