This is a fun one :) What's the best (preferably typesafe) way to flatten it to a List[T] 
Let the function called ∘ have the type (A => B) => F[A] => F[B] Let M=List Let F=Function1[T, _] (in which case, function composition) Then the answer to your question is simply: μ∘μ∘μ∘μ ... μ // so on for each level of nesting You asked for the best :) See Scalaz. On 11/09/10 06:11, Kevin Wright wrote:
 Tony Morris http://tmorris.net/ 
What I need is a function that can flatten the List, but doesn't know
in advance how deeply it'll be nested. The same function should be usable for different depths. On Friday, September 10, 2010, Tony Morris <[hidden email]> wrote: > > > > > > > > Let the function called μ have the type M[M[A]] => M[A]. > Let the function called ∘ have the type (A => B) => F[A] => > F[B] > Let M=List > Let F=Function1[T, _] (in which case, function composition) > > Then the answer to your question is simply: > μ∘μ∘μ∘μ ... μ // so on for each level of nesting > > You asked for the best :) See Scalaz. > > On 11/09/10 06:11, Kevin Wright wrote: > > This is a fun one :) > > > Given some nested structure: List[List[...List[T]]] > What's the best (preferably typesafe) way to flatten it to a > List[T] > > > >  > Kevin Wright > > mail / gtalk / msn : [hidden email] > pulse / skype: kev.lee.wright > twitter: @thecoda > > > > > >  > Tony Morris > http://tmorris.net/ > > > > >  Kevin Wright mail / gtalk / msn : [hidden email] pulse / skype: kev.lee.wright twitter: @thecoda 
In reply to this post by Kevin Wright3
So far, I've only been able to make it work with specific inner component types. I still haven't quite figured out how to generalize it to any component type without running into ambiguities in Scala's implicit resolution. As it is, this code only works because scalac just so happens to resolve a very specific sort of implicit ambiguity in favor of the most specific expansion.
trait Expansion[A] { def apply(a: A): List[Int] } implicit object IdExpansion extends Expansion[List[Int]] { def apply(xs: List[Int]) = xs } implicit def deepExpansion[A](implicit sub: Expansion[List[A]]): Expansion[List[List[A]]] = new Expansion[List[List[A]]] { def apply(xs: List[List[A]]) = sub(xs.flatten) } def flatten[A](xs: List[A])(implicit exp: Expansion[A]) = xs flatten exp.apply scala> flatten(List(List(List(1, 2, 3, 4), List(4, 5, 6, 7)), List(List(1, 2, 3, 4), List(0, 9, 8, 7)))) res0: List[Int] = List(1, 2, 3, 4, 4, 5, 6, 7, 1, 2, 3, 4, 0, 9, 8, 7) Daniel On Fri, Sep 10, 2010 at 3:11 PM, Kevin Wright <[hidden email]> wrote:

In reply to this post by Kevin Wright3
Kevin Wright skrev 20100910 22:11:
> This is a fun one :) > > Given some nested structure: List[List[...List[T]]] > What's the best (preferably typesafe) way to flatten it to a List[T] A combination of implicits and default arguments works: case class Flat[T, U](fn : T => List[U]) implicit def recFlattenFn[T, U](implicit f : Flat[T, U] = Flat((l : T) => List(l))) = Flat((l : List[T]) => l.flatMap(f.fn)) def recFlatten[T, U](l : List[T])(implicit f : Flat[List[T], U]) = f.fn(l) Examples: scala> recFlatten(List(1, 2, 3)) res0: List[Int] = List(1, 2, 3) scala> recFlatten(List(List(1, 2, 3), List(4, 5))) res1: List[Int] = List(1, 2, 3, 4, 5) scala> recFlatten(List(List(List(1, 2, 3), List(4, 5)), List(List(6, 7)))) res2: List[Int] = List(1, 2, 3, 4, 5, 6, 7) /Jesper Nordenberg 
On Fri, Sep 10, 2010 at 3:59 PM, Jesper Nordenberg <[hidden email]> wrote:
> A combination of implicits and default arguments works: is there a typo, or is that 2.8+ only? 
With defaults args, it's absolutely 2.8 only!
On 11 September 2010 00:07, Raoul Duke <[hidden email]> wrote:
 Kevin Wright mail / gtalk / msn : [hidden email] pulse / skype: kev.lee.wright twitter: @thecoda 
