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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Olumide
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Where is the accumulator in the expression foldr (<=<) return (replicate x oveKnight)? -- from LYAH example

Ut Primum
Hi,
Looking at the structure of the expression, you should have

foldr operator accumulator list

So in your example the accumulator should be "return" (because it is the second argument)

Il gio 26 lug 2018, 03:45 Olumide <[hidden email]> ha scritto:
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Where is the accumulator in the expression foldr (<=<) return (replicate x oveKnight)? -- from LYAH example

Paul
In reply to this post by Olumide

Hello,

`return` is the initial value. So, `replicate x oveKnignt)` is a list of functions. `foldr` folds them with initial value `return` with the `<=<` between them: functions are folding with (<=<). First folding value is `return` function. You can check the types with :t something in the GHCi.

Result of folding is flow of functions or long functions circuit. `return start` is the same as to pass `start` to this functions circuit:

inMany x start = foldr (<=<) return (replicate x oveKnight) $ start

Idea seems, to make from [KnighPos -> [KnighPos]] functions list one function: KnighPos -> [KnighPos] performing those functions step by step (<=<) and to pass `start` to it. Due to `<=<`  joining of functions is not "do", but "do for each...", because <=< is in the list monad. Something like:

for x in f-last start:
  for y in f-prelast x:
    ...
You can look at these types:
:t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
 :t (<=<)
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c


26.07.2018 04:44, Olumide wrotes:
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Where is the accumulator in the expression foldr (<=<) return (replicate x oveKnight)? -- from LYAH example

Tony Morris-4
In reply to this post by Olumide
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
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

signature.asc (499 bytes) Download Attachment