Personal tools

Key-value apply

From HaskellWiki

Revision as of 19:27, 15 February 2007 by MathematicalOrchid (Talk | contribs)

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
several times and you will end up with a sorted list. (Note that
uses the fact that the list is sorted to cut the search short in the 'I can't find it' case - hence the
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 '
'? 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
. Your
function is almost the same as
, 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


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)