Simple enough to describe...

[Kevin Wright-3]

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]

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

[Kevin Wright-3]

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

[Daniel Spiewak]

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:

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

[Jesper Nordenberg]

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

[Raoul Duke]

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 Wright-3]

With defaults args, it's absolutely 2.8 only!

On 11 September 2010 00:07, Raoul Duke <[hidden email]> 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 Wright

mail / gtalk / msn : [hidden email]

pulse / skype: kev.lee.wright
twitter: @thecoda

[Tony Morris]

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/

[Kevin Wright-3]

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.

 

 

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 Wright

mail / gtalk / msn : [hidden email]

pulse / skype: kev.lee.wright
twitter: @thecoda

[Andreas Flierl]

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 :)

[Raoul Duke]

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]

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/

[Raoul Duke]

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?

[Erik Engbrecht]

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 <[hidden email]> 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/

[Jesper Nordenberg]

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

[Andreas Flierl]

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?

[Andreas Flierl]

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.

[Jesper Nordenberg]

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

[Raoul Duke]

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? :-)

[Meredith Gregory]

Andreas,

The structures rlistDeep and rAStream[Int]( 1 ) (built using the code below) are infinitely deep and type-safe. 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:

> 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 :)

--
L.G. Meredith
Managing Partner
Biosimilarity LLC
7329 39th Ave SW

Seattle, WA 98136

+1 206.650.3740

http://biosimilarity.blogspot.com