Personal tools

Key-value apply

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Nice one...)
(Why we did this.)
Line 37: Line 37:
[[User:MathematicalOrchid|MathematicalOrchid]] 19:27, 15 February 2007 (UTC)
[[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:Code]]
[[Category:Code]]

Revision as of 12:02, 16 February 2007

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?

1 Data.Map

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

2 Outer Context

This function actually occurred in the definition of a larger utility. It has the type 

decode :: (Eq k) => [([k],[v])] -> [k] -> [v]

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
apply
function above occurs because the case actually transforms the
[([k],[v])]
into a tree to facilitate faster searching. (I gather that
Data.Map
does the exact same thing - but it's already implemented for you!) Is a function like
decode
already out there somewhere?
Retrieved from "http://www.haskell.org/haskellwiki/Key-value_apply"

Category: Code