001 package fj.data; 002 003 import fj.Effect; 004 import fj.F; 005 import fj.FW; 006 import static fj.data.Option.some; 007 import static fj.data.Option.somes; 008 009 import java.util.Collection; 010 import java.util.Iterator; 011 012 /** 013 * Provides an in-memory, immutable, singly linked list with total <code>head</code> and <code>tail</code>. 014 * 015 * @version %build.number%<br> 016 * <ul> 017 * <li>$LastChangedRevision: 180 $</li> 018 * <li>$LastChangedDate: 2009-06-28 09:59:09 +1000 (Sun, 28 Jun 2009) $</li> 019 * </ul> 020 */ 021 public final class NonEmptyList<A> implements Iterable<A> { 022 /** 023 * Returns an iterator for this non-empty list. This method exists to permit the use in a <code>for</code>-each loop. 024 * 025 * @return A iterator for this non-empty list. 026 */ 027 028 public Iterator<A> iterator() { 029 return toCollection().iterator(); 030 } 031 032 /** 033 * The first element of this linked list. 034 */ 035 @SuppressWarnings({"PublicField", "ClassEscapesDefinedScope"}) 036 public final A head; 037 038 /** 039 * This list without the first element. 040 */ 041 @SuppressWarnings({"PublicField"}) 042 public final List<A> tail; 043 044 private NonEmptyList(final A head, final List<A> tail) { 045 this.head = head; 046 this.tail = tail; 047 } 048 049 /** 050 * Prepend the given value to this list. 051 * 052 * @param a The value to prepend. 053 * @return A non-empty list with an extra element. 054 */ 055 public NonEmptyList<A> cons(final A a) { 056 return nel(a, tail.cons(head)); 057 } 058 059 /** 060 * Appends the given list to this list. 061 * 062 * @param as The list to append. 063 * @return A new list with the given list appended. 064 */ 065 public NonEmptyList<A> append(final NonEmptyList<A> as) { 066 final List.Buffer<A> b = new List.Buffer<A>(); 067 b.append(tail); 068 b.snoc(as.head); 069 b.append(as.tail); 070 final List<A> bb = b.toList(); 071 return nel(head, bb); 072 } 073 074 /** 075 * Maps the given function across this list. 076 * 077 * @param f The function to map across this list. 078 * @return A new list after the given function has been applied to each element. 079 */ 080 public <B> NonEmptyList<B> map(final F<A, B> f) { 081 return nel(f.f(head), tail.map(f)); 082 } 083 084 /** 085 * Binds the given function across each element of this list with a final join. 086 * 087 * @param f The function to apply to each element of this list. 088 * @return A new list after performing the map, then final join. 089 */ 090 public <B> NonEmptyList<B> bind(final F<A, NonEmptyList<B>> f) { 091 final List.Buffer<B> b = new List.Buffer<B>(); 092 final NonEmptyList<B> p = f.f(head); 093 b.snoc(p.head); 094 b.append(p.tail); 095 tail.foreach(new Effect<A>() { 096 public void e(final A a) { 097 final NonEmptyList<B> p = f.f(a); 098 b.snoc(p.head); 099 b.append(p.tail); 100 } 101 }); 102 final List<B> bb = b.toList(); 103 return nel(bb.head(), bb.tail()); 104 } 105 106 /** 107 * Returns a NonEmptyList of the sublists of this list. 108 * 109 * @return a NonEmptyList of the sublists of this list. 110 */ 111 public NonEmptyList<NonEmptyList<A>> sublists() { 112 return fromList( 113 somes(toList().toStream().substreams() 114 .map(FW.<List<A>, Option<NonEmptyList<A>>>$(new F<List<A>, Option<NonEmptyList<A>>>() { 115 public Option<NonEmptyList<A>> f(final List<A> list) { 116 return fromList(list); 117 } 118 }).o(Conversions.<A>Stream_List())).toList())).some(); 119 } 120 121 /** 122 * Returns a NonEmptyList of the tails of this list. A list is considered a tail of itself for the purpose of this 123 * function (Comonad pattern). 124 * 125 * @return A NonEmptyList of the tails of this list. 126 */ 127 public NonEmptyList<NonEmptyList<A>> tails() { 128 return fromList(somes(toList().tails().map(new F<List<A>, Option<NonEmptyList<A>>>() { 129 public Option<NonEmptyList<A>> f(final List<A> list) { 130 return fromList(list); 131 } 132 }))).some(); 133 } 134 135 /** 136 * Maps the given function across the tails of this list (comonad pattern). 137 * 138 * @param f The function to map across the tails of this list. 139 * @return The results of applying the given function to the tails of this list, as a NonEmptyList. 140 */ 141 public <B> NonEmptyList<B> mapTails(final F<NonEmptyList<A>, B> f) { 142 return tails().map(f); 143 } 144 145 /** 146 * Returns a <code>List</code> projection of this list. 147 * 148 * @return A <code>List</code> projection of this list. 149 */ 150 public List<A> toList() { 151 return tail.cons(head); 152 } 153 154 /** 155 * Projects an immutable collection of this non-empty list. 156 * 157 * @return An immutable collection of this non-empty list. 158 */ 159 public Collection<A> toCollection() { 160 return toList().toCollection(); 161 } 162 163 /** 164 * Returns a function that takes a non-empty list to a list. 165 * 166 * @return A function that takes a non-empty list to a list. 167 */ 168 public static <A> F<NonEmptyList<A>, List<A>> toList_() { 169 return new F<NonEmptyList<A>, List<A>>() { 170 public List<A> f(final NonEmptyList<A> as) { 171 return as.toList(); 172 } 173 }; 174 } 175 176 /** 177 * Return a non-empty list with the given head and tail. 178 * 179 * @param head The first element of the new list. 180 * @param tail The remaining elements of the new list. 181 * @return A non-empty list with the given head and tail. 182 */ 183 public static <A> NonEmptyList<A> nel(final A head, final List<A> tail) { 184 return new NonEmptyList<A>(head, tail); 185 } 186 187 /** 188 * Return a non-empty list with the given value. 189 * 190 * @param head The value in the non-empty list. 191 * @return A non-empty list with the given value. 192 */ 193 public static <A> NonEmptyList<A> nel(final A head) { 194 return nel(head, List.<A>nil()); 195 } 196 197 /** 198 * Returns a function that puts an element into a non-empty list. 199 * 200 * @return A function that puts an element into a non-empty list. 201 */ 202 public static <A> F<A, NonEmptyList<A>> nel() { 203 return new F<A, NonEmptyList<A>>() { 204 public NonEmptyList<A> f(final A a) { 205 return nel(a); 206 } 207 }; 208 } 209 210 /** 211 * Returns a potential non-empty list from the given list. A non-value is returned if the given list is empty. 212 * 213 * @param as The list to construct a potential non-empty list with. 214 * @return A potential non-empty list from the given list. 215 */ 216 public static <A> Option<NonEmptyList<A>> fromList(final List<A> as) { 217 return as.isEmpty() ? 218 Option.<NonEmptyList<A>>none() : 219 some(nel(as.head(), as.tail())); 220 } 221 }