はじめに

もともと Lisp の概念だそうです.
私は Lisp にあまり詳しくないため概念だけ調べてみました.

ゴール

ガッツリとした実装はしません.
「ペアの関数を作って値を取り出す関数を作る」程度で留めます.

~~なぜ元ネタ Lisp で書かないのか🙂~~

ことば

Cons

２つの要素を持つペアを構成する関数を作ります construct.
f(a, b)

Car

先頭要素 head を返します.
今回はペアを扱うため左 left の要素を返します.
a

Cdr

残りの要素 tail を返します.
今回はペアを扱うため右 right の要素を返します.
b

Haskell の場合🙂

ペアの関数、第一要素を返す関数、第二要素を返す関数をそれぞれ:tで type を表示してみた結果です.

.hs

Prelude> :t (,)
(,) :: a -> b -> (a, b)

Prelude> :t fst
fst :: (a, b) -> a

Prelude> :t snd
snd :: (a, b) -> b

実装する

まずは Python3 と Javascript で表現します.

Python

.py

def cons(a, b):
    def pair(f):
        return f(a, b)
    return pair

def car(pair):
    def f(a, b):
        return a
    return pair(f)

def cdr(pair):
    def f(a, b):
        return b
    return pair(f)

lambda

.py

def cons(a, b):
    return lambda f: f(a, b)

def car(pair):
    return pair(lambda a, b: a)

def cdr(pair):
    return pair(lambda a, b: b)

print out

.py

# get 3
car(cons(3, 4))
# get 4
cdr(cons(3, 4))
# get 'j'
car(cdr(cons('i', cons('j', 'k'))))

Javascript

.js

function cons(a,b) {
  return function(pair) {
    return pair(a, b);
  };
};

function car(pair) {
  return pair(function(a, b){
    return a;
  });
};

function cdr(pair) {
  return pair(function(a, b) {
    return b;
  });
};

Arrow Function

.js

var cons = (a, b) => pair => pair(a, b);
var car = pair => pair((a, b) => a);
var cdr = pair => pair((a, b) => b);

print out

.js

// get 'a'
car(cdr(cons(cons(99, 100), cons('a', 'b'))))

あやしく実装する

Java と Scala で「試します」.
結論からいうと、静的かつ強い型付けの言語において、実装における「型」が一番悩ましいポイントになりました.

Java

.java

import java.util.function.BiFunction;
import java.util.function.Function;

public class ClosureAndPair {
  private static class Closures<T, U> {
    BiFunction<T, U, Pair<T, U>> cons = Pair::new;
    Function<Pair<T, U>, T> car = Pair::getT;
    Function<Pair<T, U>, U> cdr = Pair::getU;
  }

  private static class Pair<T, U> {
    private T t;
    private U u;
    Pair(T t, U u) { this.t = t; this.u = u; }
    public T getT() { return t; }
    public U getU() { return u; }
  }
}

java8 以降の関数型の表現だけでできないかな? と思いつつ、オブジェクト指向を捨て切れない😇

print out

.java

public class ClosureAndPair {

  /* omit */

  public static void main(String... args) {
    Closures<Integer, Pair<String, Integer>> closures = new Closures<>();
    Pair<Integer, Pair<String, Integer>> pair = closures.cons.apply(1, new Pair<>("A", 0));

    // get "A"
    System.out.println(
        new Closures<String, Integer>().car.apply(closures.cdr.apply(pair))
    );

   // 実はこれで十分なはず
   System.out.println(pair.getU().getT());
  }
}

回りくどい 😇

Pair の Interface 化

メソッド数が1つを超えるため、関数型インタフェースの条件は満たしていません.

.java

public class Closures<T, U> {
  private interface Pair<T, U> { T getT(); U getU(); }
  private BiFunction<T, U, Pair> cons = (t, u) -> new Pair() {
    @Override
    public T getT() { return t; }
    @Override
    public U getU() { return u; }
  };
  // car, cdr 省略
}

cons の中で初めて実装しているだけで、どのみち実装は必要で、
回りくどさも変わりません.

Scala

タプルっぽく

.scala

case class Pair[T, U](t: T, u: U)

def cons[T, U](a: T, b: U): Pair[T, U] = Pair(a, b)
def car[T, U](pair: Pair[T, U]): T = pair.t
def cdr[T, U](pair: Pair[T, U]): U = pair.u

case class に関しては「ペア」を新しく作りたかっただけなので built-in のタプルでもよかったです.

しかし、ペアを構成する関数を返すというより、ペアそのものを返しています 🤔

クロージャっぽく

できれば cons には関数を返してもらいたい.

.scala

def cons[T, U](a: T, b: U) = (p: (T, U) => _) => p(a, b)
def car[T, U](p: ((T, U) => _) => _) = p((a: T, b: U) => a)
def cdr[T, U](p: ((T, U) => _) => _)  = p((a: T, b: U) => b)

でもこれだと、

.scala

val pairPair = cons(cons(0, 1), cons('i, 'j))
car(cdr(pairPair)) // Type Mismatch

入れ子 cons をパラメータに渡せない. pのタイプが定義できないからでしょう.

型安全ではないやり方

.scala

def cons(a: Any, b: Any) = (p: (Any, Any) => Any) => p(a, b)
def car(p: Any) = p.asInstanceOf[Any => Any]((a: Any, b: Any) => a)
def cdr(p: Any) = p.asInstanceOf[Any => Any]((a: Any, b: Any) => b)

なんだって渡せてしまうので、実行するまでには、型の間違いに気づけません 😇

print out

.scala

// get 'a
car(cons('a, 'b))
// get 'b 
cdr(cons('a, 'b))
// get 's
cdr(car(cons(cons(99, 's), cons(100, 't))))

おわりまして

後日また修正を入れるかもしれません.

よりシンプルな書き方がありましたらコメントにどうぞ.

以上