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    }