Playing round with traverse - can someone explain a basic List/Option example?

[Chris Marshall]

scala> val f  = (i : Int) => List(i + "F", i + "G")

f: (Int) => List[String] = <function1>

scala> 1.some traverse f

res3: List[Option[String]] = List(Some(1F), Some(1G))

So far so good

scala> none[Int] traverse f

res4: List[Option[String]] = List(None)

Err. OK? Is that right? I was expecting an empty list. Let's try with a different f

scala> val f  = (i : Int) => nil[String]

f: (Int) => List[String] = <function1>

scala> none[Int] traverse f

res8: List[Option[String]] = List(None)

scala> 1.some traverse f

res9: List[Option[String]] = List()

Say what? If I traverse nothing, I end up with more results than if I traversed something... Can someone explain why any of this makes sense, assuming that this is what I should have expected to happen.

Chris

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This is correct behaviour of the traverse function. Have you seen The
Essence of the Iterate Pattern?

* http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf
* http://etorreborre.blogspot.com/2011/06/essence-of-iterator-pattern.html

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk4LnMcACgkQmnpgrYe6r60G4QCffErFu1b0ffsTXFtS1NsdU8ek
sjYAn00TVmB1xcTcl2UEPNZrWu1X72bi
=Eb8K
-----END PGP SIGNATURE-----

[Chris Marshall]

It's precisely working through Eric's blog that caused me to hit this. I was hoping for a layman's explanation as to why it was natural behaviour for:

none[A] traverse f == List(None) ∀ f : A  => List[B]

I have tried and failed with EIP a number of times now

Chris

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To post to this group, send email to sca...@googlegroups.com.
To unsubscribe from this group, send email to scalaz+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/scalaz?hl=en.

[etorreborre]

Hi Chris,

When I read your example I was also a bit surprised, but thinking about it, it kind of makes sense. In very informal words:

• when you traverse None with f, there's no Int to put into a List so you stay with None
  
• when you traverse Some with f, there is an Int to put in a List but you choose discard it and put nothing instead

So I would say, in both cases, it's difficult to imagine something else reasonable as your end result.

Another way to have a look at it is that, what goes inside the resulting Applicative must have the "form" or "shape" of the original structure. So in case of None for the original structure, this kind of "absence" must also be present in the result.

That being said, I'm with you on that one. It's one thing to understand the algebric laws. It is another to get an intuition for what's going on. This is why I liked Dominic Verity's talk at fp-syd last month. He started with some diagrams to show us what were the geometric / topological intuitions that would be reasonable to have when thinking about arrows. Then he showed how the equations and properties were actually supporting/coding/formalizing those intuitions. And I must say that, after having written that post on EIP I do have a better grasp of what's going on but still not a complete inner intuition. I stay optimistic though because I used to have the same feeling with Monads,...

Eric.

[Runar Bjarnason]

> Err. OK? Is that right? I was expecting an empty list. Let's try with a
> different f

Why are you expecting an empty list? That's the real question.

Traverse can't know anything about your functor other than that it's
applicative. It doesn't know that there's such a thing as the empty
list. It necessarily preserves the structure of whatever your
traversal returns.

> Say what? If I traverse nothing, I end up with more results than if I
> traversed something... Can someone explain why any of this makes sense,

Again, the structure of the traversal is always preserved. If your
traversal returns empty lists, you will end up with empty lists.

Here's my suggestion: Try writing traverse yourself. This will give
you a good understanding of how it actually works and why.

[Chris Marshall]

I was expecting an empty List because I don't understand traverse properly and was hoping someone could help me. I have tried writing traverse quite a few times and I have always failed: I was having another go yesterday... Difficult to write something when you don't have a feel for what on earth it is supposed to do. I know the answer is in the types, btw :-)

Cheers always,

Chris

--
You received this message because you are subscribed to the Google Groups "scalaz" group.

[Paul Chiusano]

Hi Chris, 

The essence of the iterator pattern links that Tony gave present some intuition for what traversal is. But it is an abstract thing - in section 5.1, 5.2 and 5.3 of the paper they discuss laws they expect to hold for traversal. I haven't done this, but I'm sure you could puzzle over those laws and determine what the implementation must be. 

One useful fact about traversal is that based on the laws, if you traverse using Identity as the Applicative, you should obtain an implementation of map for the container. That says a lot about what the implementation will be. In fact, they mention in the paper that the implementation of traverse is generally the same as the implementation of map, but with function application done in the given applicative, rather than in identity. I would really see if you can puzzle out the implementation. And once you have an implementation, you can start mentally plugging in different applicatives to get an intuition for what it's doing in each case.

Paul

[Runar Bjarnason]

> I was expecting an empty List because I don't understand traverse properly

That's clear, but it might be instructive to look into what
assumptions are causing you to expect something other than what you
get.

> Difficult to write something when you don't have a feel for what on earth it
> is supposed to do. I know the answer is in the types, btw :-)

Definitely try to puzzle through it. When you look at the types in
this signature, there are a few things you know right off the bat:

def traverse[M[_]:Applicative, A, B](oa: Option[A], f: A => M[B]):
M[Option[B]] =

1. It's easy to exhaustively list everything that is in scope.

You have your arguments:
oa : Option[A]
f : A => M[B]
And an implicit argument of type Applicative[M].

2. You cannot deconstruct f any further, so you should probably
proceed by looking at oa. There are only two cases for oa, either it's
None, or Some(a). If it's None, you know how to put it in M (you can
put any value in M because you have Applicative[M]). If it's Some(a),
you can apply f(a) and put the resulting B inside Some.

Note that producing an empty M is not one of the things you can do.

[Jason Zaugg]

On Thu, Jun 30, 2011 at 9:32 PM, Runar Bjarnason <runar...@gmail.com> wrote:
> Definitely try to puzzle through it. When you look at the types in
> this signature, there are a few things you know right off the bat:
>
> def traverse[M[_]:Applicative, A, B](oa: Option[A], f: A => M[B]):
> M[Option[B]] =
>
> 1. It's easy to exhaustively list everything that is in scope.
>
>  You have your arguments:
>  oa : Option[A]
>  f : A => M[B]
>  And an implicit argument of type Applicative[M].

The instances of Traverse provided in Scalaz fall into two groups:
those that use Applicative[M].apply (List, Tree, Zipper, ...), and
those that only need Pointed[M] (Option, Either, Function0, ...).
Seems like an interesting property, does it have a name?

-jason

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I suspect there are also some that only need fmap.

PS: I am a werewolf before 0700 local time so cannot look it up.

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk4M3cIACgkQmnpgrYe6r60RFACcDJ/4wF7ijZrK59Uvs56qPgPZ
erAAn2k/5o7cGC72u7WebXutjzsk0Soc
=RsLl
-----END PGP SIGNATURE-----

[oxbow_lakes]

Thanks, Runar. That's a great explanation. As usual

Chris