January 31, 2008

Python 2.5's iterators in Haskell (sort of)

DISCLAIMER! The code I present here is likely to be far from perfect and in fact I ask for comments from the community, specifically on how to get rid of the "RecPair" user data type.

Is it possible to mimic Python 2.5's iterators in Haskell? If you don't
know what iterators are (or you're used to 2.4's ones), have a look to PEP343.
By and large, iterators are Python's way to surrogate continuations, which
represent a more general concept usually found in FP languages.

Basically, I want to be able to write something like:


bar = do y <- yield 1
yield (y+2)


and have bar return immediately the argument in a yield call to the caller. Yet, the caller should look like:


foo k = do x <- send undefined -- this will be ignored
y <- send k
return $ [x,y]


First two considerations:


  • It natural to use the Cont monad when implementing the yield function.

  • As two successive calls to send may have different outcomes, some sort of state must be involved. For the basic implementation we resort to State monad.



When trying to solve the puzzle, I stumbled upon a beautiful and straightforward implementation of Python 2.4's iterators by David Menendez. The problem of extending his approach to 2.5 iterators turned out to be a bit more difficult. First, I'll show you the code:


module Main where

import Control.Monad.Cont
import Control.Monad.State

data RecPair a b = Nil RP (b,a -> RecPair a b)

yield x = Cont $ \k -> RP (x,k)

send x = do (RP (y,f)) <- get
put $ f x
return y

runYield it cl = evalState cl $ runCont it $ \_ -> Nil


Let's discuss the yield funtion's implementation. First, as we're working
in the Cont monad, we must return a Cont value which is basically a
function taking a continuation (what to do next) and build a pair (x,k).

x is the value passed to the yield function and then returned to the
caller.

What about k? In my mind, k is a function taking an argument (the
receiving variable of a '<-' statement in a do-block) and returning another pair (x',k'), which is the result of the next small step of the Cont computation, till the next yield call. In this way, a computation can't go on after a yield statement until you feed it with a value through a send call, which is the semantics of iterators. Naively, at start I wrote: yield x = Cont $ \k -> (x,k)

But ghc promptly issued the following error:


Occurs check: cannot construct the infinite type t = a -> (t1,t)


What's going on? Let's try and do some type analysis:


  1. The type of "\k -> (x,k)" is "t -> (b,t)" which is perfectly right, as long as "x" is in the scope of that definition and is of type "b".

  2. But, the argument of "Cont" must have type "(a -> r) -> r".

  3. Let's do the bindings: "t = a -> r" and "r = (b,t)".

  4. Substituting the latter in the former we obtain "t = a -> (b,t)".



This equation is clearly impossible to solve (no types exist to make the
equation true) and the Haskell's type system did his job.

How to escape the problem? The real point here is that the above type
equation can be expanded infinitely. There must be a way to stop the
expansion. What if "r" would be masked by an opaque type?

Enter RecPair. We turn the above equation into:


t = a -> RecPair a b


which is perfectly solvable provided there are instances of the type
"RecPair a b". In the above snippet you can find a convenient definition of
RecPair which is suitable to our goal. There are other, like:


data RecPair a b = Nil RP (a -> (b,RecPair a b))


which turns out to be less elegant when you modify yield and send
accordingly.

The other part of the code is just plain Haskell code. Notice that solution
I proposed doesn't mimic completely Python 2.5's iterators: for example,
send can't deal with more than one iterator at the time due to the use of the State monad.

But these are only technicalities which can be easily overcome, for instance,
using the IO Monad and a couple of IORef here and there.

47 comments:

vignesh m said...

Hi this is raj i am having 3 years of experience as a php developer and i am certified. i have knowledge on OOPS concepts in php but dont know indepth. After learning hadoop will be enough to get a good career in IT with good package? and i crossed hadoop training in chennai website where someone please help me to identity the syllabus covers everything or not??
Thanks,
raj

Surya Prakash said...


