001 package fj.data.hlist; 002 003 import fj.F; 004 import fj.F2; 005 import fj.F3; 006 import fj.P; 007 import fj.P2; 008 import fj.Unit; 009 import static fj.Function.compose; 010 011 /** 012 * Type-safe heterogeneous lists. 013 * 014 * @param <A> The specific type of the list, as a subtype of HList 015 */ 016 public abstract class HList<A extends HList<A>> { 017 018 protected HList() { 019 } 020 021 /** 022 * Extends (cons) this list by prepending the given element, returning a new list. 023 * 024 * @param e an element to prepend to this list. 025 * @return a new heterogeneous list, consisting of the given element prepended to this list. 026 */ 027 public abstract <E> HCons<E, A> extend(E e); 028 029 public abstract <E> Apply<Unit, P2<E, A>, HCons<E, A>> extender(); 030 031 private static final HNil nil = new HNil(); 032 033 /** 034 * Returns the empty list. 035 * 036 * @return the empty list. 037 */ 038 public static HNil nil() { 039 return nil; 040 } 041 042 /** 043 * Returns a heterogeneous list consisting of an element and another list. 044 * 045 * @param e an element to put in a list. 046 * @param l the rest of the list. 047 * @return a heterogeneous list consisting of an element and another list. 048 */ 049 public static <E, L extends HList<L>> HCons<E, L> cons(final E e, final L l) { 050 return new HCons<E, L>(e, l); 051 } 052 053 /** 054 * Returns a heterogeneous list consisting of a single element. 055 * 056 * @param e an element to put in a list 057 * @return a heterogeneous list consisting of a single element. 058 */ 059 public static <E> HCons<E, HNil> single(final E e) { 060 return cons(e, nil()); 061 } 062 063 /** 064 * The concatenation of two heterogeneous lists. 065 * 066 * @param <A> The type of the first list. 067 * @param <B> The type of the second list. 068 * @param <C> The type of the combined list. 069 */ 070 public static final class HAppend<A, B, C> { 071 private final F2<A, B, C> append; 072 073 private HAppend(final F2<A, B, C> f) { 074 append = f; 075 } 076 077 /** 078 * Append a given heterogeneous list to another. 079 * 080 * @param a a heterogeneous list to be appended to. 081 * @param b a heterogeneous list to append to another. 082 * @return a new heterogeneous list consisting of the second argument appended to the first. 083 */ 084 public C append(final A a, final B b) { 085 return append.f(a, b); 086 } 087 088 /** 089 * Returns a method for concatenating lists to the empty list. 090 * 091 * @return a method for concatenating lists to the empty list. 092 */ 093 public static <L extends HList<L>> HAppend<HNil, L, L> append() { 094 return new HAppend<HNil, L, L>(new F2<HNil, L, L>() { 095 public L f(final HNil hNil, final L l) { 096 return l; 097 } 098 }); 099 } 100 101 /** 102 * Returns a method for appending lists to a nonempty heterogeneous list. 103 * 104 * @param h a method for appending lists to the tail of the given nonempty list. 105 * @return a method for appending lists to a nonempty heterogeneous list. 106 */ 107 public static <X, A extends HList<A>, B, C extends HList<C>, H extends HAppend<A, B, C>> 108 HAppend<HCons<X, A>, B, HCons<X, C>> append(final H h) { 109 return new HAppend<HCons<X, A>, B, HCons<X, C>>(new F2<HCons<X, A>, B, HCons<X, C>>() { 110 public HCons<X, C> f(final HCons<X, A> c, final B l) { 111 return cons(c.head(), h.append(c.tail(), l)); 112 } 113 }); 114 } 115 } 116 117 /** 118 * Type-level function application operators. 119 * 120 * @param <F$> The type of the function to apply. 121 * @param <A> The domain of the function. 122 * @param <R> The function's codomain. 123 */ 124 public abstract static class Apply<F$, A, R> { 125 public abstract R apply(F$ f, A a); 126 127 /** 128 * Function application operator. 129 * 130 * @return an operator that applies a given function to a given argument. 131 */ 132 public static <X, Y> Apply<F<X, Y>, X, Y> f() { 133 return new Apply<F<X, Y>, X, Y>() { 134 public Y apply(final F<X, Y> f, final X x) { 135 return f.f(x); 136 } 137 }; 138 } 139 140 /** 141 * Identity operator 142 * 143 * @return An operator that returns its second argument no matter which function is being applied. 144 */ 145 public static <X> Apply<Unit, X, X> id() { 146 return new Apply<Unit, X, X>() { 147 public X apply(final Unit f, final X x) { 148 return x; 149 } 150 }; 151 } 152 153 /** 154 * A function application operator for function composition. 155 * 156 * @param <X> The domain. 157 * @param <Y> The type through which to compose. 158 * @param <Z> The codomain. 159 * @return an operator that composes functions. 160 */ 161 public static <X, Y, Z> Apply<Unit, P2<F<X, Y>, F<Y, Z>>, F<X, Z>> comp() { 162 return new Apply<Unit, P2<F<X, Y>, F<Y, Z>>, F<X, Z>>() { 163 public F<X, Z> apply(final Unit f, final P2<F<X, Y>, F<Y, Z>> fs) { 164 return compose(fs._2(), fs._1()); 165 } 166 }; 167 } 168 169 /** 170 * An operator for the construction of heterogeneous lists. 171 * 172 * @return an operator that constructs heterogeneous lists. 173 */ 174 public static <E, L extends HList<L>> Apply<Unit, P2<E, L>, HCons<E, L>> cons() { 175 return new Apply<Unit, P2<E, L>, HCons<E, L>>() { 176 public HCons<E, L> apply(final Unit f, final P2<E, L> p) { 177 return HList.cons(p._1(), p._2()); 178 } 179 }; 180 } 181 182 /** 183 * A function application operator for concatenating heterogeneous lists. 184 * 185 * @param <A> The type of the list to which to append. 186 * @param <B> The type of the list to append. 187 * @param <C> The type of the concatenated list. 188 * @return an operator that concatenates heterogeneous lists. 189 */ 190 public static <A, B, C> Apply<HAppend<A, B, C>, P2<A, B>, C> append() { 191 return new Apply<HAppend<A, B, C>, P2<A, B>, C>() { 192 public C apply(final HAppend<A, B, C> f, final P2<A, B> p) { 193 return f.append(p._1(), p._2()); 194 } 195 }; 196 } 197 } 198 199 /** 200 * The catamorphism over heterogeneous lists. 201 * 202 * @param <G> The type of the function with which to fold. 203 * @param <V> The type of the value to be substituted for the empty list. 204 * @param <L> The type of the heterogeneous list to be folded. 205 * @param <R> The return type of the fold. 206 */ 207 public static class HFoldr<G, V, L, R> { 208 209 private final F3<G, V, L, R> foldRight; 210 211 private HFoldr(final F3<G, V, L, R> foldRight) { 212 this.foldRight = foldRight; 213 } 214 215 /** 216 * A fold instance for the empty list. 217 * 218 * @param <G> The type of the function with which to fold. 219 * @param <V> The type of value that this fold returns. 220 * @return a fold instance for the empty list. 221 */ 222 public static <G, V> HFoldr<G, V, HNil, V> hFoldr() { 223 return new HFoldr<G, V, HNil, V>(new F3<G, V, HNil, V>() { 224 public V f(final G f, final V v, final HNil hNil) { 225 return v; 226 } 227 }); 228 } 229 230 /** 231 * A fold instance for a non-empty heterogeneous list 232 * 233 * @param p An operator that applies a function on the head of the list and the fold of its tail. 234 * @param h A fold instance for the tail of the list. 235 * @param <E> The type of the head of the list. 236 * @param <G> The type of function to apply to the head of the list and the fold of its tail. 237 * @param <V> The type of value to substitute for the empty list. 238 * @param <L> The type of the tail of the list. 239 * @param <R> The type of the fold of the tail of the list. 240 * @param <RR> The return type of the fold. 241 * @param <H> The type of the fold instance for the tail of the list. 242 * @param <PP> The type of the given function application operator. 243 * @return A fold instance for a non-empty heterogeneous list. 244 */ 245 public static <E, G, V, L extends HList<L>, R, RR, 246 H extends HFoldr<G, V, L, R>, 247 PP extends Apply<G, P2<E, R>, RR>> 248 HFoldr<G, V, HCons<E, L>, RR> hFoldr(final PP p, final H h) { 249 return new HFoldr<G, V, HCons<E, L>, RR>(new F3<G, V, HCons<E, L>, RR>() { 250 public RR f(final G f, final V v, final HCons<E, L> c) { 251 return p.apply(f, P.p(c.head(), h.foldRight(f, v, c.tail()))); 252 } 253 }); 254 } 255 256 /** 257 * Folds a non-empty heterogeneous list. 258 * 259 * @param f A function with which to fold. 260 * @param v The value to substitute for the empty list. 261 * @param l The heterogeneous list to be folded. 262 * @return a value obtained by folding the given list with the given function. 263 */ 264 public R foldRight(final G f, final V v, final L l) { 265 return foldRight.f(f, v, l); 266 } 267 268 } 269 270 /** 271 * The nonempty list 272 */ 273 public static final class HCons<E, L extends HList<L>> extends HList<HCons<E, L>> { 274 private E e; 275 private L l; 276 277 HCons(final E e, final L l) { 278 this.e = e; 279 this.l = l; 280 } 281 282 public E head() { 283 return e; 284 } 285 286 public L tail() { 287 return l; 288 } 289 290 public <X> Apply<Unit, P2<X, HCons<E, L>>, HCons<X, HCons<E, L>>> extender() { 291 return Apply.cons(); 292 } 293 294 public <X> HCons<X, HCons<E, L>> extend(final X e) { 295 return cons(e, this); 296 } 297 298 } 299 300 /** 301 * The empty list 302 */ 303 public static final class HNil extends HList<HNil> { 304 HNil() { 305 } 306 307 public <E> HCons<E, HNil> extend(final E e) { 308 return cons(e, this); 309 } 310 311 public <E> Apply<Unit, P2<E, HNil>, HCons<E, HNil>> extender() { 312 return Apply.cons(); 313 } 314 315 } 316 }