On Tue, Nov 30, 2010 at 9:37 AM, Larry Evans <span dir="ltr"><<a href="mailto:cppljevans@suddenlink.net">cppljevans@suddenlink.net</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
suggested to me that bifold might be similar to the function, Q, of<br>
section 12.5 equation 1) on p. 15 of:<br>
<br>
<a href="http://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf" target="_blank">http://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf</a><br>
<br>
Now Q takes just 1 argument, a function. Also, the f function defined<br>
with Q can be short-circuited, IOW, it may not process all the<br>
elements is a list. Also, it may not even act on a list; however,<br>
that just means it's more general and could be easily specialized to<br>
just act on lists.<br>
<br>
Anyway, I'll reproduce some of the reference's section 12.5 here:<br>
<br>
f == p -> q; Q(f)<br>
<br>
where:<br>
<br>
Q(k) == h <*> [i, k<*>j]<br>
<br>
and where(by p. 4 of reference):<br>
<*> is the function composition operator:<br>
(f <*> g) x == f(g(x))<br>
and where(by p. 9 of reference):<br>
[f,g] x = <f x, g x><br>
and where(by p. 8 of reference)<br>
<x1,x2,...,xn> is a sequence of objects, x1,x2,...xn (like<br>
haskell's tuple: (x1,x2,...,xn)<br>
and where(by p. 8 of reference):<br>
(p -> g; h)(x) means "if p(x) then do g(x) else do h(x)"<br>
<br>
for any functions, k, p, g, h, i, j.<br>
<br>
p. 16 provides a nice shorthand for the result of that function:<br>
<br>
Q^n(g) = /h<*>[i,i<*>j,...,i<*>j^(n-1),g<*>J^n<br>
<br>
where:<br>
<br>
f^n = f<*>f<*>....<*> f for n applications of f<br>
/h<*>[f1,f2,...,fn] is defined on p. 13 of reference.<br></blockquote><div>[snip] <br><br>Thanks, Larry, this is some interesting stuff.<br><br>I'm not sure yet whether Q is equivalent - it may be, but I haven't been able to thoroughly grok it yet.<br>
<br>For uniformity, I shifted the notation you gave to Haskell:<br><br> (.^) :: (a -> a) -> Int -> a -> a<br> f .^ 0 = id<br> f .^ n = f . (f .^ (n - 1))<br><br> (./) :: (b -> c -> c) -> [a -> b] -> (a->c) -> a -> c<br>
(./) = flip . foldr . \h f g -> h <$> f <*> g<br><br> _Q_ :: (b -> c -> c) -> (a -> b) -> (a -> a) -> (a -> c) -> a -> c<br> _Q_ h i j k = h <$> i <*> (k . j)<br>
<br>So the shorthand just states the equivalence of (_Q_ h i j) .^ n and (./) h [ i . (j .^ m) | m <- [0 .. n-1] ] . ( . (j .^ n))<br><br>Looking at it that way, we can see that (_Q_ h i j) .^ n takes some initial value, unpacks it into a list of size n+1 (using i as the iterate function), <br>
derives a base case value from the final value (and some function k) maps the initial values into a new list, then foldrs over them.<br><br>The _f_ function seems to exist to repeat _Q_ until we reach some stopping condition (rather than n times)<br>
<br> _f_ :: (b -> c -> c) -> (a -> b) -> (a -> a) -> (a -> Bool) -> (a -> c) -> a -> c<br> _f_ h i j p q a = if p a then q a else _Q_ h i j (_f_ h i j p q) a<br><br>No simple way to pass values from left to right pops out at me, but I don't doubt that bifold could be implemented in foldr, and therefore there should be *some* way.<br>
<br>I'll have to give the paper a thorough reading (which, I apologize, I haven't had time to do yet). Thanks again!<br></div></div>