This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Abstract data types with Scala

2 replies
jaco60
Joined: 2010-11-10,
User offline. Last seen 1 year 48 weeks ago.

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.

Naftoli Gugenheim
Joined: 2008-12-17,
User offline. Last seen 42 years 45 weeks ago.
Re: Abstract data types with Scala


On Tue, Nov 30, 2010 at 6:28 PM, Eric Jacoboni <eric [dot] jacoboni [at] gmail [dot] com> wrote:
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?
jaco60
Joined: 2010-11-10,
User offline. Last seen 1 year 48 weeks ago.
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

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland