001 package fj.data; 002 003 import static fj.Bottom.error; 004 import fj.F; 005 import fj.F2; 006 import static fj.pre.Monoid.naturalAdditionMonoid; 007 import static fj.pre.Monoid.naturalMultiplicationMonoid; 008 import static fj.Function.curry; 009 import fj.data.vector.V2; 010 import fj.data.vector.V; 011 012 import java.math.BigInteger; 013 014 /** 015 * Represents a natural number (zero, one, two, etc.) 016 */ 017 public class Natural extends Number { 018 private BigInteger value; 019 private static final long serialVersionUID = -588673650944359682L; 020 021 private Natural(final BigInteger i) { 022 if (i.compareTo(BigInteger.ZERO) < 0) 023 throw error("Natural less than zero"); 024 value = i; 025 } 026 027 /** 028 * Returns the natural number equal to the given BigInteger 029 * 030 * @param i A given BigInteger 031 * @return An optional natural number, or none if the given BigInteger is less than zero. 032 */ 033 public static Option<Natural> natural(final BigInteger i) { 034 return i.compareTo(BigInteger.ZERO) < 0 035 ? Option.<Natural>none() 036 : Option.some(new Natural(i)); 037 } 038 039 /** 040 * A function that returns the natural number equal to a given BigInteger 041 */ 042 public static final F<BigInteger, Option<Natural>> fromBigInt = 043 new F<BigInteger, Option<Natural>>() { 044 public Option<Natural> f(final BigInteger i) { 045 return natural(i); 046 } 047 }; 048 049 /** 050 * Returns the natural number equal to the given long 051 * 052 * @param i A given long 053 * @return An optional natural number, or none if the given long is less than zero. 054 */ 055 public static Option<Natural> natural(final long i) { 056 return natural(BigInteger.valueOf(i)); 057 } 058 059 /** 060 * The natural number zero 061 */ 062 public static final Natural ZERO = natural(0).some(); 063 064 /** 065 * The natural number one 066 */ 067 public static final Natural ONE = natural(1).some(); 068 069 /** 070 * Return the successor of this natural number 071 * 072 * @return the successor of this natural number 073 */ 074 public Natural succ() { 075 return add(ONE); 076 } 077 078 /** 079 * First-class successor function. 080 * 081 * @return A function that returns the successor of a given natural number. 082 */ 083 public static F<Natural, Natural> succ_() { 084 return new F<Natural, Natural>() { 085 public Natural f(final Natural natural) { 086 return natural.succ(); 087 } 088 }; 089 } 090 091 /** 092 * Return the predecessor of this natural number 093 * 094 * @return the predecessor of this natural number 095 */ 096 public Option<Natural> pred() { 097 return subtract(ONE); 098 } 099 100 /** 101 * First-class predecessor function. 102 * 103 * @return A function that returns the predecessor of a given natural number, or None if it's zero. 104 */ 105 public static F<Natural, Option<Natural>> pred_() { 106 return new F<Natural, Option<Natural>>() { 107 public Option<Natural> f(final Natural natural) { 108 return natural.pred(); 109 } 110 }; 111 } 112 113 /** 114 * Add two natural numbers together. 115 * 116 * @param n A natural number to add to this one. 117 * @return the sum of the two natural numbers. 118 */ 119 public Natural add(final Natural n) { 120 return natural(n.value.add(value)).some(); 121 } 122 123 /** 124 * A function that adds two natural numbers. 125 */ 126 public static final F<Natural, F<Natural, Natural>> add = curry(new F2<Natural, Natural, Natural>() { 127 public Natural f(final Natural n1, final Natural n2) { 128 return n1.add(n2); 129 } 130 }); 131 132 133 /** 134 * Subtract a natural number from another. 135 * 136 * @param n A natural number to subtract from this one. 137 * @return The difference between the two numbers, if this number is larger than the given one. Otherwise none. 138 */ 139 public Option<Natural> subtract(final Natural n) { 140 return natural(n.value.subtract(value)); 141 } 142 143 /** 144 * A function that subtracts its first argument from its second. 145 */ 146 public static final F<Natural, F<Natural, Option<Natural>>> subtract = 147 curry(new F2<Natural, Natural, Option<Natural>>() { 148 public Option<Natural> f(final Natural o, final Natural o1) { 149 return o1.subtract(o); 150 } 151 }); 152 153 /** 154 * Multiply a natural number by another. 155 * 156 * @param n A natural number to multiply by this one. 157 * @return The product of the two numbers. 158 */ 159 public Natural multiply(final Natural n) { 160 return natural(n.value.multiply(value)).some(); 161 } 162 163 /** 164 * A function that multiplies a natural number by another. 165 */ 166 public static final F<Natural, F<Natural, Natural>> multiply = curry(new F2<Natural, Natural, Natural>() { 167 public Natural f(final Natural n1, final Natural n2) { 168 return n1.multiply(n2); 169 } 170 }); 171 172 173 /** 174 * A function that divides its second argument by its first. 175 */ 176 public static final F<Natural, F<Natural, Natural>> divide = 177 curry(new F2<Natural, Natural, Natural>() { 178 public Natural f(final Natural n1, final Natural n2) { 179 return n2.divide(n1); 180 } 181 }); 182 183 /** 184 * Divide a natural number by another. 185 * 186 * @param n A natural number to divide this one by. 187 * @return The quotient of this number and the highest number, less than or equal to the given number, 188 * that divides this number. 189 */ 190 public Natural divide(final Natural n) { 191 return natural(value.divide(n.value)).some(); 192 } 193 194 /** 195 * Take the remainder of a natural number division. 196 * 197 * @param n A natural number to divide this one by. 198 * @return The remainder of division of this number by the given number. 199 */ 200 public Natural mod(final Natural n) { 201 return natural(value.mod(n.value)).some(); 202 } 203 204 /** 205 * A function that yields the remainder of division of its second argument by its first. 206 */ 207 public static final F<Natural, F<Natural, Natural>> mod = 208 curry(new F2<Natural, Natural, Natural>() { 209 public Natural f(final Natural n1, final Natural n2) { 210 return n2.mod(n1); 211 } 212 }); 213 214 /** 215 * Divide a natural number by another yielding both the quotient and the remainder. 216 * 217 * @param n A natural number to divide this one by. 218 * @return The quotient and the remainder, in that order. 219 */ 220 public V2<Natural> divmod(final Natural n) { 221 final BigInteger[] x = value.divideAndRemainder(n.value); 222 return V.v(natural(x[0]).some(), natural(x[1]).some()); 223 } 224 225 /** 226 * A function that divides its second argument by its first, yielding both the quotient and the remainder. 227 */ 228 public static final F<Natural, F<Natural, V2<Natural>>> divmod = 229 curry(new F2<Natural, Natural, V2<Natural>>() { 230 public V2<Natural> f(final Natural n1, final Natural n2) { 231 return n2.divmod(n1); 232 } 233 }); 234 235 236 /** 237 * Return the BigInteger value of this natural number. 238 * 239 * @return the BigInteger value of this natural number. 240 */ 241 public BigInteger bigIntegerValue() { 242 return value; 243 } 244 245 /** 246 * Return the long value of this natural number. 247 * 248 * @return the long value of this natural number. 249 */ 250 public long longValue() { 251 return value.longValue(); 252 } 253 254 /** 255 * Return the float value of this natural number. 256 * 257 * @return the float value of this natural number. 258 */ 259 public float floatValue() { 260 return value.floatValue(); 261 } 262 263 /** 264 * Return the double value of this natural number. 265 * 266 * @return the double value of this natural number. 267 */ 268 public double doubleValue() { 269 return value.doubleValue(); 270 } 271 272 /** 273 * Return the int value of this natural number. 274 * 275 * @return the int value of this natural number. 276 */ 277 public int intValue() { 278 return value.intValue(); 279 } 280 281 /** 282 * A function that returns the BigInteger value of a given Natural. 283 */ 284 public static final F<Natural, BigInteger> bigIntegerValue = new F<Natural, BigInteger>() { 285 public BigInteger f(final Natural n) { 286 return n.bigIntegerValue(); 287 } 288 }; 289 290 /** 291 * Sums a stream of natural numbers. 292 * 293 * @param ns A stream of natural numbers. 294 * @return The sum of all the natural numbers in the stream. 295 */ 296 public static Natural sum(final Stream<Natural> ns) { 297 return naturalAdditionMonoid.sumLeft(ns); 298 } 299 300 /** 301 * Takes the product of a stream of natural numbers. 302 * 303 * @param ns A stream of natural numbers. 304 * @return The product of all the natural numbers in the stream. 305 */ 306 public static Natural product(final Stream<Natural> ns) { 307 return naturalMultiplicationMonoid.sumLeft(ns); 308 } 309 310 /** 311 * Sums a list of natural numbers. 312 * 313 * @param ns A list of natural numbers. 314 * @return The sum of all the natural numbers in the list. 315 */ 316 public static Natural sum(final List<Natural> ns) { 317 return naturalAdditionMonoid.sumLeft(ns); 318 } 319 320 /** 321 * Takes the product of a list of natural numbers. 322 * 323 * @param ns A list of natural numbers. 324 * @return The product of all the natural numbers in the list. 325 */ 326 public static Natural product(final List<Natural> ns) { 327 return naturalMultiplicationMonoid.sumLeft(ns); 328 } 329 }