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
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.
{-
Purpose:
Compare outputs from the foldl'r function from:
[THI10]
http://code.haskell.org/~thielema/utility/src/Data/List/HT/Private.hs
based on the method used to implement foldl in terms of foldr as described
on page 13 of:
[HUT99]
http://www.cs.nott.ac.uk/~gmh/fold.pdf
and another function, if_recur_foldlr, using a function, if_recur, modelled
after f in section 12.5 of:
[BAC77]
http://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf
-}
module HutBacFoldlr where
import Assoc
import Data.Graph.Inductive.Query.Monad(mapFst) --renamed from [THI10]
-- {*foldl'r from [THI10]
foldl'r
:: (b -> a -> b) -> b -- foldl function, start value
-> (c -> d -> d) -> d -- foldr function, start value
-> [(a,c)]
-> (b,d)
foldl'r
fl b0
fr d0
= mapFst ($b0) .
foldr
(\(a,c) ~(k,d) -> (\b -> k $! fl b a, fr c d))
(id,d0)
-- }*foldl'r from [THI10]
test_inp = [(1,'a'),(2,'b'),(3,'c')]
foldl'r_out = foldl'r AsLeft AsNull AsRight AsNull test_inp
foldl'r_foldr = foldr (\(a,c) ~(k,d) -> (\b -> k $! AsLeft b a, AsRight c d)) (id,AsNull) test_inp
foldl'r_fst = (fst foldl'r_foldr) AsNull
foldl'r_snd = snd foldl'r_foldr
-- {*if_recur from [BAC77]
if_recur
:: state_down
-> (state_down -> Bool)
-> (state_down -> state_down)
-> (state_down -> state_saved)
-> ((state_saved,state_up) -> state_up)
-> (state_down -> state_up)
-> state_up
if_recur
state_now -- current state
recur_ -- ::state_down -> Bool (continue recursion?)
then_down -- ::state_down -> state_down
save_state -- ::state_down -> state_saved
now_up -- ::((state_saved,state_up)->state_up
else_ -- ::state_down -> state_up
{- The following table shows the corresponndence
between the f in section 12.5 of [BAC77]
and the arguments to this function:
[BAC77] [if_recur]
======= ==========
p recur_
g else_
j then_down
i save_state
h now_up
-}
= if recur_ state_now
then now_up
( save_state state_now
, if_recur (then_down state_now)
recur_
then_down
save_state
now_up
else_
)
else else_ state_now
-- }*if_recur from [BAC77]
if_recur_foldlr
:: (b -> a -> b) -> b --foldl function, start value
-> (c -> d -> d) -> d --foldr function, start value
-> [(a,c)]
-> (b,d)
if_recur_foldlr
fl b0
fr d0
ac_pairs
= if_recur
(ac_pairs,(b0,d0)) --state_now
(not.null.fst) --recur_
(\((a0,c0):ac_pairs,(bn,dn)) -> (ac_pairs,(fl bn a0,d0))) --then_down
(\((a0,c0):ac_pairs,(bn,dn)) -> c0) --save_state
(\(c0,(bn,dn)) -> (bn,fr c0 dn))--now_up
(\(ac_pairs,(bn,dn)) -> (bn,dn)) --else_
if_recur_out = if_recur_foldlr AsLeft AsNull AsRight AsNull test_inp
test = sequence_
[ putStrLn "***test_inp:"
, print test_inp
, putStrLn "***foldl'r AsLeft AsNull AsRight AsNull test_inp:"
, print foldl'r_out
, putStrLn "***if_recur_foldlr AsLeft AsNull AsRight AsNull test_inp:"
, print if_recur_out
, putStrLn "---foldl'r_fst:"
, print foldl'r_fst
, putStrLn "---foldl'r_snd:"
, print foldl'r_snd
]
{-
Purpose:
A data structure which shows "association" to
either left or right depending on constructor.
-}
module Assoc where
data Assoc a
= AsNull
| AsLeft (Assoc a) a
| AsRight a (Assoc a)
deriving(Show)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
