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();
    }
}

んで、こっちは前述の単方向リストを使ったzipper。
setメソッドとかあるけどイミュータブル。