Hi apfelmus, Your code is fine, I like it. A minor hint is that mergeForest is a fold:
mergeForest = foldr merge [] Also, we have prettyPrint = putStr . unlines . prettyPrint' $ forest
Nice help on the simple things. I can't know, but it doesn't seem unreasonable that you intend to use
the ArcForest as a trie, i.e. an efficient implementation of a set of paths which allows to look up quickly whether a given path (here of type [String]) is in the set or not. So, we have
For a while, I was thinking what on Earth are you talking about, even while I continued reading the rest of the email, but it eventually clicked what you where trying to show me - which was something I didn't dare try until I got more familiar with Haskell. You're examples got me started on dealing with these sorts of complex tree structures (or tries as you call them). They made more sense as I spent more time reading and rereading them. Now, we can build up our finite map for paths:
data MapPath v = TriePath (Maybe v) (MapString (MapPath v))
because it (maybe) contains a value for the key '[] :: Path' and it (maybe) contains a map of paths that is organized by their first String element.
In my own code I had to diverge from your definition because for my needs, every node needed to contain a value (even if it was a default value). I plan to later add other numerical values to every node so that I can traverse them and do calculations that feed up and trickle down the tree. Now what about 'MapString v', how do we get this? Well, your
implementation corresponds to the choice
type MapString v = [(String,v)]
But in our case, we can apply the same trick again! We have 'String = [Char]' and given an implementation of
data MapChar v = ...
we can use exactly the same code from 'MapPath v' to implement 'MapString v'! (This reuse can be abstracted into a type class, but I'll not cover that here.) Of course, we need 'MapChar v' now. But yet, again we can think of Char as
Char ^= Int ^= [Bool]
where the '[Bool]' means the list of digits in binary representation. So, given 'MapBool v', we can implement 'MapChar v' with yet again the same code that we used for the preceding finite maps! Fortunately, the recursion ends here because a finite map for 'Bool'eans is just the pair
type MapBool v = (Maybe v, Maybe v)
That's quite beautiful, but I don't actually need to go that far. Question though, does taking the approach to this conclusion actually have real applications? In case your head does not yet hurt too much :), further information
about tries in Haskell and a detailed explanation of why the code above works, can be found in.
I did try to write my own insertWithInit called by fromPath (below), which I couldn't get working. Branches went missing from the result. I had so much trouble figuring where in the function I forgot to do something. At this point my head was about to explode, so I took a different approach using union called by fromList' (also below), which from my limited testing appears to work. I also find the union function incredibly easy to understand. I only hope I got it right. Thanks much, -John import qualified Data.Map as Map import Data.Map (Map) type Path k = [k] data Trie k v = Trie v (Map k (Trie k v)) deriving Show singleton :: v -> Trie k v singleton v = Trie v Map.empty insertWithInit :: (Ord k) => v -> (v -> v -> v) -> Path k -> v -> Trie k v -> Trie k v insertWithInit _ fInsert [] v (Trie v' m) = Trie (fInsert v v') m insertWithInit fInit fInsert (x:xs) v (Trie v' m) = Trie v' (Map.insertWith merge x subTrie m) where subTrie = insertWithInit fInit fInsert xs v (singleton fInit) merge = seq -- Left biased union union :: (Ord k) => Trie k v -> Trie k v -> Trie k v union (Trie k0 v0) (Trie k1 v1) = Trie k0 v where v = Map.unionWith union v0 v1 fromPath :: (Ord k) => v -> v -> Path k -> Trie k v fromPath initV v path = foldr addParent (singleton v) path where addParent step child = Trie initV (Map.fromList [(step, child)]) fromList :: [Path String] -> Trie String () fromList paths = foldl f (singleton ()) paths where f :: Trie String () -> Path String -> Trie String () f trie path = insertWithInit () (\x y -> ()) path () trie fromList' :: [Path String] -> Trie String () fromList' paths = foldl f (singleton ()) paths where f :: Trie String () -> Path String -> Trie String () f trie path = union trie (fromPath () () path) prettyPrint :: Trie String () -> IO () prettyPrint trie = putStrLn $ unlines $ prettyPrint' trie where prettyPrint' (Trie v m) = Map.foldWithKey f [] m f k a out = out ++ [k] ++ (map (" " ++) (prettyPrint' a))