Lazy Lists in Java and some basic functions on them

Lazy_List.java

/*
Copyright (C) Freddy A Cubas "Superstar64" 2020

Boost Software License - Version 1.0 - August 17th, 2003

Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license (the "Software") to use, reproduce, display, distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
*/
public class Lazy_List {
	// java's lambdas allow 'a -> x' for creating functions
	// do 'f.$(x)' to call a function
	interface Function<A, R> {
		R $(A x);
	}
	
	// lazy values are values that store a computation that create the actual value
	// java's lambdas allows '() -> x' for creating lazy values
	interface Lazy<A> {
		A get();
	}
	
	// a list is either empty or has a head and a tail
	// these are called nil and cons respectivly
	interface List<A> {
		// this uses Scott encoding to encode that choice as a function
		// provide 2 functions, that match whether the list is empty, or it has a head and tail
		<R> R match(Function<Nil<A>, R> nil, Function<Cons<A>, R> cons);
	}

	static class Nil<A> implements List<A> {
		Nil() {
		}

		public <R> R match(Function<Nil<A>, R> nil, Function<Cons<A>, R> cons) {
			return nil.$(this);
		}
	}

	static class Cons<A> implements List<A> {
		A head;
		List<A> tail;

		Cons(A head, List<A> tail) {
			this.head = head;
			this.tail = tail;
		}
		public <R> R match(Function<Nil<A>, R> nil, Function<Cons<A>, R> cons) {
			return cons.$(this);
		}
	}

	// this is a hack that converts a lazy value containing a list, into a lazy list
	static <A> List<A> flatten(Lazy<List<A>> lazy_list) {
		return new List<A>() {
			public <R> R match(Function<Nil<A>, R> nil, Function<Cons<A>, R> cons) {
				return lazy_list.get().match(nil, cons);
			}
		};
	}
	
	// apply a function to every element
	static <A, B> List<B> map(Function<A, B> function, List<A> list) {
		return flatten(() -> list.match(
			nil -> new Nil<B>(),
			cons -> new Cons<B>(function.$(cons.head), map(function, cons.tail))
		));
	}
	
	// combine to lists, putting left before right
	static <A> List<A> append(List<A> left, List<A> right) {
		return flatten(() -> left.match(
			nil -> right,
			cons -> new Cons<A>(cons.head, append(cons.tail, right))
		));
	}
	
	//squish a list of lists into a list
	static <A> List<A> concat(List<List<A>> list) {
		return flatten(() -> list.match(
			nil -> new Nil<A>(),
			cons -> append(cons.head, concat(cons.tail))
		));
	}
	
	//take at most the first n element of a list
	static <A> List<A> take(Integer amount, List<A> list){
		if (amount == 0) {
			return new Nil<A>();
		} else {
			return flatten(() -> list.match(
				nil -> new Nil<A>(),
				cons -> new Cons<A>(cons.head,take(amount-1,cons.tail))
			));
		}
	}
	
	
	static <A> String prettyPrintImpl(Function<A,String> prettyItem, List<A> list){
		return list.match(
			nil -> "",
			cons -> prettyItem.$(cons.head) + ", " + prettyPrintImpl(prettyItem, cons.tail)
		);
	}
	
	static <A> String prettyPrint(Function<A,String> prettyItem, List<A> list){
		return "[" + prettyPrintImpl(prettyItem, list) + "]";
	}
	
	//creates an infinite list of the natural numbers, starting fro the argument
	static List<Integer> naturalsFrom(Integer from){
		return flatten(() -> new Cons<Integer>(from, naturalsFrom(from + 1)));
	}
	
	public static void main(String[] args){
		List<Integer> naturals = naturalsFrom(0);
		List<Integer> squares = map(x -> x * x, naturals);
		
		List<Integer> firstXNumbers = take(100,naturals);
		List<Integer> firstXSquares = take(100,squares);
		
		System.out.println(prettyPrint(x -> x.toString(), firstXNumbers));
		System.out.println(prettyPrint(x -> x.toString(), firstXSquares));
		
		//the nth index is a list of the n natural numbers
		List<List<Integer>> naturalsList = map(i -> take(i,naturals), naturals);
		
		System.out.println(prettyPrint(list -> prettyPrint(x -> x.toString(),list), take(6, naturalsList) ) );
		
		List<Integer> naturalsListConcat = concat(naturalsList);
		
		System.out.println(prettyPrint(x -> x.toString(), take(20, naturalsListConcat)));
	}
	
	// unrelated but, useful utilities
	static class Pair<A, B> {
		A left;
		B right;

		Pair(A left, B right) {
			this.left = left;
			this.right = right;
		}
	}
	
	static <A, B> A first(Pair<A, B> pair) {
		return pair.left;
	}

	static <A, B> B second(Pair<A, B> pair) {
		return pair.right;
	}
	
	static <A, B, C> Function<A, C> compose(Function<B, C> f, Function<A, B> g) {
		return x -> f.$(g.$(x));
	}
}