Functional Java Code

	/**
	* Berlin Brown , berlin dot brown at gmail.com
	*
	* Java Insertion Sort based on Haskell impl (Convert from Haskell to Java).
	*
	*/
	package org.berlin.algo.basic;
	import java.io.Serializable;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.List;
	import java.util.Random;
	/**
	* Insertion Sort using list of integers.
	* Based on logic from "Introduction to algorithms", coreman, stein.
	*
	* Using recursion for later use with Haskell.
	*
	* Expected Output:
	* <pre>
	* Running main - insertion sort - with recursion
	* A {N=11}= [5, 2, 4, 6, 1, 3, 83, 12, 3, 5, 7, ].
	* A(after sort) = [1, 2, 3, 3, 4, 5, 5, 6, 7, 12, 83, ].
	* </pre>
	*/
	public class InsertionSortRecursionLists {
	/*
	* Based on Haskell version:
	insert e [] = [e]
	insert e lst@(x:xs)
	| e < x = e : lst
	| otherwise = x : (insert e xs)
	insertionSort lst = insertionSort' lst [] where
	insertionSort' [] lst = lst
	insertionSort' (x:xs) lst = insertionSort' xs (insert x lst)
	*/
	public InsertionSortRecursionLists insertionSort(final Integer [] A) {
	final List<Integer> list = Arrays.asList(A);
	final List<Integer> res = insertionSort(list);
	int i = 0;
	for (final Integer x : res) {
	A[i] = x;
	i++;
	}
	return this;
	}
	public List<Integer> insertionSort(final List<Integer> A) {
	if ((A == null) || (A.size() == 0)) {
	return $();
	}
	if (A.size() == 1) {
	return A;
	}
	final Pair<Integer, List<Integer>> xxs = toXs(A);
	return insertionSort(xxs, $());
	}
	public List<Integer> insertionSort(final Pair<Integer, List<Integer>> xxs, final List<Integer> addToLst) {
	if (xxs.x() == null) {
	// insertionSort' [] lst = lst
	return addToLst;
	} else {
	// Haskell: insertionSort' (x:xs) lst = insertionSort' xs (insert x lst)
	// Java code for this declaration
	return insertionSort(toXs(xxs.xs()), insert(xxs.x(), addToLst));
	}
	}
	public List<Integer> insert(final Integer e, final List<Integer> lst) {
	final Pair<Integer, List<Integer>> xxs = toXs(lst);
	final Integer x = xxs.x();
	final List<Integer> xs = xxs.xs();
	if ((lst == null) || (lst.size() == 0)) {
	final List<Integer> l = $();
	l.add(e);
	return l;
	} else {
	// Haskell:
	// insert e lst@(x:xs)
	// | e < x = e : lst
	// | otherwise = x : (insert e xs)
	if (e < x) {
	final List<Integer> addEtoList = $();
	addEtoList.add(e);
	for (final Integer z:lst) { addEtoList.add(z);}
	return addEtoList;
	} else {
	final List<Integer> recursiveResultCallInsert = insert(e, xs);
	final List<Integer> addXtoRecursiveList = $();
	addXtoRecursiveList.add(x);
	for (final Integer z:recursiveResultCallInsert) {
	addXtoRecursiveList.add(z);
	}
	return addXtoRecursiveList;
	}
	}
	}
	/**
	* Return x:xs
	* @param lst
	* @return
	*/
	public Pair<Integer, List<Integer>> toXs(final List<Integer> lst) {
	if ((lst == null) || (lst.size() == 0)) {
	return new Pair<Integer, List<Integer>>(null, $());
	} else if (lst.size() == 1) {
	return new Pair<Integer, List<Integer>>(lst.get(0), $());
	}
	final Integer x = lst.get(0);
	final List<Integer> xs = $();
	for (int i = 1; i < lst.size(); i++) { xs.add(lst.get(i)); }
	return new Pair<Integer, List<Integer>>(x, xs);
	}
	public List<Integer> xsToList(final Pair<Integer, List<Integer>> xxs) {
	final List<Integer> addToList = $();
	addToList.add(xxs.x());
	for (final Integer z:xxs.xs()) { addToList.add(z);}
	return addToList;
	}
	public final List<Integer> $() {
	return new ArrayList<Integer>();
	}
	public static class Pair <T, S> implements Serializable {
	private static final long serialVersionUID = -2202117371650541073L;
	private final T first;
	private final S second;
	public Pair(final T f, final S s) {
	first = f;
	second = s;
	}
	public T x() {
	return getFirst();
	}
	public S xs() {
	return getSecond();
	}
	public T getFirst() {
	return first;
	}
	public S getSecond() {
	return second;
	}
	/**
	* Return String string representation of object.
	* @return String
	*/
	public String toString() {
	return "("
	+ ((first == null) ? "" : first.toString()) + ", "
	+ ((second == null) ? "" : second.toString()) + ")";
	}
	}
	public static void logBefore(final Integer [] A) {
	System.out.print("A {N=" + A.length + "}= [");
	for (int i = 0; i < A.length; i++) {
	System.out.print(A[i] + ", " );
	}
	System.out.println("].");
	}
	public static void logAfter(final Integer [] A, final InsertionSortRecursionLists insertionSort) {
	System.out.print("A(after sort) = [");
	for (int i = 0; i < A.length; i++) {
	System.out.print(A[i] + ", " );
	}
	System.out.println("].");
	System.out.println();
	}
	public static void main(final String [] args) {
	System.out.println("Running main - insertion sort - with recursion");
	{
	final Integer A [] = {
	5, 2, 4, 6, 1, 3, 83, 12, 3, 5, 7
	};
	logBefore(A);
	// Run the insertion sort and update the entries for the array A
	final InsertionSortRecursionLists insertionSort = new InsertionSortRecursionLists().insertionSort(A);
	logAfter(A, insertionSort);
	}
	{
	// With random N
	final Integer A2 [] = new Integer [30];
	final Random rand = new Random(System.currentTimeMillis());
	for (int i = 0; i < A2.length; i++) {
	A2[i] = rand.nextInt(1000);
	}
	logBefore(A2);
	final InsertionSortRecursionLists insertionSort2 = new InsertionSortRecursionLists().insertionSort(A2);
	logAfter(A2, insertionSort2);
	}
	System.out.println("Done");
	}
	} // End of the Class //

view raw gistfile1.java hosted with ❤ by GitHub