[<<][staapl][>>][..]Sun Sep 20 18:51:45 CEST 2009

Main rationale: boundary conditions significantly complicate expression of folds over images. Write an algebra of fusable operations, first ignoring boundary conditions (infinite fold), and second taking that into account. Parameterizing composition of 2D filter masks will yield a large class of useful programs, and will probably give some idea about how to move on to more serious folds. So... How to express data types? Or can this be avoided? Moving to the simpler problem of 1D filter masks over the stream s, which consists of an infinite list of elements s = e*, this is about the operator Z wich delays the stream by one time instance. Q: what does `Z + 1' mean? Here Z is an operator: s -> s this makes 1 also an operator: s -> s and + is an operator combinator: (s->s, s->s) -> ((s,s)->s) It looks like it is actually this shift operator that makes things so problematic. The reason is that it ``looks inside'' an iteration over a stream. What I mean is that, while it is easy to lift + to a stream operation (s,s) -> s and feed it with two streams s and Zs, it is less trivial to turn the operation into an operation f : s->s, where f is obtained from +,1 and Z. More specificially, the function that provides arguments from the input stream to the scalar + : (e,e) -> e somehow needs to retain memory. This ``state maintenance'' seems to be the central problem related to combining maps + folds and stream shift operators. In other words, there is a difference between the following lift types, depending on lift over streams, or lift over s,Zs. S-lift : ((e,e) -> e) -> ((s,s) -> s) Z-lift : ((e,e) -> e) -> (s -> s) Making these functions explicit and providing laws for them is probably what needs to be done. The lower one can be separated in as ((s -> s), (s -> s), ((e,e) -> e)) -> (s -> s) i.e. taking two stream transformers and a binary scalar op, and feeding the transformed streams into the binary element op. Filling in 1,Z,+ gives the filter function f mentioned above. So.. the interaction between map2 : ((e,e)->e, s ,s) -> ((s, s) -> s) map1 : ((e->e), s) -> (s->s) Z : (s -> s) streamZ s = (s -> (s,s)) map2(+, s, Z(s)) = map1(+,streamZ(s)) : s->s It's important to distinguish between a stream of tuples and a tuple of streams. It looks like making the types work is going to bring us half way there (in the light of Wadler's free theorems[1]). [1] http://homepages.inf.ed.ac.uk/wadler/papers/free/free.ps

[Reply][About]

[<<][staapl][>>][..]