Key-value apply

From HaskellWiki
Revision as of 18:25, 15 February 2007 by Twanvl (talk | contribs) (Data.Map can be used)

Jump to: navigation, search

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

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. (Note that 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.)

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 'apply'? Have you ever had call to use such a function yourself?


When you are making excessive use of (key,value) pairs it is usually time to switch to Data.Map. apply 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. --Twanvl