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.
I found:
http://www.haskell.org/haskellwiki/Foldl_as_foldr#Folding_by_concatenating_updates
hard to understand. However, scanning
http://www.haskell.org/haskellwiki/Foldl_as_foldr#See_also
shows, on page 13(with fold renamed to foldr):
(1.t): foldl :: ( b -> a -> b) -> b -> ([a] -> b)
(1.0): foldl f v [] = v
(1.1): foldl f v xs = foldr (\x g -> (\a -> g (f a x))) id xs v
which is much simpler than with wiki page; however, it still looks
like foldr on the rhs takes 4 args instead of 3, until one realizes
that foldr is calculating a function instead of a value and the last
arg on the rhs, v, is being passed to that calculated function.
foldr from p. 2 of the reference( again, with renaming) is:
(2.t): foldr :: ( a' -> b' -> b') -> b' -> ([a'] -> b')
(2.0): foldr f v [] = v
(2.1): foldr f v x:xs = f x (foldr f v xs)
So, the (1.1) rhs( except for v) with xs=[1,2,3] gives:
(1.1.rhs.0):
foldr (\x g -> (\a -> g (f a x))) id [1,2,3]
applying(i.e. replacing lhs with rhs) (2.1) to (1.1.rhs.0) with
(2.1) substitutiions being:
[ f <- (\x g -> (\a -> g (f a x)))
, v <- id
, x <- 1
, xs <- [2,3]
]
gives(after renaming x and g to avoid variable capture):
(1.1.rhs.1):
(\x0 g0 -> (\a0 -> g0 (f a0 x0)))
1
(foldr
(\x1 g1 -> (\a1 -> g1 (f a1 x1)))
id
[2,3]
)
applying substitutions:
[x0 <- 1]
in (1.1.rhs.1) gives:
(1.1.rhs.2):
(\g0 -> (\a0 -> g0 (f a0 1)))
(foldr
(\x1 g1 -> (\a1 -> g1 (f a1 x1)))
id
[2,3]
)
applying subsitutions:
[ g0 <-
(foldr
(\x1 g1 -> (\a1 -> g1 (f a1 x1)))
id
[2,3]
)
]
in (1.1.rhs.2) gives:
(1.1.rhs.3):
(\a0 ->
(foldr
(\x1 g1 -> (\a1 -> g1 (f a1 x1)))
id
[2,3]
)
(f a0 1)
)
applying (2.1) to (1.1.rhs.3) with (2.1) substitutions
being:
[ f <- (\x1 g1 -> (\a1 -> g1 (f a1 x1)))
, v <- id
, x <- 2
, xs <- [3]
]
gives:
(1.1.rhs.4):
(\a0 ->
(\x1 g1 -> (\a1 -> g1 (f a1 x1)))
2
(foldr
(\x2 g2 -> (\a2 -> g2(f a2 x2)))
id
[3]
)
)
(f a0 1)
)
applying substitutions:
[x1 <- 2]
in (1.1.rhs.4) gives:
(1.1.rhs.4):
(\a0 ->
(\g1 -> (\a1 -> g1 (f a1 2)))
(foldr
(\x2 g2 -> (\a2 -> g2(f a2 x2)))
id
[3]
)
)
(f a0 1)
)
applying substitutions:
[ g1 <-
(foldr
(\x2 g2 -> (\a2 -> g2 (f a2 x2)))
id
[3]
)
]
in (1.1.rhs.4) gives:
(1.1.rhs.5):
(\a0 ->
(\a1 ->
(foldr
(\x2 g2 -> (\a2 -> g2 (f a2 x2)))
id
[3]
)
(f a1 2)
)
(f a0 1)
)
applying (2.1) to (1.1.rhs.5) with (2.1) substitutions
being:
[ f <- (\x2 g2 -> (\a2 -> g2 (f a2 x2)))
, v <- id
, x <- 3
, xs <- []
]
gives:
(1.1.rhs.6):
(\a0 ->
(\a1 ->
(\x2 g2 -> (\a2 -> g2 (f a2 x2)))
3
( foldr
(\x3 g3 ->(\a3 -> g3 (f a3 x3)))
id
[]
)
)
(f a1 2)
)
(f a0 1)
)
applying (2.0) to (1.1.rhs.6) gives:
(1.1.rhs.6):
(\a0 ->
(\a1 ->
(\x2 g2 -> (\a2 -> g2 (f a2 x2)))
3
id
)
(f a1 2)
)
(f a0 1)
)
applying substitutions:
[ x2 <- 3
, g2 <- id
]
in (1.1.rhs.6) gives:
(1.1.rhs.7):
(\a0 ->
(\a1 ->
(\a2 -> f a2 3
)
(f a1 2)
)
(f a0 1)
)
Then, addding back the tail argument, v, that was left off of
(1.1.rhs.0) gives:
(1.1.rhs.8):
(\a0 ->
(\a1 ->
(\a2 -> f a2 3
)
(f a1 2)
)
(f a0 1)
)
v
Then, the substition:
[ a0 <- v
]
into (1.1.rhs.8) gives:
(1.1.rhs.9):
(\a1 ->
(\a2 -> f a2 3
)
(f a1 2)
)
(f v 1)
Then, the substition:
[ a1 <- (f v 1)
]
into (1.1.rhs.9) gives:
(1.1.rhs.10):
(\a2 -> f a2 3
)
(f (f v 1 ) 2 )
Then, the substition:
[ a2 <- (f (f v 1 ) 2 )
]
into (1.1.rhs.10) gives:
(1.1.rhs.11):
f (f (f v 1 ) 2 ) 3
which agrees with:
foldl f z [x1, x2, ..., xn] == (...((z ‘f‘ x1) ‘f‘ x2) ‘f‘...)
‘f‘ xn
from:
http://www.haskell.org/onlinereport/haskell2010/haskellch9.html#x16-1720009.1
except for the use of infix f instead of prefix f and the the use
of z instead of v, and the use of i instead of xi for i=1,2,3.