Quantcast

Simple enough to describe...

classic Classic list List threaded Threaded
28 messages Options
12
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Simple enough to describe...

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


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

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Simple enough to describe...

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

Re: Simple enough to describe...

Daniel Spiewak
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)

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


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Simple enough to describe...

Jesper Nordenberg
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

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Simple enough to describe...

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

Re: Simple enough to describe...

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

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Simple enough to describe...

Tony Morris
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/


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Simple enough to describe...

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

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Simple enough to describe...

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

Re: Simple enough to describe...

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

Re: Simple enough to describe...

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/


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Simple enough to describe...

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

Re: Simple enough to describe...

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

Re: Simple enough to describe...

Jesper Nordenberg
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

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Simple enough to describe...

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

Re: Simple enough to describe...

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.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Simple enough to describe...

Jesper Nordenberg
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


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Simple enough to describe...

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

Re: Simple enough to describe...

Meredith Gregory
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 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

12
Loading...