Circular Programming
Foldl (haskell terminology) is the same as doing a scan and then taking the last element. Iogii provides a builtin called foldr that works similarly to iterate but from right to left and then taking the first element. The advantage of this as opposed to foldl is you could actually compute the answer without considering all elements, using laziness. Suppose you wanted to inefficiently find the square root of a number. You could look for the first element such that (x+1) squared is greater than the target. Normally I would just filter and then take the first, but for this example let's do it without filter.
26 wholes 1+ dup * < not 0 foldr wholes ifElse > → 5
It computes the answer even though we are essentially folding on an infinite list.
Fold Padding
This isn't something you should need to think about in iogii, but if you are trying to use these techniques in Haskell you may run into a gotcha that iogii takes care of automatically, you can still use the techniques in Haskell but you may need to manually pad your lists.
Let's look at how foldr and meld work, they start from the right and move to the left, but how long is the starting list? Folds manually pad their yielded args with the initial value and make the list infinite rather than just append it to the end. So the fold: initial foldr block is defined as:
ans initial pad tail block set ans head
For example:
ans 0 pad tail 1,2,3+ set ans head → 6
Using append wouldn't work, it would create a circular dependency:
ans 0j append tail 1,2,3+ set ans head # Stack Overflows
pad isn't special, in fact you accomplish the same thing by like this:
1,2,3 Iterate tail > head 10 keep → [1,2,3,0,0,0,0,0,0,0]
And iterate isn't special it is just:
ans block initial cons set ans
So that would be:
ans tail 1,2,3 Cons set ans head 10 keep → [1,2,3,0,0,0,0,0,0,0]
Or in Haskell, pad could be defined as so:
pad a v = h : pad t v
where
~(h,t) =
if null a
then (v,[])
else (head a,tail a)
The purpose of pad is essentially just to short circuit how vectorization (zipWith in Haskell) checks for the end of a list (by truncating when either arg is empty. This would create a direct circular dependency when checking the length of the padded arg in our foldrs, now it can immediately return true.
You don't really need to know about this but I find it very beautiful that all of computation can be built off of just a few simple vectorized primitives, cons, head, tail, if, nil. It would be worth writing more about this in a context outside of iogii.
Superpad
Suppose we wanted to get the tails of each row in a 2d list (similarly to how our manual pad was written), the code would be the exact same as for a 1d list:
1,2,,3,4 J Iterate tail > 4 Take → [[[1,2],[2],[],[]],[[3,4],[4],[],[]]]
No problem, but if you try this as a circular program in Haskell it will timeout. The reason is because the tail operation is vectorized inside of a circular program. Haskell (and iogii) need to know how many times Iterate will run and that depends on the size of the result of applying tail which in turn depends on the length of the arg passed from Iterate which is just something consed with what we started with. This would happen anytime you use a vectorized loop. Iogii solves problem by padding the value passed to Iterate, etc. That is it creates an infinite list that starts with our normal list. The extra values are just the default for that type, but you won't normally see them. This works because it allows vectorization to skip the check for if the list should terminate. You won't normally see these default values because they will always be followed by the cons / pad of our foldr / iterate.
You could see these values by looking at the args to our functions directly:
1,2,,3,4 J, Iterate set pp tail 5K > del pp 10 K, → [[[1,2],[3,4],[2],[4],[],[],[]],[],[],[],[],[],[],[],[],[]]
Atlas Solves this problem by detecting self dependencies at run time and then having "faith" that the result will not be empty. But since iogii has dedicated ops for folding we can do this statically which allows for compilation to Haskell. So iterate is actually defined as:
ans superpad block initial cons set ans
Where superpad pads the highest x ranks (where x is the vectorization level of the fold). You can actually use superpad manually to test things out, or padDefault which is what it generates.
So to use these techniques in Haskell you would need to manually superpad for nested zips.
This is difficult to explain, but basically if you just follow folding patterns and don't look directly at args to vectorized folds then you won't have any problems and don't need to know any of this! Just know that folds are not special, they are converted to an intermediate representation that is identical to if you created them using regular ops.