# Simple enough to describe...

28 messages
12
Open this post in threaded view
|
Report Content as Inappropriate

## Simple enough to describe...

 This is a fun one :)Given some nested structure: List[List[...List[T]]]What's the best (preferably type-safe) way to flatten it to a List[T]-- Kevin Wright mail / gtalk / msn : [hidden email]pulse / skype: kev.lee.wrighttwitter: @thecoda
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 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 type-safe) 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/ ```
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 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 type-safe) 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
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 In reply to this post by Kevin Wright-3 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)DanielOn Fri, Sep 10, 2010 at 3:11 PM, Kevin Wright wrote: This is a fun one :)Given some nested structure: List[List[...List[T]]]What's the best (preferably type-safe) way to flatten it to a List[T] -- Kevin Wright mail / gtalk / msn : [hidden email]pulse / skype: kev.lee.wrighttwitter: @thecoda
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 In reply to this post by Kevin Wright-3 Kevin Wright skrev 2010-09-10 22:11: > This is a fun one :) > > Given some nested structure: List[List[...List[T]]] > What's the best (preferably type-safe) 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
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 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?
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 With defaults args, it's absolutely 2.8 only!On 11 September 2010 00:07, Raoul Duke wrote: 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? -- Kevin Wrightmail / gtalk / msn : [hidden email]pulse / skype: kev.lee.wrighttwitter: @thecoda
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 In reply to this post by Kevin Wright-3 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 type-safe) 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/
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 On 11 September 2010 00:17, Tony Morris 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.    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 type-safe) 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/ -- Kevin Wrightmail / gtalk / msn : [hidden email]pulse / skype: kev.lee.wright twitter: @thecoda
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 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 :)
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 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.
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 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/
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 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?
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 I'm guessing "`fmap` join" repeated over and over again, so that the list can be flattened in a type-safe way.On Fri, Sep 10, 2010 at 7:59 PM, Raoul Duke wrote: 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? -- http://erikengbrecht.blogspot.com/
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 In reply to this post by Andreas Flierl Andreas Flierl skrev 2010-09-11 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
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 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 compile-time). That was all I meant to say :) Am I not comprehending something correctly?
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 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.
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 In reply to this post by Andreas Flierl Andreas Flierl skrev 2010-09-11 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
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Simple enough to describe...

 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 type-safe 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 fmap-join approach would automatically do the right number of things in the "..." and i wouldn't have to hold its hand? :-)