Work samples

Either.java

package functionaljava.Data;

import functionaljava.Data.List;

import java.util.function.*;

abstract interface Either<A, B> {

	abstract <T> T foldEither(final Function<? super A, ? extends T> f, Function<? super B,? extends T> g);
	abstract List<Either<A, B>> lefts(List<Either<A, B>> xs);
	abstract List<Either<A, B>> rights(List<Either<A, B>> xs);
	abstract Boolean isLeft(Either<A, B> v);
	abstract Boolean isRight(Either<A, B> v);
	abstract Either<A, B> pi(Either<A, B> v);
	
	default Pair<List<Either<A, B>>, List<Either<A, B>>>
		partitionEither(List<Either<A, B>> xs) {
			return new Pair<List<Either<A, B>>, List<Either<A, B>>>
			(lefts(xs), rights(xs));
	}
}

final class Left<A, B> implements Either<A, B> {
	private final A a;
	
	public Left(A a) {
		this.a = a;
	}

	/**
	 * Standard Either fold. If case of Left, fold through f, else g.
	 * Applies to contained value.
	 * @param f - function f :: A -> T applying to this value if case of Left
	 * @param g - function g :: B -> T applying to this value if case of Right
	 * @param <T> - Target return type
	 * @return f(a)||g(a)
	 */
	public <T> T foldEither(Function<? super A, ? extends T> f,
			Function<? super B, ? extends T> g) {
		return f.apply(a);
	}

	/**
	 * From a list of Eithers, get instances of Left and concat them.
	 * @param xs - incoming list
	 * @return new list of all Lefts in xs
	 */
	public List<Either<A, B>> lefts(List<Either<A, B>> xs) {
        return xs.filter(x -> isLeft(x));
    }

	/**
	 * Same as Lefts, but instead, all instances of Right
	 */
	public List<Either<A, B>> rights(List<Either<A, B>> xs) {
		return xs.filter((x -> isRight(x)));
	}

	public Boolean isLeft(Either<A, B> v) {
		return true;
	}

	public Boolean isRight(Either<A, B> v) {
		return false;
	}

	/**
	 * Accesses the value of the Either passed
	 * @param v instance of Either
	 * @return this internal value if instance of Left. Otherwise, right
	 */
	public A fromLeft(Either<A, B> v) {
		return this.a;
	}

	/**
	 * Projects left portion of the given Either
	 * @param v instance of Either
	 * @return this
	 */
	public Left<A, B> pi(Either<A, B> v) {
		return this;
	}
}

final class Right<A, B> implements Either<A, B> {
	private final B b;
	
	public Right(B b) {
		this.b = b;
	}
	public <T> T foldEither(Function<? super A, ? extends T> f,
			Function<? super B, ? extends T> g) {
		return g.apply(b);
	}

	public List<Either<A, B>> lefts(List<Either<A, B>> xs) {
		return xs.filter(x -> isLeft(x));
	}

	public List<Either<A, B>> rights(List<Either<A, B>> xs) {
		return xs.filter(x -> isRight(x));
    }

	public Boolean isLeft(Either<A, B> v) {
		return false;
	}

	public Boolean isRight(Either<A, B> v) {
		return true;
	}

	public Either<A, B> pi(Either<A, B> v) {
		return this;
	}
	
	public B fromRight(Either<A, B> v) {
		return this.b;
	}
}

F.java

package functionaljava.Function;

/**
 * Created by Emily on 2/18/2015.
 */
 
public interface F<A> {
  A apply();
}

//TODO: Functions of arity 2-7

F1.java

package functionaljava.Function;

/**
 * Created by emily on 5/14/2015.
 */
public interface F1<A, B> {
    B apply(A a);

    /**
     * Given a function f ::  -> A, we compose this with g :: A -> B.
     * Left composition with - (g o f) :: A -> C : x -> g(f(x))
     */
    default <E> F1<E, B> o(final F1<? super E, ? extends A> f) {
        return (e) -> apply(f.apply(e));
    }

    /**
     * Given a function f :: A -> B, we take a function p :: B -> E and precompose p with f.
     * Right composition with - (p o f) :: A -> E : x -> p(f(x))
     * @param p :: B -> A.
     */
    default <E> F1<A, E> andThen(final F1<? super B, ? extends E> p) {
        return (A a) -> p.apply(apply(a));
    }

    /**
     * Identity function wrapper
     * @return whatever it is that is passed
     */
    default <A> F1<A, A> id() {
        return a -> a;
    }
}

F2.java

package functionaljava.Function;

import functionaljava.Data.Pair;

/**
 * Created by emily on 5/14/2015.
 */

