Difference between revisions of "Keyvalue apply"
From HaskellWiki
(Another day, another random function...) 
BrettGiles (talk  contribs) (Clean up to make more like a howto, move context to talk page) 

(3 intermediate revisions by 2 users not shown)  
Line 1:  Line 1:  
−  I just wrote this function: 

+  ==The problem / code == 

+  Consider the function: 

<haskell> 
<haskell> 

Line 13:  Line 14:  
</haskell> 
</haskell> 

−  +  This takes a list of key/value pairs and processes it as follows: 

* The function is given a key to look for. 
* The function is given a key to look for. 

Line 19:  Line 20:  
* If the key is ''not'' found, it is inserted (at the correct place) with a specified 'default value'. 
* If the key is ''not'' found, it is inserted (at the correct place) with a specified 'default value'. 

−  Notice that if you start with a completely empty list, you can call <hask>apply</hask> several times and you will end up with a sorted list. 
+  Notice that if you start with a completely empty list, you can call <hask>apply</hask> several times and you will end up with a sorted list. <hask>apply</hask> uses the fact that the list is sorted to cut the search short in the 'I can't find it' case  hence the <hask>Ord</hask> context. 
−  Does a function like this already exist somewhere? (Hoogle seems to indicate not.) Is this a special case of something more general? Is there a better implementation? (The code isn't very readable at it is.) Can you think of a better name than just '<hask>apply</hask>'? Have you ever had call to use such a function yourself? 

+  However, Haskell already provides this and much more functionality. 

+  == The solution: <hask>Data.Map</hask> == 

+  
+  When you are making excessive use of (key,value) pairs it is usually time to switch to <hask>Data.Map</hask>. The <hask>apply</hask> function is almost the same as <hask>Data.Map.insertWith</hask>, only that function has the type: 

+  <haskell> 

+  insertWith :: Ord k => (a > a > a) > k > a > Map k a > Map k a 

+  </haskell> 

+  Here the update function receives the new value as well. 

+  
+  
+  
+  [[Category:How to]] 

[[Category:Code]] 
[[Category:Code]] 
Latest revision as of 18:36, 16 February 2007
The problem / code
Consider the 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)
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'.
Notice that if you start with a completely empty list, you can call apply
several times and you will end up with a sorted list. apply
uses the fact that the list is sorted to cut the search short in the 'I can't find it' case  hence the Ord
context.
However, Haskell already provides this and much more functionality.
The solution: Data.Map
When you are making excessive use of (key,value) pairs it is usually time to switch to Data.Map
. The apply
function is almost the same as Data.Map.insertWith
, only that function has the type:
insertWith :: Ord k => (a > a > a) > k > a > Map k a > Map k a
Here the update function receives the new value as well.