Our story today begins with the rather unmotivated type
eval ( )
Lets construct a value of the type,
eval f = xs xs = ($ xs) f
Plugging the list functor in, we have:
It becomes a little clearer from looking at the function that what we're doing is creating a list where each value in the list is a function of the list itself. The base case would be the constant function.
Creating a value of the argument to eval we have something like:
arg = [\list -> list !! , const , \list -> list !! + list !! + list !! , const , const , const ]
If we eval arg , it provides arg as the argument to each index in arg . If the graph isn't acyclic we're going to <<loop>>; this is very reminiscent of a spreadsheet.
Thus eval provides a method of traversal of a directed acyclic graph when the functor is a list. Among the many algorithms related to graph traversal I'm going to pick topological sort.
So each element in the list has a list of dependencies.
= [[[ -> [
topSort a = res
indices = [0..]
res = sortBy comparator $ indices (eval a)
comparator x y = ( ( x)) ( ( y))
We evaluate the dependencies and tag them with their indices. Then we sort them by the number of dependencies. The algorithm works because for any two nodes u and v, if there is a directed path from u to v, the number of dependencies associated with u is strictly greater than that of v.
What remains is to construct sample adjacency lists for which we will need to construct a list of dependencies:
ref = (!!)
deps l = f ( ) l
f g e = (++) <$> g <*> (e:) (ref e)
adj1 = [deps [, , ], , deps [, ], ]
Full code at https://github.com/joshcc3/HaskellExperiments/blob/master/interestingTypes/Loeb.hs