Тугай
Новичок
Топик в "лес" уходит
В "Хаскелах" есть типовой полиморфизм - это похоже на перегрузку методов и на полиморфизм ООП, но записывается подругому.
Вот, например :
Код:
<?php
/*
Сортировака с использованием бинарного дерева
Hope vs PHP
*/
/*
data tree == empty ++ leaf(num) ++ node(tree#num#tree);
dec Treesort : list(num) -> list(num);
dec MakeTree : list(num) -> tree;
dec Flatten : tree -> list(num)l;
--- MakeTree(nil) <= empty;
dec Insert : num # tree -> tree;
--- MakeTree(n::rest) <= Insert(n, MakeTree(rest));
--- Insert(n, empty) <= leaf(n);
--- Insert(n, Oldleaf & leaf(m)) <=
if n =< m
then node(empty, , Oldleaf)
else node(Oldleaf, n empty);
--- Insert(n, node(left, value, right)) <=
if n =< value
then node(Insert(n, left), value right)
else node(left, value, Insert(n, right));
--- Flatten(empty) <= nil;
--- Flatten(leaf(n)) <= [n];
--- Flatten(left, value, right)) <=
Flatten(left)<>(value::Flatten(right));
let UnsortedList <= [5,2,1,9];
--- Treesort(UnsortedList) <= Flatten(MakeTree(UnsortedList));
*/
abstract class Tree
{
public function insert($m) {}
public function flatten() {}
}
class EmptyTree extends Tree
{
public function insert($m)
{
return new LeafTree($m);
}
public function flatten()
{
return [];
}
}
class LeafTree extends Tree
{
public $num;
function __construct($n)
{
$this->num = $n;
}
public function insert($m)
{
if ( $m > $this->num ) {
return new NodeTree( new EmptyTree(), $this->num, new LeafTree($m) );
} else {
return new NodeTree( new LeafTree($m), $this->num, new EmptyTree() );
}
}
public function flatten()
{
return [$this->num];
}
}
class NodeTree extends Tree
{
public $leftTree;
public $num;
public $rightTree;
function __construct($lt, $n, $rt)
{
$this->leftTree = $lt;
$this->num = $n;
$this->rightTree = $rt;
}
public function insert($m)
{
if ( $m > $this->num ) {
$this->rightTree = $this->rightTree->insert($m);
} else {
$this->leftTree = $this->leftTree->insert($m);
}
return $this;
}
public function flatten()
{
return array_merge( $this->leftTree->flatten(), [$this->num], $this->rightTree->flatten() );
}
}
function makeTree($list)
{
/*
$tree = new EmptyTree();
foreach($list as $l) {
$tree = $tree->insert($l);
}
return $tree;
*/
return array_reduce($list, function ($t, $l) { return $t->insert($l); }, new EmptyTree());
}
print_r(makeTree([5,2,1,9])->flatten()); // [1,2,5,9]
Последнее редактирование:
