Graph.toTree (haskell & scala)

toTree.hs

import qualified Data.Map as Map
import qualified Data.Set as Set
import Data.List
import Text.Regex
import Control.Monad.State
import Control.Applicative

-- some setup for the types
type Graph a = Map.Map a [a]
data Tree a = Tree
              { root :: a
              , children :: [Tree a]
              } deriving (Eq, Ord)
instance (Show a) => (Show (Tree a)) where
  show tree =
    show (root tree)
    ++
    concatMap ("\n"++) 
      (map (intercalate "\n" . map ("  " ++) . splitRegex (mkRegex "\n") . show) (children tree))

toTree :: (Ord a) => Graph a -> a -> State (Set.Set a) (Tree a)
toTree graph node = do
    visited <- get
    (Tree node . reverse) <$>
      foldl
        (\siblingTrees child ->
          siblingTrees >>= \strs -> (:strs) <$> toTree graph child)
        (return [] <* modify (Set.insert node))
        (filter (`Set.notMember` visited) $ Map.findWithDefault [] node graph)

mapFst :: (a -> b) -> (a, c) -> (b, c)
mapFst fn (a, c) = (fn a, c)
mapSnd :: (b -> c) -> (a, b) -> (a, c)
mapSnd fn (a, b) = (a, fn b)

exampleGraph :: Map.Map String [String]
exampleGraph = Map.fromList
  [ ("tree", ["branch"])
  , ("branch", ["apple", "banana"])
  , ("apple", ["tree"])
  ]

main :: IO ()
main = print $ evalState (toTree exampleGraph "tree") Set.empty

toTree.scala

case class Tree[A](root: A, children: List[Tree[A]])

def toTree[A](root: A, graph: Map[A, List[A]]): Tree[A] = {
  def visit(node: A, graph: Map[A, List[A]], visited: Set[A]): (Tree[A], Set[A]) = {
    graph.get(node) match {
      case None => (Tree(node, Nil), visited + node)
      case Some(children) =>
        val (childTrees, newVisited) =
          children.filterNot(visited)
            .foldLeft((List.empty[Tree[A]], visited + node)){ case ((siblingTrees, visitedSoFar), child) =>
              val (childTree, newVisited) = visit(child, graph, visitedSoFar)
              (childTree :: siblingTrees, newVisited)
            }
        (Tree(node, childTrees.reverse), newVisited)
    }
  }
  visit(root, graph, Set())._1
}