- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
Nested list structures
Wed, 2009-04-01, 21:52
Hi!
When I tried to solve the following exercise from
http://aperiodic.net/phil/scala/s-99/
P07 (**) Flatten a nested list structure.
Example:
scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8)
it bothered me that this "nested list structure" is not really type safe,
and I thought about how to fix this. As I am better in stealing than
thinking, I started to disembowel Scalas regular List, and came up with this
skeleton:
sealed abstract class NestedList[+T] {
val isEmpty: Boolean
def head: Either[T, NestedList[T]]
def tail:NestedList[T]
def #:[U >: T] (u: U): NestedList[U] = new #:(u, this)
def #:[U >: T](ul: NestedList[U]): NestedList[U] = new #:(ul, this)
}
case object NestedNil extends NestedList[Nothing] {
override val isEmpty = true
def head: Either[Nothing, NestedList[Nothing]] = throw new
NoSuchElementException("head of empty list")
def tail: NestedList[Nothing] = throw new NoSuchElementException("tail of
empty list")
}
final case class #:[T](private var hd: Either[T, NestedList[T]], private var
tl: NestedList[T]) extends NestedList[T] {
override val isEmpty: Boolean = false
def this(hd:T, tl: NestedList[T]) = this(Left(hd), tl)
def this(hd: NestedList[T],tl: NestedList[T]) = this(Right(hd), tl)
def head : Either[T, NestedList[T]] = hd
def tail : NestedList[T] = tl
}
Now I can write:
def flatten[T](list:NestedList[T]):List[T] = list match {
case NestedNil => Nil
case Right(NestedNil) #: tail => flatten(tail)
case Right(head) #: tail => flatten(head) ::: flatten(tail)
case Left(head) #: tail => head :: flatten(tail)
}
Do you think this structure could be useful in the real world (of course
with some edges smoothed)?
BTW, I tried to introduce this:
type Nested[T] = Either[T, NestedList[T]]
but couldn't figure out how to get it working...
Cheers,
Daniel
Wed, 2009-04-01, 22:27
#2
Re: Nested list structures
Sorry, something like that does not work, but the following probably yest
case class NL[+T](val v : Either[List[NL[T]],T])
It is a bit more contrived, but not much.
On 4/1/09, Christian Szegedy wrote:
> You probably wanted this:
>
> type NestedList = Either(List[NestedList[T]],T)
>
>
> On 4/1/09, Landei wrote:
> >
> > BTW, I tried to introduce this:
> >
> > type Nested[T] = Either[T, NestedList[T]]
> >
> > but couldn't figure out how to get it working...
> >
> > Cheers,
> > Daniel
> >
> > --
> > View this message in context: http://www.nabble.com/Nested-list-structures-tp22834757p22834757.html
> > Sent from the Scala - User mailing list archive at Nabble.com.
> >
> >
>
Thu, 2009-04-02, 13:07
#3
Re: Nested list structures
Landei wrote:
> Hi!
>
> When I tried to solve the following exercise from
> http://aperiodic.net/phil/scala/s-99/
>
> P07 (**) Flatten a nested list structure.
> Example:
> scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
> res0: List[Any] = List(1, 1, 2, 3, 5, 8)
>
> it bothered me that this "nested list structure" is not really type safe,
Instead of using Either, you could use implicit conversions.
trait Flattenable[T] {
def toFlatList: List[T]
}
object Flattenable {
implicit def list2flattenable[T <% Flattenable[T]](list:
List[Flattenable[T]]): Flattenable[T] = new Flattenable[T] {
def toFlatList: List[T] = list.flatMap(_.toFlatList)
}
implicit def element2flattenable[T](element: T): Flattenable[T] =
new Flattenable[T] {
def toFlatList: List[T] = List(element)
}
def flatten[T](list: Flattenable[T]): List[T] = list.toFlatList
}
import Flattenable._
val list: Flattenable[Int] =
List(List(1, 1), 2, List(3, List(5, 8)))
println(flatten(list))
Fri, 2009-04-03, 14:57
#4
Re: Nested list structures
Hi!
Thanks for all suggestions!
type Nested[+T] = Either[T, NestedList[T]]
...did the trick (the + was missing)! It's cool what you can do with
implicits, but this looks a little bit too "magic" to me. I guess an
implicit conversion from List to NestedList wouldn't hurt, though.
Cheers,
Daniel
You probably wanted this:
type NestedList = Either(List[NestedList[T]],T)
On 4/1/09, Landei wrote:
>
> BTW, I tried to introduce this:
>
> type Nested[T] = Either[T, NestedList[T]]
>
> but couldn't figure out how to get it working...
>
> Cheers,
> Daniel
>
> --
> View this message in context: http://www.nabble.com/Nested-list-structures-tp22834757p22834757.html
> Sent from the Scala - User mailing list archive at Nabble.com.
>
>