# Semester 2 Week 1 (Defining your own recursive data structures (Lists))

1. Watch video about Week 8 number 1

2. Type in some simple expressions at the Hope prompt >: like:

```(1,2);
(1,'a');
[1,2];
[1,2,1];
[1+1,1,1];
"dog";
[[1,2],[1],[3]];
```

Notice the types of the results.

3. Make up expressions of type:
```num
char
list(num)
list(char)
list(list(char))
num X char
num X char X num
```

4. Try out the length function in Hope on igor: Create a file in your home directory called ggg.hop containing:

```length: list(alpha) -> num;   ! length is a function which take a list and returns a number

length(nil) <= 0;             !the length of the empty list is zero
length(x::m) <= 1+length(m);  ! length of the list whose head is x and tail is m
! is one more than the length of m

length [1,2,3,1];
```

Then type

```hope -f ggg.hop
```

This will output

```>> 4 : num
```

because that is the length of the list [1,2,3,1]. Use hope to work out the length of the following lists:

```[1,1,1,1,1]
['a','b']
["hello","goodbye"]
[[],[1],[1],[1]];
```

What is the type of each of the four lists above?

5. Watch video about Week 8 number 2
6. Watch video about Week 8 number 3

7. Copy the Java Programs in week8 on to your machine. Compile them and run test. Change test.java to print out some different lists.

```public abstract class seblist  <T>
{
public  abstract boolean isnil();

public String toString()
{
return "[" + commasBetween() + "]";

}

public abstract String commasBetween();

}

public class sebnil <T> extends seblist <T>
{

public boolean isnil()
{return true;
}

public String commasBetween()
{ return "";}

}

public class sebcons <T> extends seblist <T>
{
T h;
seblist <T> t;

public sebcons(T o1, seblist  <T> m1)
{h=o1;t=m1;}

public boolean isnil()
{return false;}

public String commasBetween()
{ if (t.isnil()) return h.toString();
else return h.toString() +","+ t.commasBetween();}

}

class test
{

public static void main (String []args)
{

System.out.println(new sebcons(1,new sebcons(2,new sebnil())));

}

}
```

8. Add the length method to seblist. You will have to add an abstract method int length() to seblist and a method int length() in sebnil and sebcons classes.
9. Write a program for testing your length method.

10. Define head and tail methods.
11. Try the Hope function for appending two lists:
```append: list(alpha) X list(alpha) -> list(alpha);
append (nil,m) <=  m;
append (x::k,m) <= x::append(k,m);
```

12. Try the Hope function elementAt:
```elementAt: list(alpha) X num -> alpha;
elementAt(0,x::m) <= x;
elementAt(n+1,x::m) <= elementAt(n,m);
```

1. Add the seblist append(seblist m) method to seblist. You will have to add an abstract method seblist append(seblist m) to seblist and a method seblist append(seblist m) in sebnil and sebcons classes.

2. Add the Object elementAt(int n) method to seblist. You will have to add an abstract method Object elementAt(int n) to seblist and a method Object elementAt(int n) in sebnil and sebcons classes.

3. Write a program for testing your append method.

Solutions

13. (Easy Assignment) Add the following method to your generic lists classes:
```reverse:list(alpha) -> list(alpha);
reverse(nil) <= nil;
reverse(x::m) <= append(reverse(m),x::nil);
```

14. (Hard Assignment) Implement the following in Java as static methods:

```type string ==list(char);

insert: string # list(string) -> list(string);
insert (s,nil) <= s::nil;
insert (s,y::m) <= if (s<y)
then s::(y::m)
else y::insert(s,m);

sort: list(string) -> list(string);
sort(nil) <= nil;
sort(x::m) <= insert(x,sort(m));
```

Hint:

```static seblist <String> insert (String x, seblist <String> m)

static seblist <String> sort (seblist <String> m)
```
s.danicic@gold.ac.uk
Sebastian Danicic BSc MSc PhD (Reader in Computer Science)
Dept of Computing, Goldsmiths, University of London, London SE14 6NW
Last updated 2015-09-04