The essence of the iterator pattern

14 views
Skip to first unread message

Chen Harry

unread,
Mar 27, 2018, 5:51:14 AM3/27/18
to scala...@googlegroups.com
I am reading the paper(https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf) these days. to better understanding it, I try to translate it into Scala. it looks like no-brain translation until I try to implement AppAdapter (page 13). Because Scala doesn't support rank-2 type directly, I use this encoding(https://gist.github.com/chenharryhua/0140ba492554fd81540082fb4b95579a#file-essence_of_iterator_pattern-scala-L37). 
it works but looks not very correct to me since the AppAdapter defined in Haskell is:
 data AppAdapter m where
    AppAdapter::Applicative (g m) ⇒
    (∀a. m a → g m a) → (∀a. g m a → m a) → AppAdapter m
which takes one type parameter. mine unfortunately has two. :(

I guess that in Haskell, the g is not an existential type(where a is)? 

Or the AppAdapter in Haskell might be defined like this?
 data AppAdapter g m where
    AppAdapter::Applicative (g m) ⇒
    (∀a. m a → g m a) → (∀a. g m a → m a) → AppAdapter m

I appreciate if someone shed a light on it.

Cheers,
Harry
 


Tony Morris

unread,
Mar 27, 2018, 5:55:59 AM3/27/18
to scala...@googlegroups.com

Hi Chen,
You might not know that Eric Torreborre has translated this paper to Scala:
https://etorreborre.blogspot.com.au/2011/06/essence-of-iterator-pattern.html

To answer your question, to represent (∀a. m a → g m a) you write something like:

trait HaveToThinkUpAName[M[_], G[_[_], _] {
  def apply[A](names: M[A]): G[M, A]
} // not type-checked, straight from head

The position of the forall quantifier (∀) informs where the type variables go in the translation.

--
You received this message because you are subscribed to the Google Groups "Melbourne Scala User Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-melb+...@googlegroups.com.
To post to this group, send email to scala...@googlegroups.com.
Visit this group at https://groups.google.com/group/scala-melb.
For more options, visit https://groups.google.com/d/optout.

signature.asc

Chen Harry

unread,
Mar 27, 2018, 6:14:35 AM3/27/18
to scala...@googlegroups.com
Hi, Tony, thank you very much. just quote from Eric: :)
Eric said...

Wow, coming from you, that makes me both happy and proud!

7:39 PM
the HaveToThinkUpAName trait looks isomorphic to the encoding below. I am pretty sure it is type-checked, at least in Scala. :)
trait AppAdapter[G[_[_], _], M[_]] {
def insert[A]: M[A] => G[M, A]
def retrieve[A]: G[M, A] => M[A]
}
By the way, I didn't find the AppAdpater in Eric's post which looks great.
Cheers,
Harry

Chen Harry

unread,
Mar 27, 2018, 6:25:09 AM3/27/18
to scala...@googlegroups.com
Eric's post is very good, especially for Scala programmer. 
the insert method in AppAdapter is isomorphic to the apply method in HaveToThinkUpAName..

Reply all
Reply to author
Forward
0 new messages