« first day    last day (298 days later) » 

1:54 AM
@LeviMorrison don't try to support const. You can't fully support it, so partially supporting it is just lunacy :-)
 
Yeah, if you change something in map or filter it could invalidate everything.
 
@GuilhermeBlanco strongly disagree there. I think you need a distinction (and more than a runtime one) between mutable and immutable structures
hence no need for Tuple, as a Tuple is just an immutable Vector.
Now, it could be a constructor argument (if it's mutable or not), but not sure if I like that off the top of my head
@LeviMorrison I think that's why === is enough. Once you go ==, then you can't hold anything constant (even in an immutable)...
 
@ircmaxell Needs to be callable; === is too restrictive and == is too loose.
At least imo ^^
 
well, for contains, sure
but in general, internally into the structure, == is too loose, since values can change over time
example
imagine a Set implementation
$set->insert(new Foo(1));
$foo2 = new Foo(2);
$set->insert($foo2);
$foo2->make(1); // let's say this adjusts the state to be identical to `new Foo(1)
the insert worked fine, but now you've got an invalid set with a duplicated element
Off to bed, good night!
 
2:17 AM
If we had generics like Hack one could say that strictly speaking, a Vector is a fixed-size Map<int,V>.
 
2:35 AM
I read through this thread a couple minutes ago and it's pretty intriguing. I wanted to chime in about a few things related to Hack's collection framework.
The goal of the "Collection" interface in Hack is to represent element storage without being specific about the kind of collection, hence why it has the add(), addAll(), and items() methods (and erase() which should be implemented soon). The "Collection" interface deals strictly with "items", whereas most of the rest of Hack's collections framework deals with values and keys.

The idea is that items()-style iteration should represent what you need to reconstruct the collection, and for items() to output things in the same format that add() and addAll() expect them. For Vectors you really on
map(), filter(), and friends all live on the Iterable interface. The idea here is that these methods should work on any Iterable, not just collection classes. For Hack it would be nice at some point in the future to have map(), filter(), and friends working with generators or other sequence-like things that are not necessarily collections. map(), filter(), and friends also mirror how array_map(), array_filter(), etc work in the sense that the operation is only applied based on the values, and the keys just goes along for the ride. There are also methods like mapWithKey() and filterWithKey()
I also noticed there was some confusion about "Const" and "Imm" (sorry our documentation doesn't cover this well, I need to make it better). Each concrete collection class is either inherently mutable (Vector, Map, Set) or inherently immutable (ImmVector, ImmMap, ImmSet). Both mutable collection classes _and_ immutable collection classes implement the relevant "Const" interface (for example, Vector and ImmVector both implement ConstVector).

The idea behind the "Const" interfaces is to allow a function to say "I don't plan to mutate the collection that is passed to me, but I don't care whet
 
3:04 AM
@DrewParoski Are const checks used at all in hh_client yet?
Also, I am curious how often these collections in their various forms are used at Facebook.
Historically there has been little to no interest in explicitly immutable collections in PHP, so I'm wondering if they have value at FB or if they are just an exercise ^^
 
3:37 AM
@LeviMorrison Right now Hack collections are getting used a fair amount in FB's codebase, though PHP arrays are still used more (PHP array -> Hack collection migration is something that's being worked on actively this year). Immutable collections are not used a ton yet, but that's mostly because they were only recently added and ready to use.

Immutable collections have a few benefits. First, since collections behave like objects and do not have copy-on-write, immutable collections come in handy when a given class needs to pass a collection it owns somewhere but doesn't want it to get mutat
 
Basically immutable casts itself.
 
Right.
Second, immutable collections can be stored into and retrieved from APC more efficiently. FB's codebase makes heavy use of APC for caching data, so this matters to us probably more than it would for other PHP codebases.
Third, Imm* collection classes and the Const* collection interfaces support covariance on their type parameters. In other words, you can pass an ImmVector<C> to a function that's expecting an ImmVector<B> (where class C derives from B). Likewise, you can pass a Vector<C> or an ImmVector<C> to a function that's expecting a ConstVector<B>.
 
But immutables don't?
 
(It's not safe to pass a Vector<C> to a function foo() expecting a Vector<B>, because foo() might try to insert a B into the Vector, which would violate type safety.)
"But immutables don't?"
I'm not sure I understand the question.
 
lol, you have to make it a separate chat entry.
 
3:42 AM
I'm a stackoverflow chat n00b :)
 
It's okay ^^
Assuming C is a subtype of B.
function (Vector<B>)
and if you pass Vector<C> that violates type safety if you modify the parameter at all add or set a value
 
Yes, and so hh_client will yell if you try to do that.
 
I think I get it.
 
function foo(Vector<B> $vec) { $vec->add(new B()); }
function bar(Vector<C> $vec) {
  foo($vec);
  foreach ($vec as $val) {
    // Uh oh, $val might not be an instance of C because foo() can insert B's
  }
}
Gonna drive home, will be back online in an hour or so.
 
I personally understand the idea and value of immutable objects but I'm just not sure about general adoption.
Okay, I'll probably be in bed by then.
 
3:52 AM
Yeah, I could see how a lot of codebases probably wouldn't use immutable collections a ton. However, if you're going to have containers that are passed around like objects (i.e. no copy-on-write) and you want these containers to completely replace PHP arrays, then I'd argue it might come in handy to have immutable collections at some point as a codebase grows and is refined and optimized over time.
 
4:44 AM
Okay, I have committed some really basic stuff up to: github.com/morrisonlevi/SPL-Collections
I've purposefully avoided creating any particular exceptions (just throwing \Exception)
There are two iterators to help with map and filter, and three collections Vector, Set and Map (the latter two are interfaces).
Let me know what you think when you get a chance to look at it.
 
 
9 hours later…
1:42 PM
so reading through, I don't care for the const base class/interface concept
 
2:08 PM
Yeah, I don't think so either. I think we need something between the current SPL and something full-blown and enterprisey like HH Collections.
 
personally, I think you basically hit the mark with ardent
 
I think certain bits might need to be removed.
Slightly smaller API.
 
perhaps
@DrewParoski $vec->add(new B()); should throw an exception (or some other type error). Because the Vector is typed against C. So trying to add B to it, even though locally allowable, breaks the constraints on the instance. Which is why you can't solve all type interactions at compile time (nor should you try)
 
The Vector impl I rewrote last night is a bit nicer than what is in Ardent, too.
As is the FilteringIterator.
 
that works? Isn't there a type conflict with the private inner?
 
2:15 PM
Trait's are copy/pasta
 
/me sighs
 
Any private on trait is a private on the class that uses it.
 
conceptually, what's the difference between enumerable and collection?
 
Enumerable has an external iterator, a Collection has either an external iterator or is an iterator.
At least with the few variants I've played with a LinkedList is better utilized as an Iterator than an IteratorAggregate, so Collection allows for that kind of thing. All it cares about is that you can iterate over it.
Enumerable also requires you to return an Enumerator, not a generic Iterator.
(for Collection chaining, basically)
 
So, that's actually something I've been thinking about lately
I'm not sure it makes sense to implement LinkedList, unless you also expose the node classes...
few variants I've played with a LinkedList is better utilized as an Iterator than an IteratorAggregate <-- can you elaborate more?
 
2:22 PM
LinkedLists allow for effective insertion in places in the middle, unlike a Vector.
 
yes
 
If you track an internal pointer that matches the current position you can easily achieve this.
Turns out that's exactly what an iterator is doing.
 
but why is iterator the right abstraction for that? Why not have the node directly exposed, and while ($node = $node->next()) { ?
meaning, why should the pointer be internal?
 
So you don't screw up everything?
Basic encapsulation.
 
You can encapsultate while exposing the node
 
2:24 PM
No, you can't. If they modify the node it will break everything.
 
I'm not saying make $node->next public. But $node->insertAfter(Node $node)
 
If this was C++ I'd expose it as const everything, certainly.
 
why const even?
 
If they change anything it breaks the structure.
 
@LeviMorrison what structures will it break?
 
2:26 PM
LinkedList
If we want to go down an entirely different road and define LinkedList as a Node with cons, then maybe that would make sense.
But as an Array-like thingy... doesn't make sense.
 
class LinkedList {
    protected $head;
    public function head() {
        return $head;
    }
    public function setHead(LinkedListNode $node) {
        $this->head = $node;
    }
}

class LinkedListNode {
    public $value;
    private $next;
    public function next() {
        return $this->next;
    }
    public function insertAfter(LinkedListNode $node) {
        $this->next = $node->next;
        $node->next = $this;
    }
}
@LeviMorrison And that's sort of my point, I don't think it makes sense to make it "array like"
 
I'll sit it on the shelf and think about it.
 
class LinkedList {
    protected $head;
    public function head() {
        return $head;
    }
    public function setHead(LinkedListNode $node) {
        if ($this->head && $this->head !== $node->next) {
            throw new RuntimeException("Trying to detach head. Bad developer. No Donut");
        }
        $this->head = $node;
    }
}

class LinkedListNode {
    public $value;
    private $next;
    public function next() {
        return $this->next;
    }
    public function insertAfter(LinkedListNode $node) {
fixed bug
 
@LeviMorrison I just don't see the value exposing an array-like interface to linkedlist, when that's the least optimal implementation of an array-like interface.
iteration interface, ok, that I can get behind. But even then, you have this weird mix of state mutation functions on one object...
 
2:32 PM
It has the benefit of knowing how big it is. Turns out that's pretty common and a huge help to efficiency.
 
In most cases, if you need to know the definite size, a linked list is the wrong structure
that's sort of the point of the structure IMHO. It can be arbitrary size, and it makes no difference, since you're only dealing with 2 nodes at a time (current, and next)
if you need more than that, a better sturcture should be used
 
LinkedLists are commonly used to work on both ends (head and tail)
Add that functionality to your linked list and you get something pretty similar to what I already have.
 
Well, in that case it should be a DLL, no?
 
It is.
 
2:52 PM
but you still don't get an array-like syntax...
no?
 
You do have array syntax in my impl, it's just not the only way.
 
@LeviMorrison Well, I prefer not haivng array syntax, mainly because random-access is actually very expensive...
 
@ircmaxell Only if truly random; the internal pointer moves to the index.
 
@LeviMorrison well, it's always expensive, since you need to start at 0 every time.
 
From what I've observed, even in normal arrays you rarely have random access, and I'd guess if you reached for a linked list it'd be even less random.
 
2:55 PM
unless you're also caching the position
 
@ircmaxell Wrong.
Yes, I am caching the position.
 
@LeviMorrison you can't do that arbitrarally though, since modification can change that
 
@ircmaxell It's just a bit of complexity; still works.
 
So, here's where I'm coming from
Boost doesn't really implement any graphs.
It gives you tools so that you can assemble one
I think for a few structures, it makes sense supporting a core implementation (hash map, map, array, set), but for others (DLL, LL, tree, graph), the implementation details become important enough that the tooling should be the only thing necessary
a default DLL implementation hides too much IMHO.
 
Perhaps. At the moment @Guilherme and I are focusing on Vector, Set and Map and the supporting infrastructure.
 
3:04 PM
++
 

« first day    last day (298 days later) »