In reply to this post by Kevin Wright3
Absurdity.
On 11/09/10 08:28, Kevin Wright wrote: > What I need is a function that can flatten the List, but doesn't know > in advance how deeply it'll be nested. The same function should be > usable for different depths. > > On Friday, September 10, 2010, Tony Morris <[hidden email]> wrote: > >> >> >> >> >> >> >> Let the function called μ have the type M[M[A]] => M[A]. >> Let the function called ∘ have the type (A => B) => F[A] => >> F[B] >> Let M=List >> Let F=Function1[T, _] (in which case, function composition) >> >> Then the answer to your question is simply: >> μ∘μ∘μ∘μ ... μ // so on for each level of nesting >> >> You asked for the best :) See Scalaz. >> >> On 11/09/10 06:11, Kevin Wright wrote: >> >> This is a fun one :) >> >> >> Given some nested structure: List[List[...List[T]]] >> What's the best (preferably typesafe) way to flatten it to a >> List[T] >> >> >> >>  >> Kevin Wright >> >> mail / gtalk / msn : [hidden email] >> pulse / skype: kev.lee.wright >> twitter: @thecoda >> >> >> >> >> >>  >> Tony Morris >> http://tmorris.net/ >> >> >> >> >> >> >  Tony Morris http://tmorris.net/ 
On 11 September 2010 00:17, Tony Morris <[hidden email]> wrote: Absurdity. How so? I'll freely concede that nested lists like this are aren't the best way to represent such a data structure. I also have no doubt that such a beast could easily crop up in production code.
But as a puzzler for exploring the (Turing complete) Type system... I think it's perfectly valid.
 Kevin Wright mail / gtalk / msn : [hidden email] pulse / skype: kev.lee.wright twitter: @thecoda 
I'm not sure, but I think "absurdity" was meant to describe the first sentence of your previous post:
> What I need is a function that can flatten the List, but doesn't know > in advance how deeply it'll be nested. That seems contradictory to me. E.g. I can't see how it could work in a type safe way if you passed a List[List[_]] to such a function. However, a single function can handle List[List[Int]] as well as List[List[List[Int]]] types (as you probably know). But those have to be known at compile time, obviously. Still chewing on Jesper's solution :) 
On Fri, Sep 10, 2010 at 4:37 PM, Andreas Flierl <[hidden email]> wrote:
> Still chewing on Jesper's solution :) i realize this is a scala list, but it would be interesting to see other statically typed language answers. like, f# or haskell or *ml. 
In Haskell the μ described earlier is spelled "join" and the ∘ function
is spelled "fmap". Therefore, join `fmap` join `fmap` join ... join On an interesting note, it can be further argued that this repetition can be eschewed by exploiting the join/μ function in another monad. Specifically, the Function1[T, _] monad. Recall μ: M[M[A]] => M[A] Let M=Function1[T, _] Then μ: (T=> T => A) => T => A However, following this further, you end up with nothing better. On 11/09/10 09:43, Raoul Duke wrote: > On Fri, Sep 10, 2010 at 4:37 PM, Andreas Flierl <[hidden email]> wrote: > >> Still chewing on Jesper's solution :) >> > i realize this is a scala list, but it would be interesting to see > other statically typed language answers. like, f# or haskell or *ml. > >  Tony Morris http://tmorris.net/ 
On Fri, Sep 10, 2010 at 4:53 PM, Tony Morris <[hidden email]> wrote:
> Therefore, join `fmap` join `fmap` join ... join who fills in the "..." part? 
I'm guessing "`fmap` join" repeated over and over again, so that the list can be flattened in a typesafe way.
On Fri, Sep 10, 2010 at 7:59 PM, Raoul Duke <[hidden email]> wrote:
 http://erikengbrecht.blogspot.com/ 