public interface F2<A, B, C> {
    C apply(A a, B b);

    default <T> F2<A, B, T> andThen(final F1<? super C, ? extends T> f) {
        return (a, b) -> f.apply(apply(a, b));
    }
}

F3.java

package functionaljava.Function;

public interface F3<A, B, C, T> {
	T apply(final A a, final B b, final C c);

	default <V> F3<A, B, C, V>
        	andThen(final F1<? super T, ? extends V> after) {
            		return (A a, B b, C c) -> after.apply(apply(a, b, c));
		}
	}

List.java

package functionaljava.Data;

import functionaljava.Function.*;


/**
 * @Author Emily Pillmore
 * Algebraic Data types continued: List ADT
 * Its fold signature is as follows:
 * 
 * b -> (a -> b -> b) -> list a -> b
 * 
 * Thus, our foldR method will look like:
 * foldR: B x (f :: AxB -> B) x List[A] -> B
 *
 * Remember - when using instanceof, since Java's type-parametrization utilizes the same runtime class,
 * we do not need to type our inputs to instanceof.
 *
 *
 * @Todo: foldL, traversal.
 * This is a  java implementation of the following skeleton in Scala
 * 

abstract sealed trait List[A] {
  def foldR[B](f:(A, B) => B)(z: B): B
}

case class Cons[A](t: A, h: List[A]) extends List[A] {
  def foldR[B](f:(A, B) => B)(z: B): B = {
    return f.apply(this.t, this.h.foldR(f)(z))
  }
}

case object Empty extends List[Nothing] {
  def foldR[B](f:(Nothing, B) => B)(z: B): B = {
    return z;
  }
}
*/
abstract class List<A> {

    abstract <B> B foldr(final F2<A, B, B> f, final B v);
    abstract List<A> append(List<A> ys);
    abstract <B> List<B> map(final F1<A, B> f);
    abstract List<A> filter(final Predicate<A> p);
    abstract A head();
    abstract List<A> tail();
    abstract Integer length();
    abstract Boolean isSingleton();
    abstract List<A> singleton(A a);
    abstract List<A> init();
    abstract List<A> traverse(A v);
}

/**
 * Case class Cons constructs a copy of the list with element a and internal copy of previous list t
 * In haskell, Cons is the infix operator (:)
 *
 */
final class Cons<A> extends List<A> {
    private final A a;
    private final List<A> t;

    public Cons(A a, List<A> t) {
        this.a = a;
        this.t = t;
    }

    /**
     * Put v in B and let f :: AxB -> B - then, our list Catamorphism ((|f, v|) = foldr) :: List A -> B
     * is a function defined by the following schema:
     * foldr Nil _           = _
     * foldr f v Cons(a, xs) = f a (foldr f v xs)
     *
     * Our v, in this case, is a least fixed set - a fixed point w.r.t the initial F-algebra under the functor f.
     * @param f :: AxB -> B
     * @param v :: fixed point under f
     * @return B which is the collapse of the list under f, or the fixed point v if Nil
     */
    <B> B foldr(F2<A, B, B> f, B v) {
        return f.apply(this.a, this.t.foldr(f, v));
    }

    /**
     * Implementation of Map as a catamorphism over List a
     * Map applies f to each a and through this Cons' copy of the list
     * @param f :: A -> B  applied to each a in this copy of the list
     * @return new list of type B
     */
    <B> List<B> map(F1<A, B> f) {
        return new Cons<B>(f.apply(a), this.t.map(f));
    }

    /**
     * Filter is a fold which takes a Predicate p as an argument and constructs a list
     * dependent upon whether p |- T v F.
     *
     * Effectively, filter p = foldr (λx xs → if p x then x : xs else xs) [ ]
     * @param p the predicate in question. p :: A -> Boolean
     * @return New list constructed of a in xs such that p(a) |- T or Nil if instance of Nil
     *
     */
    List<A> filter(Predicate<A> p) {
        return p.model(this.a) ? new Cons<A>(this.a, this.t.filter(p)) : this.t.filter(p);
    }

    /**
     * Head returns the first element in the list
     * @return this a if instanceof Cons, or throw new RuntimeException if instanceof Nil
     */
    A head() {
        return this.a;
    }

    /**
     * Get all but the first in the list
     *
     * @return this copy of list (t) if instanceof Cons or throw new RuntimeException if Nil
     */
    List<A> tail() {
        return this.t;
    }

    /**
     * Gets number of elements in the list. Counts using the lambda (z, n) -> n + 1
     * foreach Cons containing a z. Folds using 0 as fixed point under (+)
     *
     * @return integer representing the number of elements in the list.
     */
    Integer length() {
        return foldr((k, n) -> n + 1, 0);
    }

