Re: Announcing Functional Fall: A 6-session functional programming reading circle in the Fall

[Jim Snavely <ludflu@gmail.com>]

This is rather confusing, because our notions of "to the left" and "to
the right" are ambiguous. Let's use the source.
We'll find the definitions use Hoogle. http://haskell.org/hoogle/

The documentation actually says this:
http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/GHC-Base.html#foldr

It seems GHC-Base is part of the standard Prelude.

-- | 'foldr', applied to a binary operator, a starting value (typically
-- the right-identity of the operator), and a list, reduces the list
-- using the binary operator, from right to left:

And the code below it says this:

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

Which shows it applying the function k using infix syntax (like a
binary operator)  to two arguments, namely the head of the list (1)
and the results of folding the rest of the list via "go ys" (2).

At first, to my way of thinking, this would be notionally "to the
right". But consider that the function k can't be fully applied until
the rest of the list has been folded. So in fact, as the comment says,
it has to be applied "from the right to the left"

Conversely, check out the definition of foldl
http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/GHC-List.html#foldl

-- | 'foldl', applied to a binary operator, a starting value (typically
-- the left-identity of the operator), and a list, reduces the list
-- using the binary operator, from left to right:
--
-- > foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
--
-- The list must be finite.

-- We write foldl as a non-recursive thing, so that it
-- can be inlined, and then (often) strictness-analysed,
-- and hence the classic space leak on foldl (+) 0 xs

foldl        :: (a -> b -> a) -> a -> [b] -> a
foldl f z0 xs0 = lgo z0 xs0
             where
                lgo z []     =  z
                lgo z (x:xs) = lgo (f z x) xs

lgo is invoked with two arguments:
1. the result of applying f to head of the list (x) and the starting
value (z) passed in as (z0)
2. the tail of the list

In this case, apparently you can still run out of space, but its not
because we're evaluating from the end of the list.

Relevant: http://haskell.org/haskellwiki/Foldr_Foldl_Foldl%27

In fact when I've created the "classic space leak" mentioned above, it
was because I wasn't using foldl'
(pronounced "fold-el-prime") which is the strict version that will
start reducing the expressions.

http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Data-List.html#foldl%27

It uses the "seq" function to force evaluation of f before recursing.

--Jim

On Mon, Sep 12, 2011 at 7:08 AM, Dan Mead <d.w.mead@gmail.com> wrote:
> foldr is TO the right
>
> On Mon, Sep 12, 2011 at 12:48 AM, Eduard Kram <pbl2@hotmail.com> wrote:
>>
>> All:
>>
>> Thanks to Trevor et al. for organizing, and thanks to all for a great
>> discussion during recent event.
>>
>> It has to be made a fix to one of the meeting 's conclusions that is also
>> recorded in noted ("Also, foldr was mentioned but not foldl, because fold
>> left has to go te the end of the array (and thus means recurring to the
>> bottom of the possibly infinite list)").
>>
>> Actually, as the name suggests, the folding by foldr is made from the
>> RIGHT and reason why it is still more useful then foldl is different.
>>
>> I made a few related notes on my site tisr@wordpress.com
>>
>> Please, use password ed to access the notes.
>>
>> I think also that everybody can and should develop clear understanding how
>> foldr works, even if the opposite was suggested. Borrowing a few parenthesis
>> from the LISP really helps ;-)
>>
>> ________________________________
>> Date: Wed, 7 Sep 2011 23:08:31 -0400
>> Subject: Re: Announcing Functional Fall: A 6-session functional
>> programming reading circle in the Fall
>> From: hblanks@monetate.com
>> To: philly-lambda@googlegroups.com
>>
>> All,
>> Thanks to Trevor et al. for organizing, and thanks to all for a great
>> discussion this evening. Notes are up at:
>> -
>> http://public.monetate.net.s3.amazonaws.com/engineering-blog/2011-09-07/function_fall_meeting_1_notes.html
>> in HTML and at:
>> -
>> http://public.monetate.net.s3.amazonaws.com/engineering-blog/2011-09-07/function_fall_meeting_1_notes.txt
>> in plain (aka ReStructured) text.
>> -HJB
>> --
>> Hunter Blanks
>> hblanks@monetate.com
>> Monetate, Inc. - Test, Target, Personalize
>> Next Generation Website Optimization for Marketers
>> www.monetate.com
>
>



-- 
--Jim