PHPでイミュータブルな単方向リストとzipper
何か使い道があるのかと聞かれてもまあ特にないんだけど書いた。
<?php interface ILinkedList extends Countable, IteratorAggregate { function isEmpty(); function nth($i, $default_val = null); function car(); function cdr(); function cons($elt); function reverse(); function toArray(); function map($callback); } class LinkedList implements ILinkedList { protected $car, $cdr; function __construct($elt, ILinkedList $rest) { list($this->car, $this->cdr) = func_get_args(); } function isEmpty() { return false; } function car() { return $this->car; } function cdr() { return $this->cdr; } function cons($elt) { return new self($elt, $this); } function nth($i, $default_val = null) { return $i === 0 ? $this->car : $this->cdr->nth($i - 1, $default_val); } function count() { return 1 + count($this->cdr); } function getIterator() { return new LinkedListIterator($this); } function toArray() { $ret = array(); $current = $this; while (!$current->isEmpty()) { $ret[] = $current->car(); $current = $current->cdr(); } return $ret; } static function fromArray(Array $arr) { $current = NullLinkedList::it(); while($arr) { $current = new self(array_pop($arr), $current); } return $current; } function reverse() { return self::fromArray(array_reverse(self::toArray())); } function map($callback) { if (!is_callable($callback)) throw new InvalidArgumentException('argument must be callable'); return new self(call_user_func($callback, $this->car), $this->cdr->map($callback)); } } class NullLinkedList implements ILinkedList { private function __construct() { } static function it() { static $obj = null; return $obj ? $obj : $obj = new self; } function isEmpty() { return true; } function nth($i, $default_val = null) { return $default_val; } function car() { throw new BadMethodCallException; } function cdr() { throw new BadMethodCallException; } function count() { return 0; } function getIterator() { return new LinkedListIterator($this); } function toArray() { return array(); } function reverse() { return $this; } function cons($elt) { return new LinkedList($elt, $this); } function map($callback) { return $this; } } class LinkedListIterator implements Iterator { protected $head, $current, $i = 0; function __construct(ILinkedList $list) { $this->head = $this->current = $list; } function current() { return $this->current->car(); } function next() { $this->i++; $this->current = $this->current->cdr(); } function rewind() { $this->i = 0; $this->current = $this->head; } function key() { return $this->i; } function valid() { return !$this->current->isEmpty(); } }
副作用を持たないリスト。
car, cdrメソッドとかあるようにlispのconsセルをイミュータブルにした感じ。
<?php include_once dirname(__FILE__) . '/linkedlist.php'; class Zipper { protected $left, $right; function __construct(ILinkedList $left, ILinkedList $right) { list($this->left, $this->right) = func_get_args(); } function next() { return new self($this->left->cons($this->right->car()), $this->right->cdr()); } function prev() { return new self($this->left->cdr(), $this->right->cons($this->left->car())); } function insert($elt) { return new self($this->left, $this->right->cons($elt)); } function remove() { return new self($this->left, $this->right->cdr()); } function get() { return $this->right->car(); } function set($elt) { return new self($this->left, $this->right->cdr()->cons($elt)); } function eos() { return $this->right->isEmpty(); } }