    /**
     * Models T v F if this t is Nil - T if true.
     * @return T v F
     */
    Boolean isSingleton() {
        return this.t instanceof Nil;
    }

    /**
     * Constructs singleton from a by assigning new Nil
     * @param a element to Cons
     * @return new singleton by Consing a, new Nil
     */
    List<A> singleton(A a) {
        return new Cons<A>(a, new Nil<A>());
    }

    /**
     * Get all but the last element in xs testing using isSingleton
     * @return all but last element testing if singleton and return Nil, or fold through t
     *
     */
    List<A> init() {
        return this.isSingleton() ? new Nil<A>() : new Cons<A>(this.a, this.t.init());
    }
    
    /**
     * Return copy of list ending in given value by using the prediate v == this a. Anamorphism
     * 
     * @param v - item to filter by
     * @return list ending in v
     */ 
    List<A> traverse(A v) {
    	return v == this.a ? this.t : this.t.traverse(v);
    }

    /**
     * Concatenates two lists a la ys : xs :: (\x y -> y:x)
     * @param ys - list to concat
     * @return new list as = ys : xs
     */
    List<A> append(List<A> ys) {
        return ys instanceof Nil ? this : new Cons(ys.head(), this.append(ys.tail()));
    }

}

final class Nil<A> extends List<A> {

    <B> B foldr(final F2<A, B, B> f, B x) {
        return x;
    }

    <B> List<B> map(F1<A, B> f) {
	return new Nil<B>();
    }
	
    List<A> filter(Predicate<A> p) {
	return this;
    }
	
    Integer length() {
	return 0;
    }

    A head() {
        throw new RuntimeException();
    }

    List<A> tail() {
        throw new RuntimeException();
    }

    Boolean isSingleton() {
        return false;
    }

    List<A> singleton(A a) {
        return new Cons<A>(a, this);
    }
    
    List<A> init() {
        throw new RuntimeException();
    }
    
    List<A> traverse(A v) {
    	throw new RuntimeException();
    }

    List<A> append(List<A> ys) { return ys; }
}

Maybe.java

package functionaljava.Data;

import functionaljava.Function.F1;

/**
 * 
 * @author Emily Pillmore
 *
 * General implementation of the Maybe datatype from Haskell.
 * 
 * Maybe represents an optional type which could be a null or a non-null value
 * taking the form data Maybe a = Nothing | Just a
 * 
 * It's fold is of the type (a -> b) -> b -> Maybe a -> b
 * 
 * Along with its fold are implementations of the standard methods given in the Haskell
 * library Data.Maybe.
 */
abstract class Maybe<A> {
	
	abstract <B> B foldMaybe(final F1<A, B> f, final B v);
	abstract Boolean isJust(final Maybe<A> v);
	abstract Boolean isNothing(final Maybe<A> v);
	abstract A fromJust(final Maybe<A> v);
	abstract A fromMaybe(final Maybe<A> m, final A v);
	abstract Maybe<A> listToMaybe(final List<A> xs);
    abstract List<Maybe<A>> maybeToList(final Maybe<A> v);
    abstract List<A> catMaybes(final List<Maybe<A>> xs);

}

final class Just<A> extends Maybe<A> {
	private final A a;
	
	public Just(A a) {
		this.a = a;
	}
	
	/**
	 * Standard fold with type signature (a -> b) -> b -> Maybe a -> b).
	 * Fold takes a function f :: A -> B and a default value b 
	 * of type B, and applies f to the value in Maybe in the case that 
	 * Maybe is Just and returns the default value b if Maybe is Nothing.
	 */
	public <B> B foldMaybe(F1<A, B> f, B b) {
		return f.apply(a);
	}
	
	public Boolean isJust(Maybe<A> v) {
		return true;
	}
	
	public Boolean isNothing(Maybe<A> v) {
		return false;
	}

	/**
	 * @param v - the value from which we extract Just a in the case
	 * that v is Just and throwing an error if it is Nothing.
	 */
	public A fromJust(Maybe<A> v) {
		return this.a;
	}

	/**
	 * Extract Just a in the case that m is Just a and returning the default
	 * value v in the case that it is Nothing
	 * @Param Maybe m, A v
	 */
	public A fromMaybe(Maybe<A> m, A v) {
		return this.a;
	}

	/**
	 * @param xs - the list from which we extract the first case of
	 * Maybe and return Just in the case that xs contains Just a.
	 */
	public Maybe<A> listToMaybe(List<A> xs) {
		return this;
	}

