Prolog
======

1) Note the function append:

append([], X, X).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

Write function mymember(X, Xs) that checks, given an X and a
list Xs, whether Xs contains X. 

a) Write such function as a recursively defined predicate.

b) Write such function using a single call to append.


2) Let a graph be given by a binary edge predicate e that
applies to constants. 

a) Write a predicate

path(Start, NoNodes, End)

that holds if there is a path from Start to End such that,
excluding Start,End, the path does not pass through any of
the graph nodes in NoNodes list. Assume that the predicate
is called with all variables bound to known values. The
predicate should succeed even if the graph given by e has
cycles. You are allowed to use negation and assume that it
behaves according to its logical meaning.

b) Re-express the previous solution in Scala. Given a Scala type 

type Node = Symbol
type Graph = List[(Node,Node)]

and a value declared by

val e : Graph = ...

write a Scala function of signature

def path(start: Node, noNodes : List[Node], end : Node) : Boolean

that corresponds to the Prolog predicate from the previous
part.

Non-determinism, proofs, and monads
===================================

3) We model non-deterministic imperative computation with
state S as the type.

type N[S] = S => Stream[S]

Complete the following worksheet definitions.  

Define function that either doubles or triples its argument.

def doubleOrTriple : N[Int] = ???

Define function that either adds a or b to the state.

  def addOneOf(a : Int, b : Int) : N[Int] = ???

compose(f,g) composes two non-deterministic computations,
running first f, then g. The function should be associative.

def compose[S](f : N[S], g : N[S]): N[S] = ???

Prove that your compose is associative.

Identity should be a computation that does nothing.
When composed with any function from left or right,
it should give back the same function.

def id[S]: N[S] = ???

We can put non-deterministic computations in a list.

  type Actions[S] = List[N[S]]
  
composeAll should compose all functions in a given list,
applying the functions at the beginning of the list first.

def composeAll[S](as : Actions[S]) : N[S] = ???

runAll should run all actions in a given action list,
starting from the first action.

def runAll[S](as : Actions[S], on : S) : Stream[S] = ???


Here is an example list of actions.
 
  val actions : List[N[Int]] =
    List(addOneOf(5, 20), doubleOrTriple, addOneOf(0, 100))

Here is how you can run it and get it all displayed:
  
  runAll(actions, 1).toList