Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Finding the first successful Map.lookup (John Obbele)
2. Re: Finding the first successful Map.lookup (Johan Tibell)
3. Re: Finding the first successful Map.lookup (Daniel Fischer)
4. Re: Finding the first successful Map.lookup (John Obbele)
5. Parser composition (Angelos Bimpoudis)
6. Re: Parser composition (Amy de Buitl?ir)
----------------------------------------------------------------------
Message: 1
Date: Thu, 2 Dec 2010 13:04:17 +0100
From: John Obbele <[email protected]>
Subject: [Haskell-beginners] Finding the first successful Map.lookup
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Hi every one !
A long time ago, I got a problem about Map.lookup and lazyness (the
programmer's one). Since it's still bugging me, I'd like to ask for some
external advice.
Let's say I've build a big documentation index (:: Map Key URL)
where both Key and URL are Strings. The problem is that my keys
have some random prefixes (ie the key "foo" could be store either
as "foo", "a_foo", "b_foo", "g_foo", "gtk_foo" or "pango_foo").
How could I implement effectively in Haskell a function which
return me the first (and only the first!) correct URL ?
For now, I'm doing something like this:
{{{
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
}}}
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 ?
regards,
/John
------------------------------
Message: 2
Date: Thu, 2 Dec 2010 13:15:02 +0100
From: Johan Tibell <[email protected]>
Subject: Re: [Haskell-beginners] Finding the first successful
Map.lookup
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On Thu, Dec 2, 2010 at 1:04 PM, John Obbele <[email protected]> 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
> }}}
>
> 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 ?
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.
Johan
------------------------------
Message: 3
Date: Thu, 2 Dec 2010 14:39:21 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Finding the first successful
Map.lookup
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Thursday 02 December 2010 13:15:02, Johan Tibell wrote:
> On Thu, Dec 2, 2010 at 1:04 PM, John Obbele <[email protected]>
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
------------------------------
Message: 4
Date: Thu, 2 Dec 2010 17:37:51 +0100
From: John Obbele <[email protected]>
Subject: Re: [Haskell-beginners] Finding the first successful
Map.lookup
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Hi Johan & Daniel,
thanks for you answers. I had forgotten the MonadPlus/msum and
the trick to use undefined.
... althought the trick with undefined here takes me quiet some
time to grasp it ... but now I know my function works lazily.
regards,
/John
------------------------------
Message: 5
Date: Fri, 3 Dec 2010 00:50:16 +0200
From: "Angelos Bimpoudis" <[email protected]>
Subject: [Haskell-beginners] Parser composition
To: <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-7"
Hi all,
This is my first post to this list. Nice to meet you!
I study Functional Programming with Haskell, and I have stuck at p.77 (the
first checkpoint in FP, as far as I understand). Passing this, I feel that I
make steps towards understanding monadic binding!
So I would like to ask about whether or not this:
P1>>=?u1 ->
P2>>=?u2 ->
P3>>=?u3 ->
P4>>=?u4 ->
return (f u1 u2 u3 u4)
can be rewritten to:
P1>>=(?u1 -> P2>>=(?u2 -> P3>>=(?u3 -> P4>>=(?u4 -> return (f u1 u2 u3
u4)))))
I am trying to understand what is the f in p>>=f in each one of above
sequencing applications?
So >>= gets you in this structure (is this the monad?), and return is the
gate out of it?
Best regards.
These are my first steps to FP!
--
Angelos Bimpoudis
Doctoral Researcher, Pervasive Computing [p-comp.di.uoa.gr]
SDE, Nessos IT S.A. [www.nessos.gr]
(m): +306942075153
<http://gr.linkedin.com/in/aggelosmp> Description: Description: Linkedin
<http://www.facebook.com/aggelosmp> Description: Description: Facebook
<http://www.studentguru.gr/blogs/grnemo/> Description: Description: Blog RSS
<http://twitter.com/aggelosmp> Description: Description: Twitter
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20101203/1c0e5b50/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/png
Size: 655 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20101203/1c0e5b50/attachment-0004.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/png
Size: 258 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20101203/1c0e5b50/attachment-0005.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/png
Size: 691 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20101203/1c0e5b50/attachment-0006.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: image/png
Size: 570 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20101203/1c0e5b50/attachment-0007.png>
------------------------------
Message: 6
Date: Thu, 2 Dec 2010 23:15:46 +0000
From: Amy de Buitl?ir <[email protected]>
Subject: Re: [Haskell-beginners] Parser composition
To: Angelos Bimpoudis <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Someone else can probably explain this better than I, but...
"return" takes a value and puts it in a minimal context that still
yields that value. I think of "return" as saying "take this ordinary
value and make a monadic value out of it, in the most straightforward
way possible". Consider the Maybe monad, for example. What kind of
value would you expect the expresion "return 7" to create? Well, there
are only two constructors for Maybe values, Just ___ and Nothing. The
latter wouldn't do any good, because it doesn't encapsulate the value
"7" in any way. So the only choice is "Just 7".
>>= is like function application, only instead of taking a normal value and
>>feeding it to a normal function, it takes a monadic value and feeds it to a
>>function that takes a normal value but returns a monadic value. It provides a
>>convenient notation for chaining a series of monadic computations together.
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 30, Issue 3
****************************************