	/**
	 * @param v - the value from which we create a singleton
	 * using the list constructor Cons with parameters a and setting its copy to Nil
	 */
    public List<Maybe<A>> maybeToList(Maybe<A> v) {
        return new Cons<Maybe<A>>(v, new Nil<Maybe<A>>());
    }

	/**
	 * Creates a list of type a from a list of Maybe a's, effectively reducing 
	 * a list to its non-null values. 
	 * @param xs - the list of Maybe a's to reduce to a list of a's
	 */
	public List<A> catMaybes(List<Maybe<A>> xs) {
        return xs.filter(x -> x instanceof Just).map(x -> x.fromJust(x));
    }
}
final class Nothing<A> extends Maybe<A> {
	public Nothing() {}
	
	public <B> B foldMaybe(F1<A, B> f, B b) {
		return b;
	}

	public Boolean isJust(Maybe<A> v) {
		return false;
	}
	
	public Boolean isNothing(Maybe<A> v) {
		return true;
	}

	public A fromJust(Maybe<A> v) {
		throw new RuntimeException();
	}

	public A fromMaybe(Maybe<A> m, A v) {
		return v;
	}

	public Maybe<A> listToMaybe(List<A> xs) {
		return this;
	}

    public List<Maybe<A>> maybeToList(Maybe<A> v) {
        return new Nil<Maybe<A>>();
    }

	public List<A> catMaybes(List<Maybe<A>> xs) {
        return new Nil<A>();
    }
}

Nat.java

package functionaljava.Data;

import functionaljava.Function.F1;

import java.util.function.Function;
/**
 * Nat :: (Nat -> a) -> a -> Nat -> a
 * 
 */
abstract class Nat {

    abstract <A> A fold(final F1<A, A> f, final A z);
    abstract Boolean isZero(Nat m);
    abstract Boolean isSucc(Nat m);
    abstract Nat add(Nat m);
    abstract Nat minus(Nat m);
    abstract Nat mult(Nat m);
    abstract Integer toNum();
    abstract Nat Max(Nat n);
    abstract Nat Fib();
    abstract Nat Fac();
}

final class Z extends Nat {
    public Z() {}

    public <A> A fold(F1<A, A> f, A v) {
        return v;
    }

    public Boolean isZero(Nat n) {
        return true;
    }

    public Boolean isSucc(Nat n) {
        return false;
    }

    public Nat add(Nat m) {
        return m;
    }

    public Nat minus(Nat m) { return this; }

    public Nat mult(Nat m) {
        return this;
    }

    public Integer toNum() {
        return 0;
    }
    
    public Nat Max(Nat n) {
        return n;
    }

    public Nat Fib() { return this; }

    public Nat Fac() { return new S(this); }
}

final class S extends Nat {
    private final Nat a;

    public S(Nat a) {
        this.a = a;
    }

    public <A> A fold(F1<A, A> f, A v) {
        return f.apply(this.a.fold(f, v));
    }

    public Boolean isZero(Nat n) {
        return false;
    }

    public Boolean isSucc(Nat n) {
        return true;
    }

    public Nat add(Nat m) {
        F1<Nat, Nat> f = (x) -> new S(this.a.add(x));
        return fold(f, m);
    }

    public Nat minus(Nat m) {
        return m instanceof Z ? this
                : this.a.Max(m) == m
                ? m.minus(this.a)
                : this.a.minus(m);
    }
    public Nat mult(Nat m) {
        Z z = new Z();
        F1<Nat, Nat> f = (x) -> x.add(this.a.mult(x));
        return fold(f, new S(z));
    }

    public Integer toNum() {
        return 1 + this.a.toNum();
    }
    
    public Nat Max(Nat n) {
        return n.toNum() < this.a.toNum() ? this.a : n;
    }

    public Nat Fib() {
        Nat one = new S(new Z());
        return this == new S(new Z()) ? this :
                this.a.minus(one).Fib().add(this.a.minus(new S(one)).Fib());
    }

    public Nat Fac() {
        return this == new S(new Z()) ? this
                : this.a.mult(this.a.minus(new S(new Z())).Fac());
    }

}

Predicate.java

package functionaljava.Function;

/**
 * @Author Emily Pillmore - draws heavily from Guava and Java8 models
 *
 * Predicates are many things - The precise semantic interpretation of an atomic formula and an atomic sentence
 * will vary from theory to theory.
 *
 *  - In propositional logic, atomic formulas are called propositional variables. In a sense, these are nullary (i.e. 0-arity) predicates.
 *  - In first-order logic, an atomic formula consists of a predicate symbol applied to an appropriate number of terms.
 *  - In set theory, predicates are understood to be characteristic functions or set indicator functions, i.e. functions from a set element to a truth value. Set-builder notation makes use of predicates to define sets.
 *  - In Model theory, predicates are understood to be well-formed formulas that effectively model True or False only if they are valid
 *    formulas in some countable model.
 *
 * We use the last as our definition to model our own predicates.
 */
