Skip to content

Instantly share code, notes, and snippets.

@mathiasverraes
Created November 17, 2014 09:13
Show Gist options
  • Save mathiasverraes/4b76822c6be565a092f7 to your computer and use it in GitHub Desktop.
Save mathiasverraes/4b76822c6be565a092f7 to your computer and use it in GitHub Desktop.
Lambdalicious blog post
<?php
require_once __DIR__ . 'path/to/src/Verraes/Lambdalicious/load.php';
assert(
isatom(@my_atom)
);
atom(@my_atom);
assert(
isatom(my_atom)
);
atom(@a, @b, @c, @d);
assert(
islist([a, b, c])
);
assert(isequal(
cons(d, [a, b, c]),
[d, a, b, c]
));
assert(isequal(
cons(a, cons(b, cons(c, []))),
[a, b, c]
));
assert(isequal(
head([a, b, c]),
a
));
assert(isequal(
tail([a, b, c]),
[b, c]
));
function half($x){ return divide($x, 2);}
assert(isequal(
half(6),
3
));
atom(@half);
assert(isequal(
call(half, [6]),
half(6)
));
$half = function($x) { return divide($x, 2);};
assert(isequal(
$half(3),
call($half, [3])
));
$halves1 = function($list) use(&$halves1) {
return
cons( // create a new list consisting of:
divide(head($list), 2), // the half of the first element
$halves1(tail($list)) // the halves of the remaining elements
);
};
$halves2 = function($list, $acc = []) use(&$halves2) {
return
isempty($list) ? $acc : // return $acc when we're done picking off items
$halves2( // Recurse
tail($list),
cons( // Our new $acc will be our newly calculated half, followed by the old $acc
divide(head($list), 2),
$acc
)
);
};
$halves3 = function($list, $acc = []) use(&$halves3) {
return
isempty($list) ? reverse($acc) : // Reversing $acc at the last moment
$halves3(
tail($list),
cons( // This is where our halved heads end up in the wrong order
divide(head($list), 2),
$acc
)
);
};
assert(isequal(
$halves3([2, 4, 6]),
[1, 2, 3]
));
$halves4 = function($half, $list, $acc = []) use(&$halves4) { // Take $half as an argumet
return
isempty($list) ? reverse($acc) :
$halves4(
$half, // Don't forget to keep passing $half along to $halves4
tail($list),
cons(
$half(head($list)), // Using our injected $half function
$acc
)
);
};
assert(isequal(
$halves4($half, [2, 4, 6]),
[1, 2, 3]
));
$map = function($function, $list, $acc = []) use(&$map) { // Take $function as an argument
return
isempty($list) ? reverse($acc) :
$map( // Recurse over map
$function, // Passing $function along to the next call of $map
tail($list),
cons(
$function(head($list)), // Using our injected $function
$acc
)
);
};
assert(isequal(
$map($half, [2, 4, 6]), // Map $half over the list
[1, 2, 3]
));
$halfMaker = function() {
return function($x) { return divide($x, 2);}; // make a new function and return it
};
$half2 = $halfMaker();
assert(isequal(
$half2(8),
4
));
$divisionMaker = function($y) {
return function ($x) use ($y) {
return divide($x, $y);
};
};
$third = $divisionMaker(3);
assert(isequal(
$third(9),
3
));
$partial = function($f, $y) {
return function($x) use($f, $y) {
return $f($x, $y);
};
};
$third2 = $partial(divide, 3);
assert(isequal(
$third2(9),
3
));
$half3 = divide(__, 2); // returns a function $f($x){ return divide($x, 2); }
$increment = add(1, __); // returns a function $f($y){ return add(1, $y); }
assert(isequal(
$half(8), 4
));
assert(isequal(
$increment(5), 6
));
$halfAndIncrementMaker = function($half3, $increment) {
return function($x) use ($half3, $increment) {
return $increment($half3($x));
};
};
$halfAndIncrement = $halfAndIncrementMaker($half3, $increment);
assert(isequal(
$halfAndIncrement(10), 6
));
$compose = function($f, $g) {
return function($x) use ($f, $g) {
return $g($f($x));
};
};
$halfAndIncrement = $halfAndIncrementMaker($half3, $increment);
assert(isequal(
$halfAndIncrement(10), 6
));
$half5 = divide(__, 2);
$greaterThanSix = gt(__, 6);
$calculate = pipe( // pipe returns a new function
map($half5, __), // Half all the elements of a list
filter($greaterThanSix, __), // Keep only the elements of the previous result that are greater that 6
reduce(add, __, 0) // Add up all the filtered elements, starting with 0
);
assert(isequal(
$calculate([10, 20, 30]),
25
));
$calculate2 = pipe(
map(divide(__, 2), __),
filter(gt(__, 6), __),
reduce(add, __, 0)
);
$calculate3 = pipe(
map(divide(__, 2), __),
dump,
filter(gt(__, 6), __),
dump,
reduce(add, __, 0)
);
@crodrigues
Copy link

Love the project! I do hope The PHP Group addresses your concerns about tail call optimization. A few thoughts came to mind while looking over your blog post & the code. First was trivial on line 2 after DIR, there's a missing directory separator there before "path"

The other was regarding the first recursive iteration of halves, starting at line 54. You went from that to an accumulator, but I figured you could just take the following route on the terminal iteration (I haven't cloned the repo yet just found it, so implemented these functions real quickly to test). Also avoids call to reverse.

<?php
    function divide($a, $b)
    {
        return ((is_numeric($a) && is_numeric($b) && $b) ? $a / $b : 0);
    }

    function head($a)
    {
        return (isempty($a) ? NULL : array_shift($a));
    }

    function tail($a)
    {
        return (isempty($a) ? [] : array_slice($a, 1));
    }

    function cons($a, $b)
    {
        return array_merge([$a], $b);
    }

    function isempty($a)
    {
        return ( ! (is_array($a) && $a));
    }

    $halves1 = function($list) use(&$halves1) {
        return isempty($list) ? [] : cons( // create a new list consisting of:
            divide(head($list), 2), // the half of the first element
            $halves1(tail($list)) // the halves of the remaining elements
        );
    };

    var_dump($halves1([2, 4, 6])); // array(3) { [0]=> int(1) [1]=> int(2) [2]=> int(3) }

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment