On 12/07/10 12:36, Henning Thielemann wrote:

Noah Easterly wrote:

...

Somebody suggested I post this here if I wanted feedback.

So I was thinking about the ReverseState monad I saw mentioned on r/haskell a couple days ago, and playing around with the concept of information flowing two directions when I came up with this function:

bifold :: (l -> a -> r -> (r,l)) -> (l,r) -> [a] -> (r,l) bifold _ (l,r) [] = (r,l) bifold f (l,r) (a:as) = (ra,las) where (ras,las) = bifold f (la,r) as (ra,la) = f l a ras

(I'm sure someone else has come up with this before, so I'll just say I discovered it, not invented it).

Basically, it's a simultaneous left and right fold, passing one value from the start of the list toward the end, and one from the end toward the start.

I also needed a bidirectional fold in the past. See foldl'r in http://code.haskell.org/~thielema/utility/src/Data/List/HT/Private.hs

You can express it using foldr alone, since 'foldl' can be written as 'foldr': http://www.haskell.org/haskellwiki/Foldl_as_foldr

You may add your example to the Wiki.

Hi Henning, I tried to understand the Foldl_as_foldr method by actually manually tracing the the execution. The result is in the attachment 1(Bifold.Thielemann.txt). Then I tried to implement the equivalent of the foldl'r in your Private.hs with the if_recur mentioned in my other post: http://www.mail-archive.com/haskell-cafe@haskell.org/msg84793.html This code is in attachment 2(HutBacFoldlr.hs). It uses a small help module to make explicit the associativity of the folded values. This help module is in attachment 3(Assoc.hs). The emacs eshell output shows: --{--eshell output-- /home/evansl/prog_dev/haskell/my-code $ ghci HutBacFoldlr.hs GHCi, version 6.12.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. [1 of 2] Compiling Assoc ( Assoc.hs, interpreted ) [2 of 2] Compiling HutBacFoldlr ( HutBacFoldlr.hs, interpreted ) Ok, modules loaded: HutBacFoldlr, Assoc. *HutBacFoldlr> test Loading package array-0.3.0.0 ... linking ... done. Loading package containers-0.3.0.0 ... linking ... done. Loading package mtl-1.1.0.2 ... linking ... done. Loading package fgl-5.4.2.2 ... linking ... done. ***test_inp: [(1,'a'),(2,'b'),(3,'c')] ***foldl'r AsLeft AsNull AsRight AsNull test_inp: (AsLeft (AsLeft (AsLeft AsNull 1) 2) 3,AsRight 'a' (AsRight 'b' (AsRight 'c' AsNull))) ***if_recur_foldlr AsLeft AsNull AsRight AsNull test_inp: (AsLeft (AsLeft (AsLeft AsNull 1) 2) 3,AsRight 'a' (AsRight 'b' (AsRight 'c' AsNull))) ---foldl'r_fst: AsLeft (AsLeft (AsLeft AsNull 1) 2) 3 ---foldl'r_snd: AsRight 'a' (AsRight 'b' (AsRight 'c' AsNull)) *HutBacFoldlr> --}--eshell output-- The two outputs preceded by the *** lines show both foldl'r and if_recur_foldlr compute the same result. The two outputs preceded by the --- lines show that part of the result of foldl'r output is a tuple whose fst is a function and whose 2nd is an already calculated value. The manual trace in attachment 1 shows how this fst function is calculated. I think the last step in foldl'r, the mapFst call, corresponds to applying the last argument in the foldl_as_foldr method as shown at (1.1.rhs.8) of attachment 1. IOW, the application of v in the rhs of (1.1) in attachment 1 performs the same role (as far as the foldl calculation is concerned) the mapFst ($b0) . in foldl'r rhs. What's also interesting is that with if_recur_foldlr, the foldr calculations (i.e. calls to fr argument) are delayed until going up the call stack; whereas in foldl'r the foldl calculations (i.e. calls to fl argument) are delayed by composing a sequence of functions with the: \b -> k $! fl b a expression. I'm not real sure if these observations have any importantance, but maybe there's a difference of performance between composing a sequence of functions (as in the foldl'r function) as opposed to storing values on the call stack (as in the if_record_foldlr function). Maybe you have some insight on this. -regards, Larry