[Haskell-cafe] Bifold: a simultaneous foldr and foldl

[Larry Evans]

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



-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Bifold.Thielemann.txt
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20101219/928dc938/attachment.txt>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: HutBacFoldlr.hs
Type: text/x-haskell
Size: 3418 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20101219/928dc938/attachment.hs>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Assoc.hs
Type: text/x-haskell
Size: 240 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20101219/928dc938/attachment-0001.hs>