Hi this is abinaya i am having 3 years of experience as a java developer and i am certified. i have knowledge on OOPS concepts in java but dont know indepth. After learning oracle will be enough to get a good career in IT with good package? and i crossed Oracle Training in Chennai website where someone please help me to identity the syllabus covers everything or not??

Thanks, abinaya

Surya Prakash said...

Hi this is abinaya i am having 3 years of experience as a java developer and i am certified. i have knowledge on OOPS concepts in java but dont know indepth. After learning oracle will be enough to get a good career in IT with good package? and i crossed oracle training chennai website where someone please help me to identity the syllabus covers everything or not??

Thanks, abinaya

Ganesh said...

Hi, this is Ganesh I am having 3 years of experience as a Dot Net developer and I am certified. I have Knowledge on OOPS Concepts in .NET indepth. After learning Salesforce will be enough to get a good career in IT with good Package? and i crossed Salesforce Training in Chennai website where someone please help me to identify the syllabus covers everything or not??

Thanks, Ganesh

Ganesh said...

Hi, this is Ganesh I am having 3 years of experience as a Dot Net developer and I am certified. I have Knowledge on OOPS Concepts in .NET indepth. After learning Salesforce will be enough to get a good career in IT with good Package? and i crossed Salesforce Training in Chennai website where someone please help me to identify the syllabus covers everything or not??

Thanks, Ganesh

dwara kesh said...

Hi this is dwarakesh i am having 3 years of experience as a php developer and i am certified. i have knowledge on OOPS concepts in php but dont know
indepth. After learning java will be enough to get a good career in IT with good package? and i crossed
java training in chennai website where someone please help me to identity the syllabus covers everything or

not??

thanks, dwarakesh

dwara kesh said...


Hi this is dwarakesh i am having 3 years of experience as a php developer and i am certified. i have knowledge on OOPS concepts in php but dont know
indepth. After learning java will be enough to get a good career in IT with good package? and i crossed
java training in Chennai website where someone please help me to identity the

syllabus covers everything or not??

thanks, dwarakesh

Kathiresan Muthu said...

Hi this is Kathiresan i am having 3 years of experience as a dot net developer and i am certified. i have knowledge on OOPS concepts in .NET but dont know indepth. After learning android will be enough to get a good career in IT with good package? and i crossed Android Training in Chennai website where someone please help me to identity the syllabus covers everything or not??

Thanks,
kathiresan

Kathiresan Muthu said...

Hi this is Kathiresan i am having 3 years of experience as a dot net developer and i am certified. i have knowledge on OOPS concepts in .NET but dont know indepth. After learning android will be enough to get a good career in IT with good package? and i crossed Android Training in Chennai website where someone please help me to identity the syllabus covers everything or not??

Thanks,
kathiresan

Ganesh M said...


Hi this is Ganesh i am having 3 years of experience as a java developer

and i am certified. i have knowledge on OOPS concepts in java but dont

know indepth. After learning php will be enough to get a good career in IT

with good package? and i crossed php training in chennai

website where someone please help me to identity the syllabus covers

everything or not??

thanks,Ganesh.

Ganesh M said...

Hi this is Ganesh i am having 3 years of experience as a java developer

and i am certified. i have knowledge on OOPS concepts in java but dont

know indepth. After learning php will be enough to get a good career in IT

with good package? and i crossed php training in chennai

website where someone please help me to identity the syllabus covers

everything or not??

thanks,Ganesh.

Ganesh M said...

Hi this is Ganesh i am having 3 years of experience as a java developer

and i am certified. i have knowledge on OOPS concepts in java but dont

know indepth. After learning php will be enough to get a good career in IT

with good package? and i crossed php training in chennai

website where someone please help me to identity the syllabus covers

everything or not??

thanks,Ganesh.

kovalan Jayamurugan said...

Thanks for your detailed information. You need to have attractive and informative elements in your website to impress visitors on the first site. Infographic will help you to deliver information in attractive way. PHP Course in Chennai

murali karthik said...

