dtm: (Default)
[personal profile] dtm
Yeah, yeah. Haven't posted in two months, blah blah blah.

And this isn't going to be a life update post either. Sorry. People who are not CS types (and this is much more academic CS than practical CS stuff) should just skip this post.

Now, I present some gloriously ridiculous, useless code, done primarily to show that I could do this in java, and do so in a typesafe manner.

package com.google.functional;

// this is an interface with just one method, apply()
import com.google.common.base.Function;

import junit.framework.TestCase;

public class YNot extends TestCase {
  public static interface Fii extends Function<Integer, Integer> {
  }
  public static interface Branch extends Function<Branch, Fii> {
  }

  // Look, it's an anonymous recursive function!
  public void testY() {
    assertEquals(720,
        new Function<Function<Fii, Fii>, Fii>() {
          public Fii apply(final Function<Fii, Fii> f) {
            return new Branch() {
              public Fii apply(final Branch x) {
                return f.apply(new Fii() {
                  public Integer apply(Integer y) {
                    return x.apply(x).apply(y);
                  }
                });
              }
            }.apply(new Branch() {
              public Fii apply(final Branch x) {
                return f.apply(new Fii() {
                  public Integer apply(Integer y) {
                    return x.apply(x).apply(y);
                  }
                });
              }
            });
          }
        }.apply(new Function<Fii, Fii>() {
          public Fii apply(final Fii f) {
            return new Fii() {
              public Integer apply(Integer i) {
                return (i <= 0) ? 1 : i * f.apply(i - 1);
              }
            };
          }
        }).apply(6).intValue());
  }
}


Well that was a bit interesting. Get you head around how it works, if you've never worked all the way through the Y combinator before. The relevant wikipedia article might be useful. The translation from scheme to java was fairly straightforward; the trick was getting all the types to work out properly.

But wait, there's more! That code there isn't really reuseable at all. What's really needed is a version that works with arbitrary types:

package com.google.functional;

import com.google.common.base.Function;

import junit.framework.TestCase;

public class YCFun extends TestCase {
  public static interface BranchType<F, T> extends
      Function<BranchType<F, T>, Function<F, T>> {
  }

  public static <F, T> Function<Function<Function<F, T>,
      Function<F, T>>, Function<F, T>> y() {
    return new Function<Function<Function<F, T>, Function<F, T>>,
        Function<F, T>>() {
      public Function<F, T> apply(
          final Function<Function<F, T>, Function<F, T>> f) {
        return new BranchType<F, T>() {
          public Function<F, T> apply(final BranchType<F, T> x) {
            return f.apply(new Function<F, T>() {
              public T apply(F y) {
                return x.apply(x).apply(y);
              }
            });
          }
        }.apply(new BranchType<F, T>() {
          public Function<F, T> apply(final BranchType<F, T> x) {
            return f.apply(new Function<F, T>() {
              public T apply(F y) {
                return x.apply(x).apply(y);
              }
            });
          }
        });
      }
    };
  }

  // To get proper type inference
  public static <F, T> Function<F, T> yapply(
      final Function<Function<F, T>, Function<F, T>> f) {
    return YCFun.<F, T> y().apply(f);
  }

  public void testFactorial() {
    Function<Integer, Integer> factorial =
        yapply(new Function<Function<Integer, Integer>,
            Function<Integer, Integer>>() {
          public Function<Integer, Integer> apply(
              final Function<Integer, Integer> f) {
            return new Function<Integer, Integer>() {
              public Integer apply(Integer i) {
                if (i <= 0) {
                  return 1;
                } else {
                  return f.apply(i - 1) * i;
                }
              }
            };
          }
        });
    assertEquals(720, factorial.apply(6).intValue());
  }
}


Oh, and for those of you worried that I'm giving away internal Google secrets by using the interface com.google.common.base.Function, that's already been open-sourced as part of the Google Collections Library.
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

May 2017

S M T W T F S
 123456
78910111213
14151617181920
212223242526 27
28293031   

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 19th, 2017 06:44 pm
Powered by Dreamwidth Studios