List's flatten vs flatMap implementation

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

List's flatten vs flatMap implementation

Daryoush Mehrtash-2
I am trying to understand the implementation difference between List class's flatten and flatMap methods.    I can see that flatten uses implicit 
function as arguments and flatMap is final method. Otherwise it seems to me that the implementation is the same. Am I missing something?

Is there a reason why flatMap is not using foreach method? Here are the methods:

def flatten[B](implicit f : A => Iterable[B]) : List[B] = {
val buf = new ListBuffer[B]
foreach(f(_).foreach(buf += _))
buf.toList
}

  final
 override def foreach(f: A => Unit) {
var these = this
while (!these.isEmpty) {
f(these.head)
these = these.tail
}
}

final override def flatMap[B](f: A => Iterable[B]): List[B] = {
val b = new ListBuffer[B]
var these = this
while (!these.isEmpty) {
var those = f(these.head).elements
while (those.hasNext) {
b += those.next
}
these = these.tail
}
b.toList
}
--
Daryoush

Weblog:   http://perlustration.blogspot.com/
Reply | Threaded
Open this post in threaded view
|

Re: List's flatten vs flatMap implementation

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

Hi Daryoush,

Daryoush Mehrtash wrote:
> I am trying to understand the implementation difference between List
> class's flatten and flatMap methods.    I can see that flatten uses
> implicit
> function as arguments and flatMap is final method.  Otherwise it seems
> to me that the implementation is the same.    Am I missing something?
>
> Is there a reason why flatMap is not using foreach method?   Here are
> the methods:

foreach would imply a side-effect, which would definitely not fit in
with flatMap. Perhaps you mean map? In which case, see below.

>
>  *def* flatten[B](*implicit* f : A => Iterable[B]) : List[B] = {
>     *val* buf = *new* ListBuffer[B]
>     foreach(f(_).foreach(buf += _))
>     buf.toList
>   }
>
>
>   *final* *override* *def* foreach(f: A => Unit) {
>     *var* these = *this*
>     *while* (!these.isEmpty) {
>       f(these.head)
>       these = these.tail
>     }
>   }
>
>  *final* *override* *def* flatMap[B](f: A => Iterable[B]): List[B] = {
>     *val* b = *new* ListBuffer[B]
>     *var* these = *this*
>     *while* (!these.isEmpty) {
>       *var* those = f(these.head).elements
>       *while* (those.hasNext) {
>         b += those.next
>       }
>       these = these.tail
>     }
>     b.toList
>   }
>

What you may have done is spotted the relationship between map, flatMap
and flatten.

Indeed, from map and flatten, we can obtain flatMap:

scala> def flatMap[A, B](as: List[A], f: A => List[B]) =
List.flatten(as.map(f))
flatMap: [A,B](List[A],(A) => List[B])List[B]

However, it is definitely the case that none of these functions are
equivalent or redundant given the others.

- From a "more category theory point of view", the relationship is between
a functor (map), monad's bind (flatMap) and monad's join (flatten). You
might want to explore this more abstract avenue if your curiosity is
strong enough.

I hope this helps. Please ask if you're still confused.

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

Hey! We had 40,000 lines of C# here yesterday, but now there are 40
lines of... Dear God, what is a catamorphism?"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHiZKHmnpgrYe6r60RAgDpAKCLex6BLMp9JZ6Pr9ZnwUYPlCbtnQCgjx6y
jtHDNl4w/cq41sslC1ePQ6s=
=442O
-----END PGP SIGNATURE-----
Reply | Threaded
Open this post in threaded view
|

Re: List's flatten vs flatMap implementation

James Iry
In reply to this post by Daryoush Mehrtash-2
Daryoush,

flatten, flatMap, and map are all related, something I cover in http://james-iry.blogspot.com/2007/10/monads-are-elephants-part-3.html

I can't think of any particular reason for the implementation choice that was made here.  Given the way List's flatten works, it could be implemented like this

def flatten[B](implicit f : A => Iterable[B]) : List[B] = flatMap(f)


---- Daryoush Mehrtash <[hidden email]> wrote:

