John Ky wrote:
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.
Your 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.
:) I think that the important point is that one can think of the trees you had as things where one can insert and lookup (path,value)-pairs. This suggests a lot of useful functions like 'insert', 'union' and 'singleton' together with corresponding laws like insert k v m == union (singleton k v) m -- left biased union that are very handy for implementation.
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!
[...]
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?
Well, besides providing an actual implementation of finite maps, it is also one of the fastest available. So while 'MapString v' and 'Data.Map String v' have the same purpose, 'MapString v' will be faster. But in your case, I wouldn't bother about this now, because if it turns out that you need to change the trie data structure again, the effort spend in optimization would be wasted. Moreover, changing from 'Data.Map' to 'MapString' or similar is very transparent and therefore can be done later because you only rely on the functions like 'unionWith' that are provided by both. Also, the trick that currently reduces the problem of a finite map for the list [k] to the problem of a finite map for k can be extended to decompose arbitrary types. To get a finite map for either one of the keys k1 or k2, you can take a pair of finite maps for the keys Either k1 k2 -> v ^= (k1 -> v, k2 -> v) Similarly, a finite map for pair of keys (k1,k2) can be encoded as a composition of finite maps (k1,k2) -> v ^= k1 -> (k2 -> v) The paper has more on this.
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.
type Path k = [k]
data Trie k v = Trie v (Map k (Trie k v)) deriving Show
That's fine, adapt them recklessly to your task :)
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 rouble figuring where in the function I forgot to do something.
I don't know an easy way to implement 'insertWithInit' that works with default elements. The problem is that one has to create the default nodes when inserting u insertWithInit v0 f ["a","b","c"] x $ / \ "a" "b" v w ==> u / \ "a" "b" v w / "b" v0 / "c" x while still guaranteeing that f only acts on the inserted value x. This somehow breaks the intuition of inserting a single (key,value)-pair. If you dispense with the 'With' part, you can outsource the creation of the default nodes to 'fromPath' and employ 'union' to implement 'insertInit': insertInit :: (Ord k) => v -> Path k -> v -> Trie k v -> Trie k v insertInit vInit path v m = union m (fromPath vInit v path) In fact, that's what you did for fromList'. If there is a globally known default element, you also have the option to actually stick with (Maybe v). For example, if you do calculations with 'Int', you can do vdefault = 5 withDefault :: Maybe Int -> Int withDefault Nothing = vdefault withDefault (Maybe x) = x instance Num (Maybe Int) where x + y = Just $ withDefault x + withDefault y ... One could also do with 'Trie k v = Trie (Either v) ...' but i don't think that it's really worth it.
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.
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
Well, once you found such a really concise function, it can only be correct :) While it is not relevant in your case, note that 'union' can be extended to be applicable with the recursive trick. But the extension suggest itself by noting that you used 'Map.unionWith' instead of 'Map.union'. So, you could do unionWith :: (Ord k) => (v -> v -> v) -> Trie k v -> Trie k v -> Trie k v unionWith f (Trie k0 v0) (Trie k1 v1) = Trie (f k0 k1) v where v = Map.unionWith (unionWith f) v0 v1 union = unionWith (\_ y -> y) Regards, apfelmus