public interface Predicate<A> {
  /**
   * Effectively (|-) :: A -> Boolean
   * @param a bound variable
   * @return T v F
   */
  boolean model(final A a);

  /**
   * Returns new predicate that is the conjunction of p and q. I.E. p.and(q) is isomorphic to p ^ q
   * The validity of and is gauranteed by the definition of wff's in this model
   *
   * @param q - predicate to conjoin
   * @return new predicate r = p ^ q
   */
  default Predicate<A> and(final Predicate<? super A> q) {
    return (a) -> model(a) && q.model(a);
  }

  /**
   * Isomorphic to the disjunction of p and q. I.E. p.or(q) is isomorphic to p v q
   *
   * @param q predicate to disjoin
   * @return new predicate r = p v q
   */
  default Predicate<A> or(final Predicate<? super A> q) {
    return (a) -> model(a) || q.model(a);
  }

  /**
   * The negation of a given predicate
   * @return ~this
   */
  default Predicate<A> not() {
    return a -> !model(a);
  }

  /**
   * Tests the equality of two elements
   *
   * @param a element to test equality against
   * @return equality testing predicate
   */
  default Predicate<A> isEqual(final A a) {
    return b -> a.equals(b);
  }

  /**
   * Wraps true in a predicate
   * @return predicate modelling true
   */
  default Predicate<A> True() {
    return a -> true;
  }

  /**
   * Wraps false in a predicate
   * @return predicate modelling false
   */
  default Predicate<A> False() {
    return a -> false;
  }
}

Tree.java

package functionaljava.Data;
import functionaljava.Function.*;

/**
 * Abstract Data types continued: Binary Tree ADT
 * Its fold signature is as follows:
 *
 * a -> (a -> b -> b -> b) -> Tree a -> b
 *
 * Thus, our fold method will look like:
 * foldR :: A x (f :: AxBxB -> B) x Tree[A] -> B
 *
 * todo: foldL, maps, traversal.
 * This is a  java implementation of the following ADT in Scala
 *

abstract sealed trait Tree[A] {
  def foldR[B](z: B)(f: (A, B, B) => B): B
}

case class Tip[A]() extends Tree[A] {
  def foldR[B](z: B)(f: (A, B, B) => B): B = {
    return z;
  }
}

case class Branch[A](t: A, l: Tree[A], r: Tree[A]) extends Tree[A] {
  def foldR[B](z: B)(f: (A, B, B) => B): B = {
    return f.apply(this.t, this.l.foldR(z)(f), this.r.foldR(z)(f))
  }
}
*/
abstract class Tree<A> {
	abstract <B> B fold(final F3<A, B, B, B> f, final B v);
	abstract <B> Tree<B> map(final F1<A, B> f);
	abstract Tree<A> filter(final F1<A, Boolean> p);
    	abstract Nat depth(Tree<A> t);

}

final class Branch<A> extends Tree<A> {

	private final A a;
	private final Tree<A> l,r;

	public Branch (A a, Tree<A> l,  Tree<A> r) {
		this.l = l;
		this.a = a;
		this.r = r;
	}

	<B> B fold(F3<A, B, B, B> f, B v) {
		return f.apply(this.a, this.l.fold(f, v), this.r.fold(f, v));
	}

    //TODO: use fold
    <B> Tree<B> map(F1<A, B> f) {
        return new Branch<B>(f.apply(this.a), this.l.map(f), this.r.map(f));
	}

	Tree<A> filter(F1<A, Boolean> p) {
        F3<A, Tree<A>, Tree<A>, Tree<A>> f = (x, xs, ys) -> p.apply(x) ? new Branch<A>(x, xs, ys) : this.filter(p);
        return f.apply(this.a, this.l.filter(p), this.r.filter(p));
    }

    Nat depth(Tree<A> t) {
        S one = new S(new Z());
        return one.add(depth(this.l).max(depth(this.r)));
    }
}

final class Tip<A> extends Tree<A> {
	public Tip () {}

	<B> B fold(F3<A, B, B, B> f, B v) {
		return v;
	}

    <B> Tree<B> map(final F1<A, B> f) {
        return new Tip<B>();
    }

    Tree<A> filter(F1<A, Boolean> p) {
		return this;
	}

    Nat depth(Tree<A> t) {
        return new Z();
    }
}

I don't know why, but IntelliJ loves to ruin my syntax.