In reply to this post by Andreas Flierl
Andreas Flierl skrev 20100911 01:37:
> I'm not sure, but I think "absurdity" was meant to describe the first sentence of your previous post: > >> What I need is a function that can flatten the List, but doesn't know >> in advance how deeply it'll be nested. > > That seems contradictory to me. E.g. I can't see how it could work in a type safe way if you passed a List[List[_]] to such a function. However, a single function can handle List[List[Int]] as well as List[List[List[Int]]] types (as you probably know). But those have to be known at compile time, obviously. > > Still chewing on Jesper's solution :) There's nothing absurd about such a function (as you can see in my solution). You need two overloaded statically evaluated functions which are discriminated by most specialized parameter type, i.e. (not valid Scala code btw :) ): recFlatten(l : List[_]) = l flatMap recFlatten // Specialized for List[_] refFlatten(v : _) = List(v) // Default case for all T != List[_] This is quite trivial to do in C++ (and probably D as well) for example as it supports template function specialization. It's doable with a bit more work in Scala as I've demonstrated. I've yet to find a Haskell solution, but I'm no expert on type classes and type families so I'm not sure it's even possible to do. /Jesper Nordenberg 
Jesper Nordenberg wrote: > This is quite trivial to do in C++ (and probably D as well) for example as it supports template function specialization. It's doable with a bit more work in Scala as I've demonstrated. If I am understanding things right, your solution needs to know the (complete) type of the list at compile time. So this won't work: val x: List[_] = List(List(List(1, 2, 3), List(4, 5, 6)), List(List(7, 8, 9))) val y: List[Int] = recFlatten(x) It needs to know that x is a List[List[List[Int]]]. Luckily, that can be inferred, so this works: val x = List(List(List(1, 2, 3), List(4, 5, 6)), List(List(7, 8, 9))) val y: List[Int] = recFlatten(x) Kevin wanted this: > What I need is a function that can flatten the List, but doesn't know > in advance how deeply it'll be nested. The same function should be > usable for different depths. recFlatten surely needs to know "how deeply it'll be nested" (aka the complete type) "in advance" (at compiletime). That was all I meant to say :) Am I not comprehending something correctly? 
I wrote:
> So this won't work: > > val x: List[_] = List(List(List(1, 2, 3), List(4, 5, 6)), List(List(7, 8, 9))) > val y: List[Int] = recFlatten(x) What I should have written: val x: List[_] = List(List(List(1, 2, 3), List(4, 5, 6)), List(List(7, 8, 9))) val y: List[_] = recFlatten(x) produces y = List(List(List(1, 2, 3), List(4, 5, 6)), List(List(7, 8, 9))) whereas val x: List[List[List[Int]]] = List(List(List(1, 2, 3), List(4, 5, 6)), List(List(7, 8, 9))) val y: List[Int] = recFlatten(x) correctly produces y = List(1, 2, 3, 4, 5, 6, 7, 8, 9) Because it works via the type system, it must know the full type in advance. 
In reply to this post by Andreas Flierl
Andreas Flierl skrev 20100911 15:42:
> > Jesper Nordenberg wrote: >> This is quite trivial to do in C++ (and probably D as well) for example as it supports template function specialization. It's doable with a bit more work in Scala as I've demonstrated. > > If I am understanding things right, your solution needs to know the (complete) type of the list at compile time. Yes, that's how I interpreted Kevin's original request. Thanks to reflection it's also possible to create a dynamic variant, but that's not as challenging. :) /Jesper Nordenberg 
In reply to this post by Erik Engbrecht
On Fri, Sep 10, 2010 at 6:20 PM, Erik Engbrecht
<[hidden email]> wrote: > I'm guessing "`fmap` join" repeated over and over again, so that the list > can be flattened in a typesafe way. but somebody has to manually type that in, to match however many levels of nested lists there are, or something? i seriously assume i'm missing something about how the fmapjoin approach would automatically do the right number of things in the "..." and i wouldn't have to hold its hand? :) 
In reply to this post by Andreas Flierl
Andreas,
The structures rlistDeep and rAStream[Int]( 1 ) (built using the code below) are infinitely deep and typesafe. Tony Morris' solution smoothly extends to flattening them.
trait TreeOfLife { class RSeq[A]( s : Seq[Either[A,RSeq[A]]] )
extends scala.collection.SeqProxy[Either[A,RSeq[A]]] { override def self = s
} def nestIt [A] ( rs : RSeq[A] ) : RSeq[A] = {
new RSeq[A]( rs.map(
{ ( e ) => { Right[A,RSeq[A]]( new RSeq[A]( List( e ) ) ) } }
) )
} // don't tug on this one...! lazy val rlistDeep : RSeq[Int] =
new RSeq[Int]( List( Left( 1 ), Right( nestIt( rlistDeep ) ) ) )
def nestStream [A] ( rs : RSeq[A] ) : RSeq[A] = {
val fn = {
( e ) => {
Right[A,RSeq[A]](
new RSeq[A]( List( e ).toStream )
)
}
} new RSeq[A]( rs map( fn ) )
} // if you want one you can tug on... def rAStream [A] ( seed : A ) = {
lazy val loopStrm : RSeq[A] = new RSeq[A](
(
List( Left( seed ) ).toStream
append
List( Right( nestStream( loopStrm ) ) ).toStream
)
) loopStrm
} }
Best wishes, greg
On Fri, Sep 10, 2010 at 4:37 PM, Andreas Flierl <[hidden email]> wrote: I'm not sure, but I think "absurdity" was meant to describe the first sentence of your previous post:  L.G. Meredith Managing Partner Biosimilarity LLC 7329 39th Ave SW 
Powered by Nabble  Edit this page 