- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
Abstract data types with Scala
Wed, 2010-12-01, 00:28
Hi, and sorry if this question is a trivial one, but i've not yet
managed to solve my problem...
I'm trying to convert to Scala some Haskell code for my functional
programming class. And i've some problem with ADT
Suppose i want to define an ADT Set. A set is either Empty, either
composed of an element and a Set.
Something like that in Haskell :
data Set a = Empty | Set a (Set a)
So, my first guess is to write something like that :
abstract class AbstractSet[T]
case object Empty extends AbstractSet[Nothing]
case class Set[T](e: T, AbstractSet[T]) extends AbstractSet[T]
But it doesn't work... I get type errors with Empty as soon i attempt to
write some functions like add, belongsTo, list2Set ou set2List.
I've found that :
abstract class AbstractSet[T]
case class Empty[T]() extends AbstractSet[T]
case class Set[T](e: T, AbstractSet[T]) extends AbstractSet[T]
works better but i admit i don't understand why i have to create a class
for Empty.
Wed, 2010-12-01, 01:07
#2
Re: Abstract data types with Scala
Le 01/12/10 00:30, Naftoli Gugenheim a écrit :
>> But it doesn't work... I get type errors with Empty as soon i attempt to
>> write some functions like add, belongsTo, list2Set ou set2List.
>
>
> Could you be more specific?
>
Of course:
scala> abstract class AbstractSet[T]
defined class AbstractSet
scala> case object Empty extends AbstractSet[Nothing]
defined module Empty
scala> case class Set[T](e: T, set: AbstractSet[T]) extends AbstractSet[T]
defined class Set
scala> def belongs_to[T](e: T, set: AbstractSet[T]): Boolean = set match {
| case Empty => false
| case Set(e, ens1) => belongs_to(e, ens1)
| }
belongs_to: [T](e: T,set: AbstractSet[T])Boolean
scala> def add[T](e: T, set: AbstractSet[T]) =
| if (belongs_to(e, set)) set else Set(e, set)
add: [T](e: T,set: AbstractSet[T])AbstractSet[T]
So far, so good...
scala> def list2Set[T](l: List[T]): AbstractSet[T] =
| l match {
| case Nil =>
| Empty
| case x::xs =>
| add(x, list2Set(xs))
| }
Bam :
:12: error: type mismatch;
found : Empty.type (with underlying type object Empty)
required: AbstractSet[T]
case Nil => Empty
On Tue, Nov 30, 2010 at 6:28 PM, Eric Jacoboni <eric.jacoboni@gmail.com> wrote:
Could you be more specific?