Thanks for your informative article on Java script. It is an advanced scripting language used at client side. Every event or action carried out in client side is validated by this scripting language. web design training in Chennai

Victoria John said...

Java is one of the popular technologies with improved job opportunity for hopeful professionals. Java Training in Chennai helps you to study this technology in details.

Victoria John said...

Thanks for sharing this informative blog. If anyone wants to get Android Training in Chennai reach FITA Academy located at Chennai, Velachery.

rebeka christy said...

If anyone want to become an oracle certified professional reach FITA, which offers best Oracle Training in Chennai with years of experienced professionals. For more details about oracle, sql training visit this site.

Oracle Training Institutes in Chennai

john son said...

Thanks for sharing this informative blog. If anyone want to get ios training, android training in Chennai please refer this link. Android Training Institutes in Chennai, Android Training in Chennai

Emi Jackson said...

Thanks for sharing this informative blog. FITA provides Salesforce Training in Chennai with years of experienced professionals and fully hands-on classes. Salesforce is a cloud based CRM software. Today's most of the IT industry use this software for customer relationship management. To know more details about salesforce reach FITA Academy. Rated as No.1 Salesforce Training Institutes in Chennai.

Emi Jackson said...

Your information is really useful for me. If anyone wants to get SEO Training in Chennai visit FITA Academy located at Chennai. Rated as No.1 SEO Training institutes in Chennai.



Emi Jackson said...

I have read your blog and i got a very useful and knowledgeable information from your blog.its really a very nice article.You have done a great job . If anyone want to get Salesforce Training in Chennai, Please visit FITA academy located at Chennai Velachery.



Victoria John said...

Java is one of the popular technologies with improved job opportunity for hopeful professionals. Java Training in Chennai helps you to study this technology in details.If you are looking for best Java Training Institutes in Chennai reach Fita academy.

christina jeni said...

Thanks for sharing this informative blog. If anyone wants to get Best Unix Training in Chennai, Please visit Fita Academy located at Chennai, Velachery.

christina jeni said...

Thank you for your sharing this informative blog. I have bookmarked this page for my future reference. Recently I did PHP course at a leading academy. If you are looking for best PHP Training Institutes in Chennai visit FITA IT training and placement academy

christina jeni said...

It was really a wonderful article and I was really impressed by reading this blog. We are giving all software Course Online Training. The HTML5 Training Institutes in Chennai is one of the reputed Training institute in Chennai. They give professional and real time training for all students.

Roshini Balu said...

Thanks for sharing these niche piece of coding to our knowledge. Here, I had a solution for my inconclusive problems & it’s really helps me a lot keep updates…
php training in velachery

john son said...

Dot Net Training Chennai

Thanks for your wonderful post.It is really very helpful for us and I have gathered some important information from this blog.If anyone wants to get Dot Net Training in Chennai reach FITA, rated as No.1 Dot Net Training Institute in Chennai.

Dot Net Course in Chennai


john son said...

Android Training Chennai

Your blog is really useful for me. Thanks for sharing this useful blog..Suppose if anyone interested to learn Android Training in Chennai please visit fita academy which offers best Android Course in Chennai at reasonable cost.

Android Training Institutes in Chennai

Martina Christy said...

Software Testing Training in Chennai

I have read your blog and i got a very useful and knowledgeable information from your blog.its really a very nice article. I did Loadrunner Course in Chennai. This is really useful for me. Suppose if anyone interested to learn Manual Testing Course in Chennai reach FITA academy located at Chennai Velachery.

Andria BZ said...

I have read all the post in your blog; was really impressed after reading it. If anyone focuses the Best Hadoop training in chennai . Let us know we are ready to serve for your career. FITA is pleased to inform you that; we provides practical training on all the technologies with the MNC exports having more than 5 years of experience in your preferred domain. Get your career with our knowledge.
Hadoop courses in Chennai|Hadoop institutes in Chennai

Andria BZ said...

Thanks for sharing this valuable information to our vision. You have posted a trust worthy blog keep sharing.Web design training in Chennai

