implement fans & spreads

[jonsterling]

In addition to wellfounded trees (as in Data.Tree) we will want to support non-wellfounded trees (i.e. trees of infinite depth). There are two principle kinds of non-wellfounded trees:

• Spreads are infinitely deep and infinitely broad
• Fans are infinitely deep, but finitely broad

[jplatte]

So, this has been sitting here a while now. I would work on it myself, but I don't feel comfortable enough in my FP skills to tackle this laziness stuff where the compiler can't tell me whether what I'm doing is actually correct.

@jonsterling Is there anything one could do to re-draw your interest to this?

[jonsterling]

@jplatte Ah, I am very sorry; I have been traveling and working on a number of very important (to me) things.

I'm hoping that I will be able to resume work on this project soon, but I cannot make any guarantees (have a few papers I'm working on, and also grad school applications).

[jplatte]

There's nothing to be sorry about; thanks for the quick answer.

[parsonsmatt]

So a rose tree is 'just' Cofree Array. Would it makes sense to say that a Fan is Cofree (Compose Array Lazy) and a Spread is Cofree Data.List.Lazy.List?

[parsonsmatt]

I've got an implementation of a spread based on Cofree List here.

I think the Cofree implementation might be better than handrolling one -- Cofree in purescript-free uses a trampoline under the hood, which probably handles the recursion stack-safely better than I could.

Lazy lists are going to be OK for certain applications of spreads, but I can also see Sequence and IntMap working better depending on the random access properties.

I also finished out the code for Fan that was in your branch @jonsterling here

[jonsterling]

@parsonsmatt Sweet, this sounds cool! Might be nice to try using Sequence too as you mention... Probably IntMap could work out well in the case of fans...

[parsonsmatt]

cool!

What are some use cases for a spread/fan? I'm not entirely familiar with them as data structures, so I don't know how to write tests or benchmarks to determine how well the implementations work for their intended uses.

[jonsterling]

@parsonsmatt I'm not sure about practical use-cases; the initial use-case was to represent sets of real numbers, etc.; another example would be to represent non-wellfounded syntax (e.g. derivations in infinitary logic).

[jplatte]

My use case for fans is that I want to represent possible moves of a piece in a game similar to chess. It's on a hexagonal board, so there are six directions from each tile instead of just four, but it's the same principle. I need a tree structure because there is one piece that can move around other pieces, but has a limited number of tiles it can cover in one move (so I can easily invalidate a whole branch of movement parts when there is a piece blocking the way). I need it to be lazy because there are pieces of which the movement is only restricted by board size and other pieces (the board size is hardcoded so I don't strictly have to encode the "infinite tiles into a certain direction" path as an infinitely deep tree, but it seems appropriate).

[jonsterling]

@jplatte what a cool use-case!