# Key-value apply

### From HaskellWiki

(Difference between revisions)

(Why we did this.) |
BrettGiles (Talk | contribs) (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 13: | ||

</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 19: | ||

* 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]] |

## Latest revision as of 18:36, 16 February 2007

## [edit] 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'.

apply

apply

Ord

However, Haskell already provides this and much more functionality.

## [edit] 2 The solution: Data.Map

When you are making excessive use of (key,value) pairs it is usually time to switch to Data.Map

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