lazy list

lazy.php

<?php

class Lazy
{
	public static function isClosure ($obj)
	{
		return is_object($obj) && $obj instanceof Closure;
	}

	/**
	 * 評価
	 */
	public static function force($obj)
	{
		if(!self::isClosure($obj)) {
			return $obj;
		}
		return call_user_func($obj);
	}

	/**
	 * $lazyConsから$n個とりだす
	 */
	public static function take($n, $lazyCons)
	{
        if (LazyCons::isEmpty($lazyCons)) {
            return $lazyCons;
        }

		return new LazyCons(
			function () use ($lazyCons) {
                return $lazyCons->car();
            },
			function () use ($n, $lazyCons) {
				if (0 < ($n - 1)) {
					return Lazy::take($n - 1, $lazyCons->cdr());
				} else {
					return null;
				}
			}
		);
	}

	/**
	 * $lazyConsから$n個おとす
	 */
	public static function drop($n, $lazyCons)
	{
        if (LazyCons::isEmpty($lazyCons)) {
            return $lazyCons;
        }

		while ($n > 0) {
			$lazyCons = $lazyCons->cdr();
			if (LazyCons::isEmpty($lazyCons)) {
				return $lazyCons;
			}
			$n -= 1;
		}

		return $lazyCons;
	}

	/**
	 * map
	 */
	public static function map($f, $lazyCons)
	{
        if (LazyCons::isEmpty($lazyCons)) {
            return $lazyCons;
        }

		return new LazyCons(
			function () use ($f, $lazyCons) {
                return call_user_func($f, $lazyCons->car());
            },
			function () use ($f, $lazyCons) {
				return Lazy::map($f, $lazyCons->cdr());
			}
		);
	}

	/**
	 * filter
	 */
	public static function filter($f, $lazyCons)
	{
        while (true) {
            if (LazyCons::isEmpty($lazyCons)) {
                return $lazyCons;
            }
            $pred = call_user_func($f, $lazyCons->car());
            if ($pred) {
                break;
            }
            $lazyCons = $lazyCons->cdr();
        }

		return new LazyCons(
			function () use ($lazyCons) {
                return $lazyCons->car();
            },
			function () use ($f, $lazyCons) {
				return Lazy::filter($f, $lazyCons->cdr());
			}
		);
	}

	/**
	 * reduce
	 */
	public static function reduce($f, $val, $lazyCons)
	{
        if (LazyCons::isEmpty($lazyCons)) {
            return $val;
        }

        $car = $lazyCons->car();
        $newVal = call_user_func($f, $car, $val);

        return Lazy::reduce($f, $newVal, $lazyCons->cdr());
	}


	/**
	 * $lazyConsを配列に変換する
	 */
	public static function toArray(LazyCons $lazyCons)
	{
		$result = [];
		while (!LazyCons::isEmpty($lazyCons)) {
			$result[] = $lazyCons->car();
			$lazyCons = $lazyCons->cdr();
		}
		return $result;
	}

	/**
	 * 繰り返し
	 */
	public static function repeat($x)
	{
		return new LazyCons(
            function () use ($x) {
                return $x;
            },
            function () use ($x) {
                return Lazy::repeat($x);
            }
        );
	}

	/**
	 * 初期値n, ステップmの無限等差数列
	 */
	public static function iota($n, $m)
	{
		return new LazyCons(
            function () use ($n) {
                return $n;
            }, 
            function () use ($n, $m) {
                return Lazy::iota($n + $m, $m);
            }
        );
	}

	/**
	 * フィボナッチ数列
	 */
	public static function fib()
	{
        return Lazy::_fib(0, 1);
    }

	public static function _fib($n, $m)
	{
		return new LazyCons(
            function () use ($n) {
                return $n;
            },
            function () use ($n, $m) {
                return Lazy::_fib($m, $n + $m);
            });
	}
}

class Cons
{
	public $car;
	public $cdr;

	public function __construct($car, $cdr) {
		$this->car = $car;
		$this->cdr = $cdr;
	}

	public function car() {
		return $this->car;
	}
	public function cdr() {
		return $this->cdr;
	}
}

class LazyCons extends Cons
{
	public function __construct($car, $cdr) {
		// car, cdr部はそれぞれ評価されないようにclosureでなければならない
		if (!(Lazy::isClosure($car) or is_null($car))) {
			throw new LogicException("car部が不正");
		}
		if (!(Lazy::isClosure($cdr) or is_null($cdr))) {
			throw new LogicException("cdr部が不正");
		}
		return parent::__construct($car, $cdr);
	}

	public function car() {
		return Lazy::force($this->car);
	}

	public function cdr() {
		return Lazy::force($this->cdr);
	}

	public static function isEmpty($lazyCons) {
		return is_null($lazyCons);
	}
}

class LazySeq implements Iterator
{
	private $key;
	private $lazyCons;

	public function __construct(LazyCons $lazyCons)
	{
		$this->lazyCons = $lazyCons;
		$this->key = 0;
	}

	public function rewind()
	{
	}

	public function key()
	{
		return $this->key;
	}

	public function current()
	{
		return $this->lazyCons->car();
	}

	public function next()
	{
		$this->lazyCons = $this->lazyCons->cdr();
	}

	public function valid()
	{
		return !LazyCons::isEmpty($this->lazyCons);
	}

	public function take($n)
	{
		$this->lazyCons = Lazy::take($n, $this->lazyCons);

		return $this;
	}

	public function drop($n)
	{
		$this->lazyCons = Lazy::drop($n, $this->lazyCons);

		return $this;
	}

	public function map($f)
	{
		$this->lazyCons = Lazy::map($f, $this->lazyCons);

		return $this;
	}

	public function filter($f)
	{
		$this->lazyCons = Lazy::filter($f, $this->lazyCons);

		return $this;
	}

	public function reduce($f, $val)
	{
		$result = Lazy::reduce($f, $val, $this->lazyCons);

		return $result;
	}

	public function toArray()
	{
		return Lazy::toArray($this->lazyCons);
	}

	public function first()
	{
		return $this->lazyCons->car();
	}

	public function rest()
	{
		return $this->lazyCons->cdr();
	}
}

//----------------------------------------------

// 0,1,2,3...の無限リスト
// $lazySeq = new LazySeq(Lazy::iota(0, 1));

// $sum =
//      // 無限リストから
//      $lazySeq
//      // 偶数のみ取り出して
//      ->filter(function ($a) {
//          return 0 == ($a % 2);
//      })
//      // 2乗して
//      ->map(function ($a) {
//          return $a * $a;
//      })
//      // 10個とりだし
//      ->take(10)
//      // 合計を求める
//      ->reduce(function ($a, $b) {
//          return $a + $b;
//      }, 0);

// echo "sum: " . $sum . "\n\n";

// フィボナッチ数列

$fibLazySeq = new LazySeq(Lazy::fib());
var_dump($fibLazySeq->drop(40)->first());