001 package fj.data; 002 003 import static fj.data.Option.some; 004 import static fj.data.Stream.iterableStream; 005 import fj.F; 006 import fj.F2; 007 import fj.F3; 008 import fj.P1; 009 import fj.P2; 010 import fj.pre.Equal; 011 import static fj.Function.curry; 012 import static fj.Function.identity; 013 014 import java.util.Collection; 015 import java.util.Iterator; 016 import java.util.ListIterator; 017 import java.util.NoSuchElementException; 018 019 /** 020 * A wrapper for Iterable that equips it with some useful functions. 021 */ 022 public final class IterableW<A> implements Iterable<A> { 023 024 private final Iterable<A> i; 025 026 private IterableW(final Iterable<A> i) { 027 this.i = i; 028 } 029 030 /** 031 * Wraps the given iterable. 032 * 033 * @param a The iterable to wrap. 034 * @return An iterable equipped with some useful functions. 035 */ 036 public static <A> IterableW<A> wrap(final Iterable<A> a) { 037 return new IterableW<A>(a); 038 } 039 040 /** 041 * Provides a function that wraps the given iterable. 042 * 043 * @return A function that returns the given iterable, wrapped. 044 */ 045 public static <A, T extends Iterable<A>> F<T, IterableW<A>> wrap() { 046 return new F<T, IterableW<A>>() { 047 public IterableW<A> f(final T a) { 048 return wrap(a); 049 } 050 }; 051 } 052 053 /** 054 * Returns an Iterable that completely preserves the argument. The unit function for Iterables. 055 * 056 * @param a A value to preserve in an Iterable. 057 * @return An Iterable that yields the argument when iterated over. 058 */ 059 public static <A> IterableW<A> iterable(final A a) { 060 return wrap(some(a)); 061 } 062 063 /** 064 * Wraps a given function's return value in a Iterable. 065 * The Kleisli arrow for Iterables. 066 * 067 * @param f The function whose return value to wrap in a Iterable. 068 * @return The equivalent function whose return value is iterable. 069 */ 070 public static <A, B> F<A, IterableW<B>> iterable(final F<A, B> f) { 071 return new F<A, IterableW<B>>() { 072 public IterableW<B> f(final A a) { 073 return iterable(f.f(a)); 074 } 075 }; 076 } 077 078 /** 079 * Provides a transformation from a function to a Iterable-valued function that is equivalent to it. 080 * The first-class Kleisli arrow for Iterables. 081 * 082 * @return A transformation from a function to the equivalent Iterable-valued function. 083 */ 084 public static <A, B> F<F<A, B>, F<A, IterableW<B>>> arrow() { 085 return new F<F<A, B>, F<A, IterableW<B>>>() { 086 public F<A, IterableW<B>> f(final F<A, B> f) { 087 return iterable(f); 088 } 089 }; 090 } 091 092 /** 093 * Binds the given function across the wrapped Iterable with a final join. 094 * 095 * @param f A function to bind across the Iterable. 096 * @return an iterable result of binding the given function over the wrapped Iterable. 097 */ 098 public <B, T extends Iterable<B>> IterableW<B> bind(final F<A, T> f) { 099 return wrap(iterableStream(this).bind(new F<A, Stream<B>>() { 100 public Stream<B> f(final A a) { 101 return iterableStream(f.f(a)); 102 } 103 })); 104 } 105 106 /** 107 * Performs function application within an iterable (applicative functor pattern). 108 * 109 * @param f The iterable function to apply. 110 * @return A new iterable after applying the given iterable function to the wrapped iterable. 111 */ 112 public <B> IterableW<B> apply(final Iterable<F<A, B>> f) { 113 return wrap(f).bind(new F<F<A, B>, Iterable<B>>() { 114 public Iterable<B> f(final F<A, B> f) { 115 return map(f); 116 } 117 }); 118 } 119 120 /** 121 * Binds the given function to the values in the given iterables with a final join. 122 * 123 * @param a A given iterable to bind the given function with. 124 * @param b A given iterable to bind the given function with. 125 * @param f The function to apply to the values in the given iterables. 126 * @return A new iterable after performing the map, then final join. 127 */ 128 public static <A, B, C> IterableW<C> bind(final Iterable<A> a, final Iterable<B> b, final F<A, F<B, C>> f) { 129 return wrap(b).apply(wrap(a).map(f)); 130 } 131 132 /** 133 * Promotes a function of arity-2 to a function on iterables. 134 * 135 * @param f The function to promote. 136 * @return A function of arity-2 promoted to map over iterables. 137 */ 138 public static <A, B, C> F<Iterable<A>, F<Iterable<B>, IterableW<C>>> liftM2(final F<A, F<B, C>> f) { 139 return curry(new F2<Iterable<A>, Iterable<B>, IterableW<C>>() { 140 public IterableW<C> f(final Iterable<A> ca, final Iterable<B> cb) { 141 return bind(ca, cb, f); 142 } 143 }); 144 } 145 146 /** 147 * Performs a bind across each element of all iterables of an iterable, collecting the values in an iterable. 148 * This implementation is strict and requires O(n) stack space. 149 * 150 * @param as The iterable of iterables to transform. 151 * @return A iterable of iterables containing the results of the bind operations across all given iterables. 152 */ 153 public static <A, T extends Iterable<A>> IterableW<IterableW<A>> sequence(final Iterable<T> as) { 154 final Stream<T> ts = iterableStream(as); 155 return ts.isEmpty() ? iterable(wrap(Option.<A>none())) : wrap(ts.head()).bind(new F<A, Iterable<IterableW<A>>>() { 156 public Iterable<IterableW<A>> f(final A a) { 157 return sequence(ts.tail().map(IterableW.<T, Stream<T>>wrap())._1()) 158 .bind(new F<IterableW<A>, Iterable<IterableW<A>>>() { 159 public Iterable<IterableW<A>> f(final IterableW<A> as) { 160 return iterable(wrap(Stream.cons(a, new P1<Stream<A>>() { 161 public Stream<A> _1() { 162 return iterableStream(as); 163 } 164 }))); 165 } 166 }); 167 } 168 }); 169 } 170 171 /** 172 * The first-class bind function over Iterable. 173 * Returns a function that binds a given function across a given iterable. 174 * 175 * @return a function that binds a given function across a given iterable. 176 */ 177 public static <A, B, T extends Iterable<B>> F<IterableW<A>, F<F<A, T>, IterableW<B>>> bind() { 178 return new F<IterableW<A>, F<F<A, T>, IterableW<B>>>() { 179 public F<F<A, T>, IterableW<B>> f(final IterableW<A> a) { 180 return new F<F<A, T>, IterableW<B>>() { 181 public IterableW<B> f(final F<A, T> f) { 182 return a.bind(f); 183 } 184 }; 185 } 186 }; 187 } 188 189 /** 190 * Joins an Iterable of Iterables into a single Iterable. 191 * 192 * @param as An Iterable of Iterables to join. 193 * @return the joined Iterable. 194 */ 195 public static <A, T extends Iterable<A>> IterableW<A> join(final Iterable<T> as) { 196 final F<T, T> id = identity(); 197 return wrap(as).bind(id); 198 } 199 200 /** 201 * Returns a function that joins an Iterable of Iterables into a single Iterable. 202 * 203 * @return a function that joins an Iterable of Iterables into a single Iterable. 204 */ 205 public static <A, T extends Iterable<A>> F<Iterable<T>, IterableW<A>> join() { 206 return new F<Iterable<T>, IterableW<A>>() { 207 public IterableW<A> f(final Iterable<T> a) { 208 return join(a); 209 } 210 }; 211 } 212 213 /** 214 * Maps a given function across the wrapped Iterable. 215 * 216 * @param f A function to map across the wrapped Iterable. 217 * @return An Iterable of the results of mapping the given function across the wrapped Iterable. 218 */ 219 public <B> IterableW<B> map(final F<A, B> f) { 220 return bind(iterable(f)); 221 } 222 223 /** 224 * Returns a function that promotes any function so that it operates on Iterables. 225 * 226 * @return a function that promotes any function so that it operates on Iterables. 227 */ 228 public static <A, B> F<F<A, B>, F<IterableW<A>, IterableW<B>>> map() { 229 return new F<F<A, B>, F<IterableW<A>, IterableW<B>>>() { 230 public F<IterableW<A>, IterableW<B>> f(final F<A, B> f) { 231 return new F<IterableW<A>, IterableW<B>>() { 232 public IterableW<B> f(final IterableW<A> a) { 233 return a.map(f); 234 } 235 }; 236 } 237 }; 238 } 239 240 /** 241 * The catamorphism for Iterables, implemented as a left fold. 242 * 243 * @param f The function with which to fold the wrapped iterable. 244 * @param z The base case value of the destination type, applied first (leftmost) to the fold. 245 * @return The result of the catamorphism. 246 */ 247 public <B> B foldLeft(final F<B, F<A, B>> f, final B z) { 248 B p = z; 249 for (final A x : this) { 250 p = f.f(p).f(x); 251 } 252 return p; 253 } 254 255 /** 256 * Takes the first 2 elements of the iterable and applies the function to them, 257 * then applies the function to the result and the third element and so on. 258 * 259 * @param f The function to apply on each element of the iterable. 260 * @return The final result after the left-fold reduction. 261 */ 262 public A foldLeft1(final F2<A, A, A> f) { 263 return foldLeft1(curry(f)); 264 } 265 266 /** 267 * Takes the first 2 elements of the iterable and applies the function to them, 268 * then applies the function to the result and the third element and so on. 269 * 270 * @param f The function to apply on each element of the iterable. 271 * @return The final result after the left-fold reduction. 272 */ 273 public A foldLeft1(final F<A, F<A, A>> f) { 274 return iterableStream(this).foldLeft1(f); 275 } 276 277 /** 278 * The catamorphism for Iterables, implemented as a right fold. 279 * 280 * @param f The function with which to fold the wrapped iterable. 281 * @param z The base case value of the destination type, applied last (rightmost) to the fold. 282 * @return The result of the catamorphism. 283 */ 284 public <B> B foldRight(final F2<A, B, B> f, final B z) { 285 final F<B, B> id = identity(); 286 return foldLeft(curry(new F3<F<B, B>, A, B, B>() { 287 public B f(final F<B, B> k, final A a, final B b) { 288 return k.f(f.f(a, b)); 289 } 290 }), id).f(z); 291 } 292 293 /** 294 * Returns an iterator for this iterable. 295 * 296 * @return an iterator for this iterable. 297 */ 298 public Iterator<A> iterator() { 299 return i.iterator(); 300 } 301 302 /** 303 * Zips this iterable with the given iterable of functions, applying each function in turn to the 304 * corresponding element in this iterable to produce a new iterable. The iteration is normalised 305 * so that it ends when one of the iterators is exhausted. 306 * 307 * @param fs The iterable of functions to apply to this iterable. 308 * @return A new iterable with the results of applying the functions to this iterable. 309 */ 310 public <B> IterableW<B> zapp(final Iterable<F<A, B>> fs) { 311 return wrap(iterableStream(this).zapp(iterableStream(fs))); 312 } 313 314 /** 315 * Zips this iterable with the given iterable using the given function to produce a new iterable. If 316 * this iterable and the given iterable have different lengths, then the longer iterable is normalised 317 * so this function never fails. 318 * 319 * @param bs The iterable to zip this iterable with. 320 * @param f The function to zip this iterable and the given iterable with. 321 * @return A new iterable with a length the same as the shortest of this iterable and the given 322 * iterable. 323 */ 324 public <B, C> Iterable<C> zipWith(final Iterable<B> bs, final F<A, F<B, C>> f) { 325 return wrap(iterableStream(this).zipWith(iterableStream(bs), f)); 326 } 327 328 /** 329 * Zips this iterable with the given iterable using the given function to produce a new iterable. If 330 * this iterable and the given iterable have different lengths, then the longer iterable is normalised 331 * so this function never fails. 332 * 333 * @param bs The iterable to zip this iterable with. 334 * @param f The function to zip this iterable and the given iterable with. 335 * @return A new iterable with a length the same as the shortest of this iterable and the given 336 * iterable. 337 */ 338 public <B, C> Iterable<C> zipWith(final Iterable<B> bs, final F2<A, B, C> f) { 339 return zipWith(bs, curry(f)); 340 } 341 342 /** 343 * Zips this iterable with the given iterable to produce a iterable of pairs. If this iterable and the 344 * given iterable have different lengths, then the longer iterable is normalised so this function 345 * never fails. 346 * 347 * @param bs The iterable to zip this iterable with. 348 * @return A new iterable with a length the same as the shortest of this iterable and the given 349 * iterable. 350 */ 351 public <B> Iterable<P2<A, B>> zip(final Iterable<B> bs) { 352 return wrap(iterableStream(this).zip(iterableStream(bs))); 353 } 354 355 /** 356 * Zips this iterable with the index of its element as a pair. 357 * 358 * @return A new iterable with the same length as this iterable. 359 */ 360 public Iterable<P2<A, Integer>> zipIndex() { 361 return wrap(iterableStream(this).zipIndex()); 362 } 363 364 /** 365 * Returns a java.util.List implementation for this iterable. 366 * The returned list cannot be modified. 367 * 368 * @return An immutable implementation of java.util.List for this iterable. 369 */ 370 public java.util.List<A> toStandardList() { 371 return new java.util.List<A>() { 372 373 public int size() { 374 return iterableStream(IterableW.this).length(); 375 } 376 377 public boolean isEmpty() { 378 return iterableStream(IterableW.this).isEmpty(); 379 } 380 381 @SuppressWarnings({"unchecked"}) 382 public boolean contains(final Object o) { 383 return iterableStream(IterableW.this).exists(Equal.<A>anyEqual().eq((A) o)); 384 } 385 386 public Iterator<A> iterator() { 387 return IterableW.this.iterator(); 388 } 389 390 public Object[] toArray() { 391 return Array.iterableArray(iterableStream(IterableW.this)).array(); 392 } 393 394 @SuppressWarnings({"SuspiciousToArrayCall"}) 395 public <T> T[] toArray(final T[] a) { 396 return iterableStream(IterableW.this).toCollection().toArray(a); 397 } 398 399 public boolean add(final A a) { 400 return false; 401 } 402 403 public boolean remove(final Object o) { 404 return false; 405 } 406 407 public boolean containsAll(final Collection<?> c) { 408 return iterableStream(IterableW.this).toCollection().containsAll(c); 409 } 410 411 public boolean addAll(final Collection<? extends A> c) { 412 return false; 413 } 414 415 public boolean addAll(final int index, final Collection<? extends A> c) { 416 return false; 417 } 418 419 public boolean removeAll(final Collection<?> c) { 420 return false; 421 } 422 423 public boolean retainAll(final Collection<?> c) { 424 return false; 425 } 426 427 public void clear() { 428 throw new UnsupportedOperationException("Modifying an immutable List."); 429 } 430 431 public A get(final int index) { 432 return iterableStream(IterableW.this).index(index); 433 } 434 435 public A set(final int index, final A element) { 436 throw new UnsupportedOperationException("Modifying an immutable List."); 437 } 438 439 public void add(final int index, final A element) { 440 throw new UnsupportedOperationException("Modifying an immutable List."); 441 } 442 443 public A remove(final int index) { 444 throw new UnsupportedOperationException("Modifying an immutable List."); 445 } 446 447 public int indexOf(final Object o) { 448 int i = -1; 449 for (final A a : IterableW.this) { 450 i++; 451 if (a.equals(o)) 452 return i; 453 } 454 return i; 455 } 456 457 public int lastIndexOf(final Object o) { 458 int i = -1; 459 int last = -1; 460 for (final A a : IterableW.this) { 461 i++; 462 if (a.equals(o)) 463 last = i; 464 } 465 return last; 466 } 467 468 public ListIterator<A> listIterator() { 469 return toListIterator(toZipper()); 470 } 471 472 public ListIterator<A> listIterator(final int index) { 473 return toListIterator(toZipper().bind(Zipper.<A>move().f(index))); 474 } 475 476 public java.util.List<A> subList(final int fromIndex, final int toIndex) { 477 return wrap(Stream.iterableStream(IterableW.this).drop(fromIndex).take(toIndex - fromIndex)).toStandardList(); 478 } 479 480 private ListIterator<A> toListIterator(final Option<Zipper<A>> z) { 481 return new ListIterator<A>() { 482 483 private Option<Zipper<A>> pz = z; 484 485 public boolean hasNext() { 486 return pz.isSome() && !pz.some().atEnd(); 487 } 488 489 public A next() { 490 if (pz.isSome()) 491 pz = pz.some().next(); 492 else throw new NoSuchElementException(); 493 if (pz.isSome()) 494 return pz.some().focus(); 495 else throw new NoSuchElementException(); 496 } 497 498 public boolean hasPrevious() { 499 return pz.isSome() && !pz.some().atStart(); 500 } 501 502 public A previous() { 503 pz = pz.some().previous(); 504 return pz.some().focus(); 505 } 506 507 public int nextIndex() { 508 return pz.some().index() + (pz.some().atEnd() ? 0 : 1); 509 } 510 511 public int previousIndex() { 512 return pz.some().index() - (pz.some().atStart() ? 0 : 1); 513 } 514 515 public void remove() { 516 throw new UnsupportedOperationException("Remove on immutable ListIterator"); 517 } 518 519 public void set(final A a) { 520 throw new UnsupportedOperationException("Set on immutable ListIterator"); 521 } 522 523 public void add(final A a) { 524 throw new UnsupportedOperationException("Add on immutable ListIterator"); 525 } 526 }; 527 } 528 529 }; 530 } 531 532 public Option<Zipper<A>> toZipper() { 533 return Zipper.fromStream(iterableStream(this)); 534 } 535 }