[Haskell-beginners] Finding the first successful Map.lookup

[Daniel Fischer]

On Thursday 02 December 2010 13:15:02, Johan Tibell wrote:
> On Thu, Dec 2, 2010 at 1:04 PM, John Obbele <john.obbele at gmail.com> 
wrote:
> > {{{
> > type Key = String
> > type URL = String
> >
> > lookupDocumentation :: Map Key URL -> Key -> Maybe URL
> > lookupDocumentation myMap key =


> >        let r = map (lookupSymbols myMap) [ key
> >                                          , "a_" ++ key
> >                                          , "b_" ++ key
> >                                          , "g_" ++ key
> >                                          , "gtk_" ++ key
> >                                          , "pango_" ++ key
> >                                          ]
> >        in case catMaybes r of
> >             []    -> Nothing
> >             (x:_) -> Just x

With an import from Control.Monad, you can write that as

msum (map (lookupSymbols myMap) [pre ++ key | pre <- ["", "a_", "b_", "g_", 
"gtk_", "pango_"]]

> > }}}
> >
> > My problem is: will `lookupDocumentation` perform n=6 lookups in my
> > Map, or will Haskell-built-in-lazyness only evaluate till an URL is
> > found ?

It will only perform the lookups needed to determine the outcome. If the 
un-prefixed key is in the map, only one lookup will be done.

>
> You can test this by creating a Map that contains undefined values e.g.
>
> {{{
> lookupDocumentation (insert "b_somekey" undefined (singleton
> "a_somekey" "somevalue")) "somekey"
> }}}
>
> Since "a_somekey" is checked before "b_somekey" and "a_somekey" is in
> the map, this should work if the function is lazy enough.

That would work even if all prefixes are looked up,

catMaybes [Nothing, Just "somevalue", Just undefined, Nothing, Nothing, 
Nothing]

evaluates to ["somevalue",undefined] without a problem.

To check it, you need a key which throws an error if compared to one of the 
later prefixed keys, for example

lookupDocumentation (insert ("b_somekey" ++ undefined) "b" (singleton 
"a_somekey" "a")) "somekey"

works while inserting something with the key ("somekey" ++ undefined) 
throws an exception.

>
> Johan