Keyvalue apply
From HaskellWiki
(Difference between revisions)
(Nice one...) 
(Why we did this.) 

Line 37:  Line 37:  
[[User:MathematicalOrchidMathematicalOrchid]] 19:27, 15 February 2007 (UTC)  [[User:MathematicalOrchidMathematicalOrchid]] 19:27, 15 February 2007 (UTC)  
+  
+  == Outer Context ==  
+  
+  This function actually occurred in the definition of a larger utility. It has the type  
+  
+  <haskell>  
+  decode :: (Eq k) => [([k],[v])] > [k] > [v]  
+  </haskell>  
+  
+  This takes a large input, searches the lookup table for the longest possible matching key, and returns the corresponding value. It then processes the rest of the input the same way.  
+  
+  The <hask>apply</hask> function above occurs because the case actually transforms the <hask>[([k],[v])]</hask> into a ''tree'' to facilitate faster searching. (I gather that <hask>Data.Map</hask> does the exact same thing  but it's already implemented for you!)  
+  
+  Is a function like <hask>decode</hask> already out there somewhere?  
[[Category:Code]]  [[Category:Code]] 
Revision as of 12:02, 16 February 2007
I just wrote this function:
apply :: (Ord k) => k > v > (v > v) > [(k,v)] > [(k,v)] apply k v f ds = let (p1,px) = span ( (k >) . fst) ds (p2,p3) = case px of [] > ((k,v),[]) (x:xs) > if fst x == k then ((k, f $ snd x), xs) else ((k, v), x:xs) in p1 ++ (p2 : p3)
As you can see (?!), this takes a list of key/value pairs and processes it as follows:
 The function is given a key to look for.
 If the key is found, a function is applied to the associated value.
 If the key is not found, it is inserted (at the correct place) with a specified 'default value'.
apply
apply
Ord
apply
1 Data.Map
When you are making excessive use of (key,value) pairs it is usually time to switch toData.Map
apply
Data.Map.insertWith
insertWith :: Ord k => (a > a > a) > k > a > Map k a > Map k a
Here the update function receives the new value as well. Twanvl

Thanks for the tip! A whole new module for me to learn. My oh my... I do love the way Haskell type signatures almost tell you what the whole function does!
MathematicalOrchid 19:27, 15 February 2007 (UTC)
2 Outer Context
This function actually occurred in the definition of a larger utility. It has the type
decode :: (Eq k) => [([k],[v])] > [k] > [v]
This takes a large input, searches the lookup table for the longest possible matching key, and returns the corresponding value. It then processes the rest of the input the same way.
Theapply
[([k],[v])]
Data.Map
decode