> I am trying to understand the implementation difference between List
> class's flatten and flatMap methods.    I can see that flatten uses
> implicit
> function as arguments and flatMap is final method.  Otherwise it seems
> to me that the implementation is the same.    Am I missing something?
>
> Is there a reason why flatMap is not using foreach method?   Here are
> the methods:
>
>  *def* flatten[B](*implicit* f : A => Iterable[B]) : List[B] = {
>     *val* buf = *new* ListBuffer[B]
>     foreach(f(_).foreach(buf += _))
>     buf.toList
>   }
>
>
>   *final* *override* *def* foreach(f: A => Unit) {
>     *var* these = *this*
>     *while* (!these.isEmpty) {
>       f(these.head)
>       these = these.tail
>     }
>   }
>
>  *final* *override* *def* flatMap[B](f: A => Iterable[B]): List[B] = {
>     *val* b = *new* ListBuffer[B]
>     *var* these = *this*
>     *while* (!these.isEmpty) {
>       *var* those = f(these.head).elements
>       *while* (those.hasNext) {
>         b += those.next
>       }
>       these = these.tail
>     }
>     b.toList
>   }
>
> --
> Daryoush
>
> Weblog:  http://perlustration.blogspot.com/
Reply | Threaded
Open this post in threaded view
|

Re: List's flatten vs flatMap implementation

Daryoush Mehrtash-2
In reply to this post by tmorris
- From a "more category theory point of view", the relationship is between
a functor (map), monad's bind (flatMap) and monad's join (flatten). You
might want to explore this more abstract avenue if your curiosity is
strong enough.

I hope this helps. Please ask if you're still confused.


Since you asked :)

I read the "monads are elephant" write ups. I understand that flatmap can be implemented as flatten(map(f)) or map can be implemented as  flatMap {x => unit(f(x))}.  Is that what you mean by "more category theory point of view" or is there more I should look at, if so I would appreciate some references?


As far as implementation is concern, if indeed there are no reason for the different implementation it would be nice if the code can be cleaned up.  I think these classes are valuable source for any new comer, it would be great if they are consistent.


On Jan 12, 2008 8:24 PM, Tony Morris <[hidden email]> wrote:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Daryoush,

Daryoush Mehrtash wrote:
> I am trying to understand the implementation difference between List
> class's flatten and flatMap methods.    I can see that flatten uses
> implicit
> function as arguments and flatMap is final method.  Otherwise it seems
> to me that the implementation is the same.    Am I missing something?
>
> Is there a reason why flatMap is not using foreach method?   Here are
> the methods:

foreach would imply a side-effect, which would definitely not fit in
with flatMap. Perhaps you mean map? In which case, see below.

>
>  *def* flatten[B](*implicit* f : A => Iterable[B]) : List[B] = {
>     *val* buf = *new* ListBuffer[B]

>     foreach(f(_).foreach(buf += _))
>     buf.toList
>   }
>
>
>   *final* *override* *def* foreach(f: A => Unit) {
>     *var* these = *this*
>     *while* (!these.isEmpty) {
>       f(these.head)
>       these = these.tail
>     }
>   }
>
>  *final* *override* *def* flatMap[B](f: A => Iterable[B]): List[B] = {
>     *val* b = *new* ListBuffer[B]
>     *var* these = *this*
>     *while* (!these.isEmpty) {
>       *var* those = f(these.head).elements
>       *while* (those.hasNext) {
>         b += those.next
>       }
>       these = these.tail
>     }
>     b.toList
>   }
>

What you may have done is spotted the relationship between map, flatMap
and flatten.

Indeed, from map and flatten, we can obtain flatMap:

scala> def flatMap[A, B](as: List[A], f: A => List[B]) =
List.flatten(as.map(f))
flatMap: [A,B](List[A],(A) => List[B])List[B]

However, it is definitely the case that none of these functions are
equivalent or redundant given the others.

- From a "more category theory point of view", the relationship is between
a functor (map), monad's bind (flatMap) and monad's join (flatten). You
might want to explore this more abstract avenue if your curiosity is
strong enough.

I hope this helps. Please ask if you're still confused.

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

Hey! We had 40,000 lines of C# here yesterday, but now there are 40
lines of... Dear God, what is a catamorphism?"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHiZKHmnpgrYe6r60RAgDpAKCLex6BLMp9JZ6Pr9ZnwUYPlCbtnQCgjx6y
jtHDNl4w/cq41sslC1ePQ6s=
=442O
-----END PGP SIGNATURE-----



--
Daryoush

Weblog:  http://perlustration.blogspot.com/