Jhon anderson said...

I see this content as a Unique and very informative article. Impressive article like this may help many like me in finding the best Hadoop Training in Chennai

jack wilson said...

Testing Training in Chennai

Its really awesome blog..If anyone wants to get Software Testing Training in Chennai visit FITA IT academy located at Chennai. Rated as No.1 Software Testing Training Institutes in Chennai

Software Testing Course in Chennai

jack wilson said...

QTP Training in Chennai

Hi, I wish to be a regular contributor of your blog. I have read your blog. Your information is really useful for beginner. I did Software Testing Course in Chennai at Fita training and placement academy which offer best Software Testing Training in Chennai with years of experienced professionals. This is really useful for me to make a bright career.

Regards...

Software Testing Training Institutes in Chennai

Victoria John said...

HTML5 Training in Chennai

Your blog is really awesome. Thank you for your sharing this informative blog. Recently I did PHP course at a leading academy. If you are looking for best PHP Training Institute in Chennai visit FITA IT training academy which offer real time PHP Training in Chennai.

PHP Course in Chennai

Victoria John said...

SAP Training

Thanks for sharing this valuable information.and I gathered some information from this blog. I did SAP Training in Chennai, at FITA Academy which offer best SAP Course in Chennai with years of experienced professionals.

Regards.......

SAP Training Institute in Chennai

Roshini RS said...

Thanks for sharing... Actually Hadoop is a highly growing & scoopful technology in IT market it’s an open-source software framework for managing big data in a distributed fashion on large commodity computing hardware. FITA provides Hadoop training in Chennai get in to fita and out with your career.

christina jeni said...

Oracle Training

The information you posted here is useful to make my career better keep updates..If anyone want to become an oracle certified professional reach FITA Oracle Training Institutes in Chennai, which offers Best Oracle Training in Chennai with years of experienced professionals.

dhanamlakshmi palu said...

Thanks for sharing this valuable information to our vision. You have posted a trust worthy blog keep sharing.Nice article i was really impressed by seeing this article, it was very interesting and it is very useful for me.. Cloud Computing Training in chennai | Cloud Computing Training chennai | Cloud Computing Course in chennai | Cloud Computing Course chennai

Melisa said...

Pretty article! I found some useful information in your blog, it was awesome to read, thanks for sharing this great content to my vision, keep sharing.
Regards,
Web design course in Chennai

Kana Gokul said...

Thanks for your informative article on software testing. Your post helped me to understand the future and career prospects in software testing. Keep on updating your blog with such awesome article.
Python Training Institute in Chennai

caroline jesi said...

Pretty article! I found some useful information in your blog, it was awesome to read, thanks for sharing this great content to my vision, keep sharing.
Regards,
PHP Training in Chennai | PHP Training Chennai | PHP Course in Chennai

kovalan Jayamurugan said...

Excellent post!!! Selenium automation testing tool makes your software validation process lot simpler. Keep on updating your blog with such awesome information. Selenium Training in Chennai | Selenium Course in Chennai | Selenium training institute in Chennai

Andria BZ said...

I am reading your post from the beginning, it was so interesting to read & I feel thanks to you for posting such a good blog, keep updates regularly.
Regards,
Salesforce training in Chennai|Salesforce training |Salesforce training institute in Chennai

Melisa said...

This information is impressive; I am inspired with your post writing style & how continuously you describe this topic. After reading your post, thanks for taking the time to discuss this, I feel happy about it and I love learning more about this topic.
Regards,
php training institutes|php training in velachery|php training institute

Amirtha rao said...

I feel satisfied to read your blog, you have been delivering a useful & unique information to our vision even you have explained the concept as deep clean without having any uncertainty, keep blogging.
Web design institutes in Chennai|Web design training institutes in Chennai|Web designing course in chennai

hari said...

Thanks for sharing such informative article on Load runner Automation testing tool. This load testing tool will provide most precise information about the quality of software.
Best Python training in chennai