some insights into functional programming

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

some insights into functional programming

Michael Mossey
I'm starting to figure out a few things that I didn't "get" about
functional programming and monads. I wanted to explain them. I'm not
looking for a particular response to this post, other than any elaboration
that seems natural.

There is an exercise here working with the trivial monad W:

<http://blog.sigfpe.com/2007/04/trivial-monad.html>

Write a function
g :: W a ->  W a -> W a

such that
g (W x) (W y) = W (x+y)

except don't use pattern matching, but >>= instead. The answer is

g mx my = mx >>= (\x -> my >>= \y -> W (x+y))

There are a couple things here that threw me off. One is that I didn't
expect 'my' to be available inside the first lambda. I somehow thought of
lambda as isolated, sealed-off from the rest of the universe. But they
aren't. I believe this is the concept of closures, or related to it?

Secondly, I didn't expect >>= to be available inside the lambda. This is
related to the mistaken conception of >>= as a procedural statement rather
than an expression. In Python, where I have previously encountered lambdas,
no statements are allowed inside lambdas. Of course, >>= is actually an
expression and you can put any expression to the right of a lambda ->.

Maybe these are typical beginner misconceptions, or maybe they have more to
do with coming from Python and complete beginners actually find it more
natural.

Mike

Reply | Threaded
Open this post in threaded view
|

some insights into functional programming

John Dorsey-2
Michael,

> g mx my = mx >>= (\x -> my >>= \y -> W (x+y))
>
> There are a couple things here that threw me off. One is that I didn't  
> expect 'my' to be available inside the first lambda. I somehow thought of
> lambda as isolated, sealed-off from the rest of the universe. But they  
> aren't. I believe this is the concept of closures, or related to it?

Yes!  You're spot on; 'my' is available precisely because closures
encapsulate the part of the surrounding environment that's referenced by
bound variables.

> Secondly, I didn't expect >>= to be available inside the lambda. This is  
> related to the mistaken conception of >>= as a procedural statement
> rather than an expression. In Python, where I have previously encountered
> lambdas, no statements are allowed inside lambdas. Of course, >>= is
> actually an expression and you can put any expression to the right of a
> lambda ->.

With all due respect to Python (a language I like but no longer use), it's
no place to develop any intuition about lambdas.

Python's lambda is an attempt to incorporate some of the syntactic benefit
of anonymous functions while refusing them any real meaning or importance.

> Maybe these are typical beginner misconceptions, or maybe they have more
> to do with coming from Python and complete beginners actually find it
> more natural.

As you can probably guess, I think it's more the latter.  But I can't say
first-hand because I dabbled in dozens of languages before Haskell, and I
got my intuition for lambda from scheme.  I wish I'd learned them in Haskell
though, because with purity they're more elegant.

Cheers,
John

Reply | Threaded
Open this post in threaded view
|

some insights into functional programming

Adam Bergmark
In reply to this post by Michael Mossey
The reason my is available in the lambda \x -> my >>= \y -> W (x+y)  
has to do with scoping rules, Haskell (and almost all programming  
languages) use static scoping, meaning a variable defined in an outer  
function is available in the inner function, for instance, (\a -> \b -
 > (a,b)) 1 2 will evauate to (1,2) since a is bound to 1 in the outer  
lambda, and the inner one can refer to the outer one, if instead you  
write (\a -> \a -> (a,a)) 1 2 the result will be (2,2) since the  
innermost a will be used (no ambiguity here, but  if shadowing is done  
by accident it can be hard to find the error). The book Structure and  
Interpretation of Computer Programs (freely available online)  
discusses this subject in detail.

 >>= is available inside the lambda for the same reason, >>= is  
imported into the modules namespace, and therefore available  
everewhere, unless a shadowing binding exists.

I wouldn't say that this has anything to do with functional  
programming specifically.

This also exists in Python i might add, you can read variables defined  
in an outer scope:
 >>> a = 1
 >>> f()
 >>> def f():
...   return a
...
 >>> f()
1

The fact that most languages are scoped like this is nothing obvious,  
and like I said, Python is the same.


I hope this helps!

/ Adam


On Aug 9, 2009, at 9:31 PM, Michael Mossey wrote:

