[Haskell-beginners] Where is the accumulator in the expression foldr (<=<) return (replicate x oveKnight)? -- from LYAH example

Tony Morris tonymorris at gmail.com
Fri Jul 27 03:29:31 UTC 2018


foldr does not involve an accumulator. Only left folds involve an
accumulator. Specifically, the expression:

foldl f z list

can be though of as this loop:

var r = z
foreach(element in list) {
  r = f(r, element)
}
return r

That is why, for example, foldl (\r element -> element : r) [] will
reverse a list. The accumulator here is the (r) value in the loop.

The foldr function does constructor replacement, and in no prescribed
order. The expression foldr f z list will replace every (:) with (f) and
[] with (z) in list.

So the expression foldr (<=<) return will take a list, such as thing one:

let list = a : b : c : d : e : []

and turn it into this value:

foldr (<=<) return list
=
a <=< b <=< c <=< d <=< e <=< return

This will occur in no prescribed order, although the replacement is
right-associative. It is often said that foldr "starts at the
right-most", however, this is untrue, since foldr works on infinite
list, which has no notion of right-most. Importantly, there is no notion
of "accumulator" here, only constructor replacement.

The right-associativity simply means that the parentheses are to the right:

a <=< (b <=< (c <=< (d <=< (e <=< return))))

However, this does not necessarily impose an execution order, or
accumulator. Consider this expression:

foldr const (repeat 1)

This will produce the value:

1 `const` (1 `const` (1 `const` 1 ...

The result of normalising this expression produces the value 1. There is
no notion of the "right-most" to "accumulate" anything. It simply
evaluates and the answer is 1.


On 07/26/2018 11:44 AM, Olumide wrote:
> Dear List,
>
> Chapter 13 of LYAH
> (http://learnyouahaskell.com/for-a-few-monads-more#useful-monadic-functions)
> has the following code block
>
> import Data.List
>
> inMany :: Int -> KnightPos -> [KnightPos]
> inMany x start = return start >>= foldr (<=<) return (replicate x
> oveKnight)
>
> What I'd like to know is where the accumulator of foldr is in this
> example.
>
> Regards,
>
> - Olumide
>
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: OpenPGP digital signature
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20180727/bc5463ec/attachment.sig>


More information about the Beginners mailing list