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

On Thursday 02 December 2010 13:15:02, Johan Tibell wrote:

On Thu, Dec 2, 2010 at 1:04 PM, John Obbele 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