> I'm starting to figure out a few things that I didn't "get" about  
> functional programming and monads. I wanted to explain them. I'm not  
> looking for a particular response to this post, other than any  
> elaboration that seems natural.
>
> There is an exercise here working with the trivial monad W:
>
> <http://blog.sigfpe.com/2007/04/trivial-monad.html>
>
> Write a function
> g :: W a ->  W a -> W a
>
> such that
> g (W x) (W y) = W (x+y)
>
> except don't use pattern matching, but >>= instead. The answer is
>
> g mx my = mx >>= (\x -> my >>= \y -> W (x+y))
>
> There are a couple things here that threw me off. One is that I  
> didn't expect 'my' to be available inside the first lambda. I  
> somehow thought of lambda as isolated, sealed-off from the rest of  
> the universe. But they aren't. I believe this is the concept of  
> closures, or related to it?
>
> Secondly, I didn't expect >>= to be available inside the lambda.  
> This is related to the mistaken conception of >>= as a procedural  
> statement rather than an expression. In Python, where I have  
> previously encountered lambdas, no statements are allowed inside  
> lambdas. Of course, >>= is actually an expression and you can put  
> any expression to the right of a lambda ->.
>
> Maybe these are typical beginner misconceptions, or maybe they have  
> more to do with coming from Python and complete beginners actually  
> find it more natural.
>
> Mike
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners

Reply | Threaded
Open this post in threaded view
|

some insights into functional programming

Michael Mossey
Thanks for the ideas, Adam. I still have a few questions.

Adam Bergmark wrote:
> The reason my is available in the lambda \x -> my >>= \y -> W (x+y) has
> to do with scoping rules, Haskell (and almost all programming languages)
> use static scoping, meaning a variable defined in an outer function is
> available in the inner function, for instance, (\a -> \b -> (a,b)) 1 2
> will evauate to (1,2) since a is bound to 1 in the outer lambda, and the
> inner one can refer to the outer one, if instead you write (\a -> \a ->
> (a,a)) 1 2 the result will be (2,2) since the innermost a will be used
> (no ambiguity here, but  if shadowing is done by accident it can be hard
> to find the error).


Because the lambda is executed by the implementation of >>=, doesn't the concept
closure still apply? That value of 'my' has to "get into" the other routine.

I am aware that other languages have closures, but in Python they are an
advanced, rarely explored concept, so I haven't gotten a good intuition for
them. (I don't mean to imply I've only programmed in Python---also Lisp and C++,
but only to do boring things, never anything sophisticated from a CS point of
view.)

It's not that I don't understand the use of 'my'---it's just that it didn't
occur to me at first.

> The book Structure and Interpretation of Computer
> Programs (freely available online) discusses this subject in detail.
>
>  >>= is available inside the lambda for the same reason, >>= is imported
> into the modules namespace, and therefore available everewhere, unless a
> shadowing binding exists.
>

The problem is not that I didn't expect >>= to be outside the namespace. The
problem is that I am still having to "unlearn" imperative concepts, so it was
all too easy to think of >>= as an imperative concept, and in Python procedural
statements are not allowed inside lambdas. Also, in the early stages of learning
Haskell there are no monads used inside lambdas. So it's not that anyone told me
I couldn't do it, just that it didn't occur to me the first time I saw the problem.

There is no great revelation here, other than my own satisfaction at seeing a
little deeper into the way things are done in Haskell, and finding these
problems much easier after revisiting them (I didn't do anything Haskell for a
couple months, and just came back to it).

-Mike
Reply | Threaded
Open this post in threaded view
|

some insights into functional programming

Magnus Therning
Michael P Mossey wrote:

> Thanks for the ideas, Adam. I still have a few questions.
>
> Adam Bergmark wrote:
>> The reason my is available in the lambda \x -> my >>= \y -> W (x+y) has to
>> do with scoping rules, Haskell (and almost all programming languages) use
>> static scoping, meaning a variable defined in an outer function is
>> available in the inner function, for instance, (\a -> \b -> (a,b)) 1 2 will
>> evauate to (1,2) since a is bound to 1 in the outer lambda, and the inner
>> one can refer to the outer one, if instead you write (\a -> \a -> (a,a)) 1
>> 2 the result will be (2,2) since the innermost a will be used (no ambiguity
>> here, but  if shadowing is done by accident it can be hard to find the
>> error).
>
>
> Because the lambda is executed by the implementation of >>=, doesn't the
> concept closure still apply? That value of 'my' has to "get into" the other
> routine.

I think you are both right.  AFAIU Adam comments on *visibility* of the
variables, while you look more at the fact that you pass the lambda as an
argument to (>>=).  The lambda can "see" the variable my due to scoping, and
(>>=) can trigger evaluation of the lambda due to closures.

I'm looking forward to be corrected by someone who knows more about this than
I do.

/M

--
Magnus Therning                        (OpenPGP: 0xAB4DFBA4)
magnus?therning?org          Jabber: magnus?therning?org
http://therning.org/magnus         identi.ca|twitter: magthe

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: OpenPGP digital signature
Url : http://www.haskell.org/pipermail/beginners/attachments/20090811/303059f8/signature.bin