Hi apfelmus,<br><br><div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Your code is fine, I like it. A minor hint is that mergeForest is a fold:
<br> mergeForest = foldr merge []<br>Also, we have<br> prettyPrint = putStr . unlines . prettyPrint' $ forest</blockquote><div><br>Nice help on the simple things. <br></div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I can't know, but it doesn't seem unreasonable that you intend to use<br>the ArcForest as a trie, i.e. an efficient implementation of a set of<br>paths which allows to look up quickly whether a given path (here of type
<br>[String]) is in the set or not. So, we have</blockquote><div><br>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.
<br><br>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.<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Now, we can build up our finite map for paths:<br><br> data MapPath v = TriePath (Maybe v) (MapString (MapPath v))<br><br>because it (maybe) contains a value for the key '[] :: Path' and it<br>(maybe) contains a map of paths that is organized by their first String
<br>element.</blockquote><div><br>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.
<br></div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Now what about 'MapString v', how do we get this? Well, your<br>implementation corresponds to the choice
<br><br> type MapString v = [(String,v)]<br><br>But in our case, we can apply the same trick again! We have 'String =<br>[Char]' and given an implementation of<br><br> data MapChar v = ...<br><br>we can use exactly the same code from 'MapPath v' to implement
<br>'MapString v'! (This reuse can be abstracted into a type class, but I'll<br>not cover that here.) Of course, we need 'MapChar v' now. But yet, again<br>we can think of Char as<br><br> Char ^= Int ^= [Bool]
<br><br>where the '[Bool]' means the list of digits in binary representation.<br>So, given 'MapBool v', we can implement 'MapChar v' with yet again the<br>same code that we used for the preceding finite maps! Fortunately, the
<br>recursion ends here because a finite map for 'Bool'eans is just the pair<br><br> type MapBool v = (Maybe v, Maybe v)</blockquote><div><br>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?
<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">In case your head does not yet hurt too much :), further information<br>about tries in Haskell and a detailed explanation of why the code above
<br>works, can be found in.</blockquote><div><br>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.
<br><br>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.
<br><br>Thanks much,<br><br>-John<br><br>import qualified Data.Map as Map<br>import Data.Map (Map)<br><br>type Path k = [k]<br><br>data Trie k v = Trie v (Map k (Trie k v)) deriving Show<br><br>singleton :: v -> Trie k v
<br>singleton v = Trie v Map.empty<br><br>insertWithInit :: (Ord k) =><br> v -> (v -> v -> v) -> Path k -> v -> Trie k v -> Trie k v<br>insertWithInit _ fInsert [] v (Trie v' m) =<br> Trie (fInsert v v') m
<br>insertWithInit fInit fInsert (x:xs) v (Trie v' m) =<br> Trie v' (Map.insertWith merge x subTrie m)<br> where<br> subTrie = insertWithInit fInit fInsert xs v (singleton fInit)<br> merge = seq<br><br>-- Left biased union
<br>union :: (Ord k) => Trie k v -> Trie k v -> Trie k v<br>union (Trie k0 v0) (Trie k1 v1) = Trie k0 v<br> where<br> v = Map.unionWith union v0 v1<br><br>fromPath :: (Ord k) => v -> v -> Path k -> Trie k v
<br>fromPath initV v path = foldr addParent (singleton v) path<br> where<br> addParent step child = Trie initV (Map.fromList [(step, child)])<br><br>fromList :: [Path String] -> Trie String ()<br>fromList paths = foldl f (singleton ()) paths
<br> where<br> f :: Trie String () -> Path String -> Trie String ()<br> f trie path = insertWithInit () (\x y -> ()) path () trie<br><br>fromList' :: [Path String] -> Trie String ()<br>fromList' paths = foldl f (singleton ()) paths
<br> where<br> f :: Trie String () -> Path String -> Trie String ()<br> f trie path = union trie (fromPath () () path)<br><br>prettyPrint :: Trie String () -> IO ()<br>prettyPrint trie = putStrLn $ unlines $ prettyPrint' trie
<br> where<br> prettyPrint' (Trie v m) = Map.foldWithKey f [] m<br> f k a out = out ++ [k] ++ (map (" " ++) (prettyPrint' a))<br><br> </div><br></div>