Personal tools

Key-value apply

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Why we did this.)
Current revision (18:36, 16 February 2007) (edit) (undo)
(Clean up to make more like a how-to, move context to talk page)
 
Line 1: Line 1:
-
I just wrote this function:
+
==The problem / code ==
 +
Consider the function:
<haskell>
<haskell>
Line 13: Line 14:
</haskell>
</haskell>
-
As you can see (?!), this takes a list of key/value pairs and processes it as follows:
+
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. (Note that <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.)
+
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.
-
== Data.Map ==
+
== 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>. Your <hask>apply</hask> function is almost the same as <hask>Data.Map.insertWith</hask>, only that function has the type:
+
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>
<haskell>
insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
</haskell>
</haskell>
Here the update function receives the new value as well.
Here the update function receives the new value as well.
-
--[[User:Twanvl|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!
 
-
 
-
[[User:MathematicalOrchid|MathematicalOrchid]] 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:How to]]
[[Category:Code]]
[[Category:Code]]

Current revision

1 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.

2 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.

Retrieved from "http://www.haskell.org/haskellwiki/Key-value_apply"

Categories: How to | Code