fork download
copy 
  1. import java.lang.String;
  2. import java.lang.StringBuilder;
  3. import java.lang.Integer;
  4. import java.lang.System;
  5.  
  6. interface Function<A, B> {
  7.     public B apply(A x);
  8. }
  9.  
  10. class List<A> {
  11. 	private final A 		head;
  12. 	private final List<A> 	tail;
  13. 	private final int		size;
  14.  
  15. 	// unit :: A -> M[A]
  16. 	// public List(A x) -- implied by "new List<>(A...)"
  17.  
  18. 	// "List" happens to be *additive*, so we also offer a "zero" instance 
  19. 	// and a "plus" operation
  20.  
  21. 	// "zero", a neutral element for the "plus" operation
  22. 	// public List()  -- implied by "new List<>(A...)"
  23.  
  24. 	// "plus" concatenates two Lists
  25. 	//     plus :: (M[A], M[A]) → M[A]
  26. 	// important properties regarding the zero:
  27. 	//     zero.plus(x) == x
  28. 	//     x.plus(zero) == x
  29. 	public List<A> plus(List<A> that) {
  30. 		if (this.size == 0) return that;
  31. 		return new List<A>(this.head, this.tail.plus(that));
  32. 	}
  33.  
  34. 	// a convenience constructor that hides excessive "plus"sing
  35. 	public List(A... xs) {
  36. 		// technically, we have to do something like:
  37. 		//     List<A> result = new List<>();
  38. 		//     for (A x : xs)
  39. 		//        result = result.plus(new List<>(x));
  40. 		//     this = result
  41. 		// let's take the equivalent shortcut:
  42.  
  43. 		if (xs.length == 0) {
  44. 			this.head	= null;
  45. 			this.tail	= null;
  46. 			this.size 	= 0;
  47. 		}
  48. 		else {
  49. 			List<A> result = new List<A>();
  50. 			for (int i = xs.length - 1; i > 0; i--) {
  51. 				result = new List<A>(xs[i], result);
  52. 			}
  53. 			this.head	= xs[0];
  54. 			this.tail 	= result;
  55. 			this.size	= result.size + 1;
  56. 		}
  57. 	}
  58.  
  59. 	// an internal constructor to create the linked lists
  60. 	private List(A x, List<A> xs) {
  61. 		this.head	= x;
  62. 		this.tail	= xs;
  63. 		this.size	= xs.size + 1;
  64. 	}
  65.  
  66. 	// "bind"
  67. 	//     bind :: (M[A], A → M[B]) → M[B]
  68. 	// can be implemented in terms of our "plus"
  69. 	public <B> List<B> bind(Function<A, List<B>> f) {
  70. 		if (this.size == 0) return new List<B>();
  71. 		List<B> partialResult = this.tail.bind(f);
  72. 		return f.apply(this.head).plus(partialResult);
  73. 	}
  74.  
  75. 	// how about a nice "toString"?
  76. 	public String toString() {
  77. 		StringBuilder sb = new StringBuilder();
  78. 		sb.append("[");
  79. 		if (this.size > 0) {
  80. 		   sb.append(this.head);
  81. 		   for (List<A> ptr = this.tail; ptr.size > 0; ptr = ptr.tail) {
  82. 		       sb.append(",");
  83. 		       sb.append(ptr.head);
  84. 		   }
  85. 		}
  86. 		sb.append("]");
  87. 		return sb.toString();
  88. 	}
  89. }
  90.  
  91. public class Main {
  92. 	public static void main (String[] args)
  93. 	{
  94. 		// example: repeat each element
  95. 	    final Function<String, List<String>> repeatEachElement = new Function<String, List<String>>() {
  96. 	    	@Override
  97. 	        public List<String> apply(String s) {
  98. 	            return new List<String>(s, s);
  99. 	        }
  100. 	    };
  101. 	    final List<String> strings = new List<String>("foo", "bar", "baz");
  102. 	    System.out.println(strings);
  103. 	    System.out.println(strings.bind(repeatEachElement));
  104.  
  105. 	    // example: square each element
  106. 	    final Function<Integer, List<Integer>> square = new Function<Integer, List<Integer>>() {
  107. 	    	@Override
  108. 	        public List<Integer> apply(Integer i) {
  109. 	            return new List<Integer>(i * i);
  110. 	        }
  111. 	    };
  112. 	    final List<Integer> numbers = new List<Integer>(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
  113. 	    System.out.println(numbers);
  114. 	    System.out.println(numbers.bind(square));
  115.  
  116. 	    // --------------- //
  117. 	    // The Monad Laws: //
  118. 	    // --------------- //
  119.  
  120. 	    // note: these aren't _proofs_ of correctnes,
  121. 	    // just some examples showing that they're probably correct.
  122.  
  123. 	    // 1. "(unit x) >>= f ≡  f x" //
  124. 	    assert new List<Integer>(42).bind(square).toString() == square.apply(42).toString();
  125.  
  126. 	    // 2. "m >>= unit ≡  m" //
  127. 	    final Function<Integer, List<Integer>> unit = new Function<Integer, List<Integer>>() {
  128. 	    	@Override
  129. 	    	public List<Integer> apply(Integer i) {
  130. 	    		return new List<>(i);
  131. 	    	}
  132. 	    };
  133. 	    assert numbers.bind(unit).toString() == numbers.toString();
  134.  
  135. 	    // 3. "(m >>= f) >>= g   ≡   m >>= ( \x -> (f x >>= g) )" //
  136. 	    // m = numbers
  137. 	    // f = square
  138. 	    // g = stringify
  139. 	    final Function<Integer, List<String>> stringify = new Function<Integer, List<String>>() {
  140. 	    	@Override
  141. 	    	public List<String> apply(Integer i) {
  142. 	    		return new List<>(i.toString());
  143. 	    	}
  144. 	    };
  145. 	    final Function<Integer, List<String>> nested = new Function<Integer, List<String>>() {
  146. 	    	@Override
  147. 	    	public List<String> apply(Integer i) {
  148. 	    		return square.apply(i).bind(stringify);
  149. 	    	}
  150. 	    };
  151. 	    assert numbers.bind(square).bind(stringify).toString()
  152. 	    	== numbers.bind(nested).toString();
  153. 	}
  154. }
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[foo,bar,baz]
[foo,foo,bar,bar,baz,baz]
[1,2,3,4,5,6,7,8,9,10]
[1,4,9,16,25,36,49,64,81,100]
https://ideone.com/S3r7v6
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!